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.
- I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck. A hub-based labeling algorithm for shortest paths in road networks. In Proceedings of the 10th international conference on Experimental algorithms, 2011. Google ScholarDigital Library
- I. Abraham, A. Fiat, A. V. Goldberg, and R. F. Werneck. Highway dimension, shortest paths, and provably efficient algorithms. In SODA '10, 2010. Google ScholarDigital Library
- R. Agrawal and H. V. Jagadish. Algorithms for searching massive graphs. TKDE, 6(2):225--238, 1994. Google ScholarDigital Library
- Stephen Alstrup, Philip Bille, and Theis Rauhe. Labeling schemes for small distances in trees. In SODA, pages 689--698, 2003. Google ScholarDigital Library
- K. Anyanwu and A Sheth. P-queries: enabling querying for semantic associations on the semantic web. In WWW '03, 2003. Google ScholarDigital Library
- D. A. Bader, S. Kintali, and M. Madduri, K.and Mihail. Approximating betweenness centrality. In WAW'07: Proc. 5th Int'l Conf. Algor. and models for the web-graph, 2007. Google ScholarDigital Library
- H. Bast, S. Funke, P. Sanders, and D. Schultes. Fast Routing in Road Networks with Transit Nodes. Science, 316:566--, April 2007.Google Scholar
- R. Bauer, D. Delling, P. Sanders, D. Schieferdecker, D. Schultes, and D. Wagner. Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm. J. Exp. Algorithmics, 15, March 2010. Google ScholarDigital Library
- U. Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25:163--177, 2001.Google ScholarCross Ref
- J. Cheng and J. X. Yu. On-line exact shortest distance query processing. In EDBT '09, 2009. Google ScholarDigital Library
- Y. J. Chu and T. H. Liu. On the shortest arborescence of a directed graph. Science Sinica, 14:1396--1400, 1965.Google Scholar
- Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. Reachability and distance queries via 2-hop labels. SIAM J. Comput., 32(5):1338--1355, 2003. Google ScholarDigital Library
- Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. McGraw Hill, 1990. Google ScholarDigital Library
- A. Das Sarma, S. Gollapudi, and R. Najork, M.and Panigrahy. A sketch-based distance oracle for web-scale graphs. In WSDM '10, 2010. Google ScholarDigital Library
- D. Delling, P. Sanders, D. Schultes, and D. Wagner. Algorithmics of large and complex networks. chapter Engineering Route Planning Algorithms. 2009. Google ScholarDigital Library
- E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269--271, December 1959.Google ScholarDigital Library
- J. Edmonds. Optimum branchings. J. Research of the National Bureau of Standards, 71B:233--240, 1967.Google ScholarCross Ref
- U. Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634--652, 1998. Google ScholarDigital Library
- C. Gavoille, D. Peleg, S. Pérennes, and R. Raz. Distance labeling in graphs. J. Algorithms, 53(1):85--112, 2004. Google ScholarDigital Library
- Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz. Distance labeling in graphs. J. Algorithms, 53(1):85--112, 2004. Google ScholarDigital Library
- R. Geisberger, P. Sanders, D. Schultes, and D. Delling. Contraction hierarchies: faster and simpler hierarchical routing in road networks. In Proceedings of the 7th international conference on Experimental algorithms, 2008. Google ScholarDigital Library
- A. V. Goldberg and C. Harrelson. Computing the shortest path: A search meets graph theory. In SODA '05, 2005. Google ScholarDigital Library
- A. V. Goldberg, H. Kaplan, and R. F. Werneck. Reach for a*: Efficient point-to-point shortest path algorithms. In IN WORKSHOP ON ALGORITHM ENGINEERING and EXPERIMENTS, pages 129--143, 2006.Google ScholarCross Ref
- R. Goldman, N. Shivakumar, S. Venkatasubramanian, and H. Garcia-Molina. Proximity search in databases. In VLDB '98, 1998. Google ScholarDigital Library
- G. Gou and R. Chirkova. Efficiently querying large xml data repositories: A survey. TKDE, 19(10):1381--1403, 2007. Google ScholarDigital Library
- A. Gubichev, S. Bedathur, S. Seufert, and G. Weikum. Fast and accurate estimation of shortest paths in large graphs. In CIKM '10, 2010. Google ScholarDigital Library
- R. J. Gutman. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In ALENEX/ANALC, pages 100--111, 2004.Google Scholar
- R. Jin, Y. Xiang, N. Ruan, and D. Fuhry. 3-hop: a high compression indexing scheme for reachability query. In SIGMOD'09, 2009. Google ScholarDigital Library
- N. Jing, Y. Huang, and E. A. Rundensteiner. Hierarchical encoded path views for path query processing: An optimal model and its performance evaluation. TKDE, 10(3):409--432, 1998. Google ScholarDigital Library
- S. Jung and S. Pramanik. An efficient path computation model for hierarchically structured topographical road maps. TKDE, 14(5):1029--1046, 2002. Google ScholarDigital Library
- J. Kleinberg, A. Slivkins, and T. Wexler. Triangulation and embedding using small sets of beacons. In FOCS '04, 2004. Google ScholarDigital Library
- H. Kriegel, P. Kröger, M. Renz, and T. Schmidt. Hierarchical graph embedding for efficient query processing in very large traffic networks. In SSDBM '08, 2008. Google ScholarDigital Library
- C. Castillo M. Potamias, F. Bonchi and A. Gionis. Fast shortest path distance estimation in large networks. In CIKM '09, 2009. Google ScholarDigital Library
- T. S. Eugene Ng and H. Zhang. Predicting internet network distance with coordinates-based approaches. In INFOCOM, 2001.Google Scholar
- David P. Proximity-preserving labeling schemes and their applications. Journal of Graph Theory, 33(3):167--176, 2000. Google ScholarDigital Library
- I. Pohl. Bi-directional search. Machine Intelligence, 6:124--140, 1971.Google Scholar
- H. Refael and S. Danny. The set cover with pairs problem. In FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 25th Int'l Conference, 2005. Google ScholarDigital Library
- H. Samet, J. Sankaranarayanan, and H. Alborzi. Scalable network distance browsing in spatial databases. In SIGMOD'08, 2008. Google ScholarDigital Library
- P. Sanders and D. Schultes. Highway hierarchies hasten exact shortest path queries. In 17th Eur. Symp. Algorithms (ESA), 2005. Google ScholarDigital Library
- J. Sankaranarayanan, H. Samet, and H. Alborzi. Path oracles for spatial networks. PVLDB, 2, August 2009. Google ScholarDigital Library
- R. Schenkel, A. Theobald, and G. Weikum. HOPI: An efficient connection index for complex XML document collections. In EDBT, 2004.Google ScholarCross Ref
- S. Shekhar, A. Fetterer, and B. Goyal. Materialization trade offs in hierarchical shortest path algorithms. In SSD '97, 1997. Google ScholarDigital Library
- G. Swamynathan, C. Wilson, B. Boe, K. Almeroth, and B. Y. Zhao. Do social networks improve e-commerce?: a study on social marketplaces. In WOSP '08: Proc. 1st workshop on Online social networks, 2008. Google ScholarDigital Library
- Y. Tao, C. Sheng, and J. Pei. On k-skip shortest paths. In SIGMOD'11, 2011. Google ScholarDigital Library
- M. Thorup and U. Zwick. Approximate distance oracles. J. ACM, 52(1):1--24, 2005. Google ScholarDigital Library
- M. V. Vieira, B. M. Fonseca, R. Damazio, P. B. Golgher, D. de C. Reis, and B. Ribeiro-Neto. Efficient search ranking in social networks. In CIKM '07, 2007. Google ScholarDigital Library
- F. Wei. Tedi: efficient shortest path query answering on graphs. In SIGMOD'10, 2010. Google ScholarDigital Library
Index Terms
- A highway-centric labeling approach for answering distance queries on large sparse graphs
Recommendations
Compression techniques for 2-hop labeling for shortest distance queries
AbstractShortest distance computation is one of the widely researched areas in theoretical computer science and graph databases. Distance labeling are well-known for improving the performance of shortest distance queries. One of the best distance labeling ...
Fault-tolerant distance labeling for planar graphs
AbstractIn fault-tolerant distance labeling we wish to assign short labels to the vertices of a graph G such that from the labels of any three vertices u , v , f we can infer the u-to-v distance in the graph G ∖ { f }. We show that any ...
Highlights- Goal: label the vertices of graph G so that from the labels of any u,v,f we can infer the u-to-v distance in G ∖ { f }.
Hierarchical Cut Labelling - Scaling Up Distance Queries on Road Networks
PACMMODAnswering the shortest-path distance between two arbitrary locations is a fundamental problem in road networks. Labelling-based solutions are the current state-of-the-arts to render fast response time, which can generally be categorised into hub-based ...
Comments