TF-label: A topological-folding labeling scheme for reachability querying in a large graph
Refereed conference paper presented and published in conference proceedings

Times Cited
Altmetrics Information

Other information
AbstractReachability querying is a basic graph operation with numerous important applications in databases, network analysis, computational biology, software engineering, etc. Although many indexes have been proposed to answer reachability queries, most of them are only efficient for handling relatively small graphs. We propose TF-label, an efficient and scalable labeling scheme for processing reachability queries. TF-label is constructed based on a novel topo-logical folding (TF) that recursively folds an input graph into half so as to reduce the label size, thus improving query efficiency. We show that TF-label is efficient to construct and propose efficient algorithms and optimization schemes. Our experiments verify that TF-label is significantly more scalable and efficient than the state-of-the-art methods in both index construction and query processing. Copyright © 2013 ACM.
All Author(s) ListCheng J., Huang S., Wu H., Fu A.W.-C.
Name of Conference2013 ACM SIGMOD Conference on Management of Data, SIGMOD 2013
Start Date of Conference22/06/2013
End Date of Conference27/06/2013
Place of ConferenceNew York, NY
Country/Region of ConferenceUnited States of America
Pages193 - 204
LanguagesEnglish-United Kingdom
KeywordsGraph indexing, Graph querying, Graph reachability

Last updated on 2020-24-09 at 00:37