|
Published Articles >> Table of Contents >> Abstract
22nd International Conference on Data Engineering (ICDE'06)
p. 75
Dual Labeling: Answering Graph Reachability Queries in Constant Time
Haixun Wang, IBM T. J. Watson Research Center
Hao He2, Duke University
Jun Yang, Duke University
Philip S. Yu, IBM T. J. Watson Research Center
Jeffrey Xu Yu, The Chinese University of Hong Kong
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDE.2006.53
Send link to a friend
| Abstract |
|
Graph reachability is fundamental to a wide range of applications,
including XML indexing, geographic navigation,
Internet routing, ontology queries based on RDF/OWL, etc.
Many applications involve huge graphs and require fast answering
of reachability queries. Several reachability labeling
methods have been proposed for this purpose. They
assign labels to the vertices, such that the reachability between
any two vertices may be decided using their labels
only. For sparse graphs, 2-hop based reachability labeling
schemes answer reachability queries efficiently using relatively
small label space. However, the labeling process
itself is often too time consuming to be practical for large
graphs. In this paper, we propose a novel labeling scheme
for sparse graphs. Our scheme ensures that graph reachability
queries can be answered in constant time. Furthermore,
for sparse graphs, the complexity of the labeling process
is almost linear, which makes our algorithm applicable
to massive datasets. Analytical and experimental results
show that our approach is much more efficient than stateof-
the-art approaches. Furthermore, our labeling method
also provides an alternative scheme to tradeoff query time
for label space, which further benefits applications that use
tree-like graphs.
|
 Additional Information
|
Citation:
Haixun Wang, Hao He2, Jun Yang, Philip S. Yu, Jeffrey Xu Yu,
"Dual Labeling: Answering Graph Reachability Queries in Constant Time,"
icde,
p. 75,
22nd International Conference on Data Engineering (ICDE'06),
2006
|
|
