Towards Efficient Shortest Path Counting on Billion-Scale Graphs
Authors:
- 1 April 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2579-2592
Abstract
Shortest path counting computes the number of shortest paths between two vertices on a graph, which can be used in the applications such as social network search and POI (Point of Interest) recommendation. The state-of-the-art approach leverages index to speed up the query processing. However, this approach incurs not only significant space overheads but also prohibitive indexing time, which makes it inapplicable to handle such queries on large graphs. Motivated by this, in this paper, we aim to propose a new solution to scale up the shortest path counting. To achieve this goal, we first propose a novel size-tunable indexing framework, which allows users to tune the index space consumption based on their requirements for query processing efficiency and available memory. Based on the size-tunable indexing framework, we devise a new parallel paradigm to accelerate index construction. We conduct experiments on 15 real graphs and the experimental results demonstrate that our new approach significantly outperforms the state-of-the-art approach regarding the index space cost and index construction cost, and is able to handle billion-scale graphs that the state-of-the-art approach cannot process with less than 5 milliseconds query processing time on all test cases.Keywords
Funding Information
- Engineering Laboratory
This publication has 57 references indexed in Scilit:
- Estimating the Number of s-t Paths in a GraphJournal of Graph Algorithms and Applications, 2007
- Betweenness centrality in large complex networksThe European Physical Journal B, 2004
- An efficient path computation model for hierarchically structured topographical road mapsIEEE Transactions on Knowledge and Data Engineering, 2002
- Treewidth: Computational ExperimentsElectronic Notes in Discrete Mathematics, 2001
- Counting trees in a graph is #P-completeInformation Processing Letters, 1994
- Technical reportOil and Chemical Pollution, 1987
- Complexity of Finding Embeddings in a k-TreeSIAM Journal on Algebraic Discrete Methods, 1987
- Graph minors. III. Planar tree-widthJournal of Combinatorial Theory, Series B, 1984
- The Complexity of Enumeration and Reliability ProblemsSIAM Journal on Computing, 1979
- A note on two problems in connexion with graphsNumerische Mathematik, 1959