SIEF: Efficiently answering distance queries for failure prone graphs

Yongrui Qin, Quan Z. Sheng, Wei Emma Zhang

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

8 Citations (Scopus)

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 publicationProceedings of the 18th International Conference on Extending Database Technology
EditorsGustavo Alonso, Floris Geerts, Lucian Popa, Pablo Barceló, Jens Teubner, Martín Ugarte, Jan Van den Bussche, Jan Paredaens
PublisherOpenProceedings.org, University of Konstanz, University Library
Pages145-156
Number of pages12
ISBN (Electronic)9783893180677
DOIs
Publication statusPublished - Mar 2015
Externally publishedYes
Event18th International Conference on Extending Database Technology - Brussels, Belgium
Duration: 23 Mar 201527 Mar 2015
Conference number: 18
http://www.wikicfp.com/cfp/servlet/event.showcfp?eventid=38926 (Link to Conference Details)

Conference

Conference18th International Conference on Extending Database Technology
Abbreviated titleEDBT 2015
CountryBelgium
CityBrussels
Period23/03/1527/03/15
Internet address

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

  • Cite this

    Qin, Y., Sheng, Q. Z., & Zhang, W. E. (2015). SIEF: Efficiently answering distance queries for failure prone graphs. In G. Alonso, F. Geerts, L. Popa, P. Barceló, J. Teubner, M. Ugarte, J. Van den Bussche, ... J. Paredaens (Eds.), Advances in Database Technology - EDBT 2015: Proceedings of the 18th International Conference on Extending Database Technology (pp. 145-156). OpenProceedings.org, University of Konstanz, University Library. https://doi.org/10.5441/002/edbt.2015.14