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

6 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.

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

Labeling
Processing

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
Qin, Yongrui ; Sheng, Quan Z. ; Zhang, Wei Emma. / SIEF : Efficiently answering distance queries for failure prone graphs. Advances in Database Technology - EDBT 2015: Proceedings of the 18th International Conference on Extending Database Technology. editor / Gustavo Alonso ; Floris Geerts ; Lucian Popa ; Pablo Barceló ; Jens Teubner ; Martín Ugarte ; Jan Van den Bussche ; Jan Paredaens. OpenProceedings.org, University of Konstanz, University Library, 2015. pp. 145-156
@inproceedings{fe7916c8a6da455cad32b93800700a36,
title = "SIEF: Efficiently answering distance queries for failure prone graphs",
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.",
keywords = "2-hop labeling, Distance query, Edge failure, Shortest paths",
author = "Yongrui Qin and Sheng, {Quan Z.} and Zhang, {Wei Emma}",
year = "2015",
month = "3",
doi = "10.5441/002/edbt.2015.14",
language = "English",
pages = "145--156",
editor = "Gustavo Alonso and Floris Geerts and Lucian Popa and Pablo Barcel{\'o} and Jens Teubner and Mart{\'i}n Ugarte and {Van den Bussche}, Jan and Jan Paredaens",
booktitle = "Advances in Database Technology - EDBT 2015",
publisher = "OpenProceedings.org, University of Konstanz, University Library",

}

Qin, Y, Sheng, QZ & Zhang, WE 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. OpenProceedings.org, University of Konstanz, University Library, pp. 145-156, 18th International Conference on Extending Database Technology, Brussels, Belgium, 23/03/15. https://doi.org/10.5441/002/edbt.2015.14

SIEF : Efficiently answering distance queries for failure prone graphs. / Qin, Yongrui; Sheng, Quan Z.; Zhang, Wei Emma.

Advances in Database Technology - EDBT 2015: Proceedings of the 18th International Conference on Extending Database Technology. ed. / Gustavo Alonso; Floris Geerts; Lucian Popa; Pablo Barceló; Jens Teubner; Martín Ugarte; Jan Van den Bussche; Jan Paredaens. OpenProceedings.org, University of Konstanz, University Library, 2015. p. 145-156.

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

TY - GEN

T1 - SIEF

T2 - Efficiently answering distance queries for failure prone graphs

AU - Qin, Yongrui

AU - Sheng, Quan Z.

AU - Zhang, Wei Emma

PY - 2015/3

Y1 - 2015/3

N2 - 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.

AB - 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.

KW - 2-hop labeling

KW - Distance query

KW - Edge failure

KW - Shortest paths

UR - http://www.scopus.com/inward/record.url?scp=84976328919&partnerID=8YFLogxK

U2 - 10.5441/002/edbt.2015.14

DO - 10.5441/002/edbt.2015.14

M3 - Conference contribution

SP - 145

EP - 156

BT - Advances in Database Technology - EDBT 2015

A2 - Alonso, Gustavo

A2 - Geerts, Floris

A2 - Popa, Lucian

A2 - Barceló, Pablo

A2 - Teubner, Jens

A2 - Ugarte, Martín

A2 - Van den Bussche, Jan

A2 - Paredaens, Jan

PB - OpenProceedings.org, University of Konstanz, University Library

ER -

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