An I/O-efficient distance oracle for evolving real-world graphs
|Title:||An I/O-efficient distance oracle for evolving real-world graphs||Authors:||Ajwani, Deepak; Meyer, Ulrich; Veith, David||Permanent link:||http://hdl.handle.net/10197/10515||Date:||5-Jan-2015||Online since:||2019-05-20T08:29:29Z||Abstract:||Computing shortest path distance is a fundamental primitive in many graph applications. On graphs that do not fit in the main memory of the computing device, computing such distances requires hours to months even with the best I/O-efficient shortest path implementations. For applications requiring many such shortest path distances, one would ideally like to preprocess the input graph into a space-efficient data structure I/O-efficiently, such that the distance queries can be answered with a small additive distortion using only O(1) I/Os. Furthermore, in a batch setting, one would like to answer O(n) such distance queries in Õ(n/B) I/Os. In this paper, we focus on engineering an I/O-efficient distance oracle for large graphs that model real-world interactions. Our engineered oracle (i) preprocesses graphs with multi-billion edges in less than an hour using a single core of a typical PC, (ii) answers online shortest path queries in milliseconds using a SSD, (iii) answers batched shortest path queries using HDDs with an average time per query of a few microseconds, (iv) results in a highly accurate shortest path estimate and (v) uses space linear in the number of nodes. Our implementation creates small oracle labels (i.e., they can still be kept in internal memory for rather large graphs) but also efficiently handles the case when both the graph and these labels have to reside on external storage. Dynamic settings where new edges are continuously inserted into the graph are efficiently supported, too.||metadata.dc.description.othersponsorship:||DFG grant
MADALGO – Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation
|Type of material:||Conference Publication||Publisher:||SIAM||Copyright (published version):||2015 the Society for Industrial and Applied Mathematics||Keywords:||I/O-efficient distance oracle; Graph algorithms; Oracle labels; Graph computations||DOI:||10.1137/1.9781611973754.14||Other versions:||https://archive.siam.org/meetings/alenex15/||Language:||en||Status of Item:||Not peer reviewed||Is part of:||Brandes, U., Eppstein, D. (eds.). 2015 Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX)||Conference Details:||The Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX 2015), 5 January 2015||ISBN:||978-1-61197-375-4|
|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.