On-line exact shortest distance query processing

ABSTRACT

Shortest-path query processing not only serves as a long established routine for numerous applications in the past but also is of increasing popularity to support novel graph applications in very large databases nowadays. For a large graph, there is the new scenario to query intensively against arbitrary nodes, asking to quickly return node distance or even shortest paths. And traditional main memory algorithms and shortest paths materialization become inadequate. We are interested in graph labelings to encode the underlying graphs and assign labels to nodes to support efficient query processing. Surprisingly, the existing work of this category mainly emphasizes on reachability query processing, while no sufficient effort has been given to distance labelings to support querying exact shortest distances between nodes. Distance labelings must be developed on the graph in whole to correctly retain node distance information. It makes many existing methods to be inapplicable. We focus on fast computing distance-aware 2-hop covers, which can encode the all-pairs shortest paths of a graph in O(|V|·|E|^1/2) space. Our approach exploits strongly connected components collapsing and graph partitioning to gain speed, while it can overcome the challenges in correctly retaining node distance information and appropriately encoding all-pairs shortest paths with small overhead. Furthermore, our approach avoids pre-computing all-pairs shortest paths, which can be prohibitive over large graphs. We conducted extensive performance studies, and confirm the efficiency of our proposed new approaches.

REFERENCES

• 1: R. Agrawal , A. Borgida , H. V. Jagadish, Efficient management of transitive relationships in large data and knowledge bases, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.253-262, June 1989, Portland, Oregon, United States
• 2: R. Agrawal , H. V. Jagadish, Algorithms for Searching Massive Graphs, IEEE Transactions on Knowledge and Data Engineering, v.6 n.2, p.225-238, April 1994 [doi>10.1109/69.277767]
• 3: Lars Backstrom , Dan Huttenlocher , Jon Kleinberg , Xiangyang Lan, Group formation in large social networks: membership, growth, and evolution, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150412]
• 4: R. Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87--90, 1958.
• 5: Ramadhana Bramandia , Byron Choi , Wee Keong Ng, On incremental maintenance of 2-hop labeling of graphs, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367611]
• 6: Li Chen , Amarnath Gupta , M. Erdem Kurul, Stack-based algorithms for pattern matching on DAGs, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 7: J. Cheng, J. X. Yu, X. Lin, H. Wang, and P. S. Yu. Fast computation of reachability labeling for large graphs. In Proc. of EDBT'06, 2006.
• 8: Jiefeng Cheng , Jeffrey Xu Yu , Xuemin Lin , Haixun Wang , Philip S. Yu, Fast computing reachability labelings for large graphs with high compression rate, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353370]
• 9: Edith Cohen , Eran Halperin , Haim Kaplan , Uri Zwick, Reachability and distance queries via 2-hop labels, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.937-946, January 06-08, 2002, San Francisco, California
• 10: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 11: F. Dabek, R. Cox, F. Kaashoek, and R. Morris. Predicting internet network distance with coordinates-based approaches. In Proc. of SIGCOMM '04, 2004.
• 12: E. W. Dijkstra. A note on two problems in connection with graphs. Numerische Math., 1:269--271, 1959.
• 13: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 14: Cyril Gavoille , David Peleg , Stéphane Pérennes , Ran Raz, Distance labeling in graphs, Journal of Algorithms, v.53 n.1, p.85-112, October 2004 [doi>10.1016/j.jalgor.2004.05.002]
• 15: A. V. Goldberg and R. F. Werneck. Computing point-to-point shortest paths from external memory. In Proc. of ALENEX '05, 2005.
• 16: A. V. Goldberg and R. F. Werneck. Reach for a*: Efficient point-to-point shortest path algorithms. In Proc. of ALENEX '06, 2006.
• 17: Gang Gou , Rada Chirkova, Efficient algorithms for exact ranked twig-pattern matching over graphs, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376676]
• 18: Hao He , Haixun Wang , Jun Yang , Philip S. Yu, BLINKS: ranked keyword searches on graphs, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247516]
• 19: H. V. Jagadish, A compression technique to materialize transitive closure, ACM Transactions on Database Systems (TODS), v.15 n.4, p.558-598, Dec. 1990 [doi>10.1145/99935.99944]
• 20: Ruoming Jin , Yang Xiang , Ning Ruan , Haixun Wang, Efficiently answering reachability queries on very large directed graphs, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376677]
• 21: Ning Jing , Yun-Wu Huang , Elke A. Rundensteiner, Hierarchical Encoded Path Views for Path Query Processing: An Optimal Model and Its Performance Evaluation, IEEE Transactions on Knowledge and Data Engineering, v.10 n.3, p.409-432, May 1998 [doi>10.1109/69.687976]
• 22: D. B. Johnson. Finding all the elementary circuits of a directed graph. SIAM J. Comput., 4(1):77--84, 1975.
• 23: David S. Johnson, Approximation algorithms for combinatorial problems, Proceedings of the fifth annual ACM symposium on Theory of computing, p.38-49, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804034]
• 24: Richard Johnsonbaugh , Martin Kalin, A graph generation software package, Proceedings of the twenty-second SIGCSE technical symposium on Computer science education, p.151-154, March 07-08, 1991, San Antonio, Texas, United States
• 25: Sungwon Jung , Sakti Pramanik, An Efficient Path Computation Model for Hierarchically Structured Topographical Road Maps, IEEE Transactions on Knowledge and Data Engineering, v.14 n.5, p.1029-1046, September 2002 [doi>10.1109/TKDE.2002.1033772]
• 26: David Kempe , Jon Kleinberg , Éva Tardos, Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956769]
• 27: I. M. Keseler, J. Collado-Vides, S. Gama-Castro, J. Ingraham, S. Paley, I. T. Paulsen, M. Peralta-Gil, and P. D. Karp. Ecocyc: a comprehensive database resource for escherichia coli. Nucleic Acids Research, 33(D334-7), 2005.
• 28: Donald E. Knuth, The Stanford GraphBase: a platform for combinatorial computing, ACM, New York, NY, 1993
• 29: T. S. E. Ng and H. Zhang. Predicting internet network distance with coordiantes-based approaches. In Proc. of INFOCOM '01, 2001.
• 30: David Peleg, Proximity-preserving labeling schemes, Journal of Graph Theory, v.33 n.3, p.167-176, March 2000 [doi>10.1002/(SICI)1097-0118(200003)33:3<>1.0.CO;2-Y]
• 31: Seth Pettie , Vijaya Ramachandran, On the shortest path and minimum spanning tree problems, The University of Texas at Austin, 2003
• 32: S. A. Rahman , P. Advani , R. Schunk , R. Schrader , Dietmar Schomburg, Metabolic pathway analysis web service (Pathway Hunter Tool at CUBIC), Bioinformatics, v.21 n.7, p.1189-1193, April 2005 [doi>10.1093/bioinformatics/bti116]
• 33: R. Schenkel, A. Theobald, and G. Weikum. Hopi: An efficient connection index for complex XML document collections. In Proc. of EDBT'04, 2004.
• 34: Ralf Schenkel , Anja Theobald , Gerhard Weikum, Efficient Creation and Incremental Maintenance of the HOPI Index for Complex XML Document Collections, Proceedings of the 21st International Conference on Data Engineering, p.360-371, April 05-08, 2005 [doi>10.1109/ICDE.2005.57]
• 35: Albrecht Schmidt , Florian Waas , Martin Kersten , Michael J. Carey , Ioana Manolescu , Ralph Busse, XMark: a benchmark for XML data management, Proceedings of the 28th international conference on Very Large Data Bases, p.974-985, August 20-23, 2002, Hong Kong, China
• 36: R. E. Tarjan. Enumeration of the elementary circuits of a directed graph. SIAM J. Comput., 2(3):211--216, 1973.
• 37: Mikkel Thorup , Uri Zwick, Approximate distance oracles, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.183-192, July 2001, Hersonissos, Greece [doi>10.1145/380752.380798]
• 38: Silke Trißl , Ulf Leser, Fast and practical indexing and querying of very large graphs, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247573]
• 39: Haixun Wang , Hao He2 , Jun Yang , Philip S. Yu , Jeffrey Xu Yu, Dual Labeling: Answering Graph Reachability Queries in Constant Time, Proceedings of the 22nd International Conference on Data Engineering, p.75, April 03-07, 2006 [doi>10.1109/ICDE.2006.53]
• 40: S. Wasserman and K. Faust. Social Network Analysis. Cambridge University Press, 1994.
• 41: Raphael Yuster , Uri Zwick, Answering distance queries in directed graphs using fast matrix multiplication, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.389-396, October 23-25, 2005 [doi>10.1109/SFCS.2005.20]
• 42: All pairs shortest paths using bridging sets and rectangular matrix multiplication, Journal of the ACM (JACM), v.49 n.3, p.289-317, May 2002 [doi>10.1145/567112.567114]