SIEF

efficiently answering distance queries for failure prone graphs

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

10 Citations (Scopus)
4 Downloads (Pure)

Abstract

Shortest path computation is one of the most fundamental operations for managing and analyzing graphs. A number of methods have been proposed to answer shortest path distance queries on static graphs. Unfortunately, there is little work on answering distance queries on dynamic graphs, particularly graphs with edge failures. Today's real-world graphs, such as the social network graphs and web graphs, are evolving all the time and link failures occur due to various factors, such as people stopping following others on Twitter or web links becoming invalid. Therefore, it is of great importance to handle distance queries on these failure-prone graphs. This is not only a problem far more difficult than that of static graphs but also important for processing distance queries on evolving or unstable networks. In this paper, we focus on the problem of computing the shortest path distance on graphs subject to edge failures. We propose SIEF, a Supplemental Index for Edge Failures on a graph, which is based on distance labeling. Together with the original index created for the original graph, SIEF can support distance queries with edge failures efficiently. By exploiting properties of distance labeling on static graphs, we are able to compute very compact distance labeling for all singe-edge failure cases on dynamic graphs. We extensively evaluate our algorithms using six real-world graphs and confirm the effectiveness and efficiency of our approach.

Original languageEnglish
Title of host publicationAdvances in Database Technology - EDBT 2015
Subtitle of host publication18th International Conference on Extending Database Technology : proceedings
EditorsGustavo Alonso, Floris Geerts, Lucian Popa, Pablo Barceló, Jens Teubner, Martín Ugarte, Jan Van den Bussche, Jan Paredaens
Place of PublicationKonstanz, Germany
PublisherOpenProceedings.org, University of Konstanz, University Library
Pages145-156
Number of pages12
ISBN (Electronic)9783893180677
DOIs
Publication statusPublished - 2015
Externally publishedYes
Event18th International Conference on Extending Database Technology, EDBT 2015 - Brussels, Belgium
Duration: 23 Mar 201527 Mar 2015

Other

Other18th International Conference on Extending Database Technology, EDBT 2015
CountryBelgium
CityBrussels
Period23/03/1527/03/15

Bibliographical note

Copyright the Author(s) 2015. Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.

Keywords

  • shortest paths
  • distance query
  • 2-hop labeling
  • edge failure

Fingerprint Dive into the research topics of 'SIEF: efficiently answering distance queries for failure prone graphs'. Together they form a unique fingerprint.

Cite this