A highway-centric labeling approach for answering distance queries on large sparse graphs
- Authors: Jin, Ruoming , Ruan, Ning , Xiang, Yang , Lee, Victor
- Date: 2012
- Type: Text , Conference paper
- Relation: ACM SIGMOD International Conference on Management of Data, 2012 p. 445-456
- Full Text: false
- Reviewed:
- Description: The distance query, which asks the length of the shortest path from a vertex u to another vertex v, has applications ranging from link analysis, semantic web and other ontology processing, to social network operations. Here, we propose a novel labeling scheme, referred to as Highway-Centric Labeling, for answering distance queries in a large sparse graph. It empowers the distance labeling with a highway structure and leverages a novel bipartite set cover framework/algorithm. Highway-centric labeling provides better labeling size than the state-of-the-art 2-hop labeling, theoretically and empirically. It also offers both exact distance and approximate distance with bounded accuracy. A detailed experimental evaluation on both synthetic and real datasets demonstrates that highway-centric labeling can outperform the state-of-the-art distance computation approaches in terms of both index size and query time. © 2012 ACM.
- Description: Proceedings of the ACM SIGMOD International Conference on Management of Data
A sparsification approach for temporal graphical model decomposition
- Authors: Ruan, Ning , Jin, Ruoming , Lee, Victor , Huang, K
- Date: 2009
- Type: Text , Conference paper
- Full Text: false
- Reviewed: