An I/O-efficient distance oracle for evolving real-world graphs

Files in This Item:
File Description SizeFormat 
ajwani_alenex15.pdf378.4 kBAdobe PDFDownload
Title: An I/O-efficient distance oracle for evolving real-world graphs
Authors: Ajwani, DeepakMeyer, UlrichVeith, 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 oracleGraph algorithmsOracle labelsGraph 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

Page view(s)

223
Last Week
5
Last month
checked on Feb 25, 2020

Download(s)

103
checked on Feb 25, 2020

Google ScholarTM

Check

Altmetric


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.