- Title
- A highway-centric labeling approach for answering distance queries on large sparse graphs
- Creator
- Jin, Ruoming; Ruan, Ning; Xiang, Yang; Lee, Victor
- Date
- 2012
- Type
- Text; Conference paper
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/101888
- Identifier
- vital:10717
- Identifier
- ISBN:07308078 (ISSN); 9781450312479 (ISBN)
- Abstract
- 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.; Proceedings of the ACM SIGMOD International Conference on Management of Data
- Relation
- ACM SIGMOD International Conference on Management of Data, 2012 p. 445-456
- Rights
- Copyright ACM
- Rights
- This metadata is freely available under a CCO license
- Subject
- Bipartite set cover; Distance query; Highway-centric labeling; Distance computation; Distance labeling; Experimental evaluation; Highway structures; Labeling scheme; Link analysis; Query time; Real data sets; Set cover; Shortest path; Social Networks; Sparse graphs; Graph theory; Highway administration
- Reviewed
- Hits: 985
- Visitors: 957
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|