James Cheng
ABSTRACT
We propose a novel disk-based index for processing single-source shortest path or distance queries. The index is useful in a wide range of important applications (e.g., network analysis, routing planning, etc.). Our index is a tree-structured index constructed based on the concept of vertex cover. We propose an I/O-efficient algorithm to construct the index when the input graph is too large to fit in main memory. We give detailed analysis of I/O and CPU complexity for both index construction and query processing, and verify the efficiency of our index for query processing in massive real-world graphs.
- I. Abraham, A. Fiat, A. V. Goldberg, and R. F. F. Werneck. Highway dimension, shortest paths, and provably efficient algorithms. In SODA, pages 782--793, 2010. Google Scholar
Digital Library
- A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems. Commun. ACM, 31(9):1116--1127, 1988. Google ScholarDigital Library
- D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput., 28(4):1167--1181, 1999. Google ScholarDigital Library
- D. Ajwani, R. Dementiev, and U. Meyer. A computational study of external-memory BFS algorithms. In SODA, pages 601--610, 2006. Google ScholarDigital Library
- D. Ajwani, U. Meyer, and V. Osipov. Improved external memory bfs implementation. In ALENEX, 2007.Google ScholarCross Ref
- A. L. Buchsbaum, M. H. Goldwasser, S. Venkatasubramanian, and J. Westbrook. On external memory graph traversal. In SODA, pages 859--860, 2000. Google ScholarDigital Library
- J. Cheng, Y. Ke, A. W.-C. Fu, J. X. Yu, and L. Zhu. Finding maximal cliques in massive networks by h*-graph. In SIGMOD Conference, pages 447--458, 2010. Google ScholarDigital Library
- T. R. Coffman and S. E. Marcus. Dynamic classification of groups through social network analysis and HMMs. In IEEE Aerospace Conference, pages 3197--3205, 2004.Google ScholarCross Ref
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Second Edition. The MIT Press and McGraw-Hill Book Company, 2001. Google ScholarDigital Library
- E. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269?71, 1959.Google ScholarDigital Library
- J. Edmonds and R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2):248--264, 1972. Google ScholarDigital Library
- D. Eppstein and J. Wang. Fast approximation of centrality. In SODA, pages 228--229, 2001. Google ScholarDigital Library
- M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the internet topology. In SIGCOMM, pages 251--262, 1999. Google ScholarDigital Library
- L. Ford and D. R. Fulkerson. Maximum flow through a network. Canadian Journal of Mathematics, 8(3):399--404, 1956.Google ScholarCross Ref
- L. C. Freeman. A set of measures of centrality based on betweenness. Sociometry, 40(1):35?1, 1977.Google ScholarCross Ref
- J. E. Hopcroft and R. M. Karp. An $n^5/2$ algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4):225--231, 1973.Google ScholarCross Ref
- V. Kumar and E. J. Schwabe. Improved algorithms and data structures for solving graph problems in external memory. In In Proc. IEEE Symp. on Parallel and Distributed Processing, pages 169--177, 1996. Google ScholarDigital Library
- K. Mehlhorn and U. Meyer. External-memory breadth-first search with sublinear I/O. In ESA, pages 723--735, 2002. Google ScholarDigital Library
- U. Meyer. Via detours to I/O-efficient shortest paths. In Efficient Algorithms, pages 219--232, 2009. Google ScholarDigital Library
- U. Meyer and V. Osipov. Design and implementation of a practical i/o-efficient shortest paths algorithm. In ALENEX, pages 85--96, 2009.Google ScholarCross Ref
- U. Meyer and N. Zeh. I/O-efficient undirected shortest paths. In ESA, pages 434--445. Springer-Verlag, 2003.Google ScholarCross Ref
- U. Meyer and N. Zeh. I/O-efficient undirected shortest paths with unbounded edge lengths. In ESA, pages 540--551, 2006. Google ScholarDigital Library
- S. Micali and V. V. Vazirani. An $O(|E| \sqrt|V|)$ algoithm for finding maximum matching in general graphs. In FOCS, pages 17--27, 1980. Google ScholarDigital Library
- K. Munagala and A. G. Ranade. I/o-complexity of graph algorithms. In SODA, pages 687--694, 1999. Google ScholarDigital Library
- M. Najork and J. L. Wiener. Breadth-first crawling yields high-quality pages. In WWW, pages 114--118, 2001. Google ScholarDigital Library
- A. Shimbel. Structural parameters of communication networks. Mathematical Biophysics, 15:501?07, 1953.Google ScholarCross Ref
- B. E. Thomason, T. R. Coffman, and S. E. Marcus. Sensitivity of social network analysis metrics to observation noise. In IEEE Aerospace Conference, pages 3206--3216, 2004.Google ScholarCross Ref
- J. S. Turner. Approximation algorithms for the shortest common superstring problem. Information and Computation, 83(1):1 -- 20, 1989. Google ScholarDigital Library
- T. W. Valente and R. K. Foreman. Integration and radiality: Measuring the extent of an individual's connectedness and reachability in a network. Social Networks, 20(1):89--105, 1998.Google ScholarCross Ref
- F. Wei. TEDI: efficient shortest path query answering on graphs. In SIGMOD Conference, pages 99--110, 2010. Google ScholarDigital Library
- Y. Xiao, W. Wu, J. Pei, W. Wang, and Z. He. Efficiently indexing shortest paths by exploiting symmetry in graphs. In EDBT, pages 493--504, 2009. Google ScholarDigital Library
Index Terms
- Efficient processing of distance queries in large graphs: a vertex cover approach
Recommendations
Efficient single-source shortest path and distance queries on large graphs
KDD '13: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data miningThis paper investigates two types of graph queries: single source distance (SSD) queries and single source shortest path (SSSP) queries. Given a node v in a graph G, an SSD query from v asks for the distance from $v$ to any other node in G, while an ...
The Vantage Index: Executing Distance Queries at Scale
SSDBM '20: Proceedings of the 32nd International Conference on Scientific and Statistical Database ManagementDue to the proliferation of GPS-enabled devices, vast amounts of trajectory datasets are being collected every day. Analyzing this data efficiently and at scale is a major challenge. Several different types of spatio-temporal queries are used to analyze ...
Packing chromatic number of distance graphs
The packing chromatic number ( G ) of a graph G is the smallest integer k such that vertices of G can be partitioned into disjoint classes X 1 , , X k where vertices in X i have pairwise distance greater than i . We study the packing chromatic number of ...
Comments