Processing Large Graphs: Representations, Storage, Systems and Algorithms
|Title:||Processing Large Graphs: Representations, Storage, Systems and Algorithms||Authors:||Ajwani, Deepak; Karnstedt, Marcel; Sala, Alessandra||Permanent link:||http://hdl.handle.net/10197/10841||Date:||22-May-2015||Online since:||2019-07-03T06:53:08Z||Abstract:||Analyzing and processing large graphs is of fundamental importance for an ever-growing number of applications. Significant advancements in the last few years at both, systems and algorithmic side, let graph processing become increasingly scalable and efficient. Often, these advances are still not well-known and well-understood outside the systems and algorithms communities. In particular, there is very little understanding of the various trade-offs involved in the usage of particular combinations of algorithms, data structures, and systems. This tutorial will have a particular focus on this aspect, imparting theoretical knowledge intertwined with hands-on experience. Since there is no clearly winning system/algorithm combination that performs best on all the different metrics, it is of utmost importance to understand the pros and cons of the various alternatives. The tutorial will enable application developers in industry and academics, students as well as researchers to make corresponding decisions in an informed way. The participants do neither require any particular a-priori knowledge apart from a basic understanding of core computer science concepts, nor any special equipment apart from their laptop. After a general introduction, we will describe the critical dimensions that need to be tackled together to effectively and efficiently overcome problems in large graph processing: data representation, data storage, acceleration via multi-core programming, and horizontally scalable graph-processing infrastructures. Thereafter, we will provide an overview of existing graph-processing systems and graph databases. This will be followed by hands-on experiences with popular representatives of such systems. Finally, we will provide a detailed description of algorithms used in these systems for fundamental problems like shortest paths and Pagerank, how they are implemented, and how this affects the overall performance. We will also cover basic data structures such as distance oracles that can be built on these systems to efficiently answer distance queries for real-world graphs.||Type of material:||Conference Publication||Publisher:||ACM||Start page:||1545||End page:||1545||Copyright (published version):||2015 the Authors||Keywords:||Graph algorithms; Data structures; Systems; Tutorial; Large graph processing; Data representation; Data storage; Multi-core programming; Graph-processing infrastructures||DOI:||10.1145/2740908.2741990||Other versions:||http://www.www2015.it/||Language:||en||Status of Item:||Not peer reviewed||Is part of:||WWW 2015 Companion - Proceedings of the 24th International Conference on World Wide Web||Conference Details:||WWW 2015: 24th International World Wide Web Conference, Florence, Italy, 18-22 May 2015||ISBN:||9781450334730|
|Appears in Collections:||Computer Science Research Collection|
Show full item record
This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.