IEEE Transactions on Knowledge and Data Engineering · 2011 · 11 citations · 27 references
ComputingComputer ScienceAlgorithmsComputational GeometryOptimizationGraph AlgorithmsGraph AnalyticsGraph MiningShortest Path AlgorithmsConstrained Shortest PathsJoin OperationsPath GenerationSearch Space PruningShortest Paths
Motivated by the needs such as group relationship analysis, this paper introduces a new operation on graphs, named top-k path join, which discovers the top-k simple shortest paths between two given node sets. Rather than discovering the top-k simple paths between each node pair, this paper proposes a holistic join method which answers the top-k path join by finding constrained top-k simple shortest paths between two nodes, and then devises an efficient method to handle the latter problem. Specifically, we transform the graph by encoding the precomputed shortest paths to the target node, and use the transformed graph in the candidate path searching. We show that the candidate path searching on the transformed graph not only has the same result as that on the original graph but also can be terminated much earlier with the aid of precomputed results. We also discuss two other optimization strategies, including considering the join constraint in the candidate path generation as early as possible, and pruning search space in each candidate path generation with an adaptively determined threshold. The final extensive experimental results also show that our method offers a significant performance improvement over existing ones.
27
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Finding the <i>K</i> Shortest Loopless Paths in a Network
Jin Y. Yen · Management Science · 1971 · 2.6K citations
Storing and querying ordered XML using a relational database system
Igor Tatarinov, Stratis D. Viglas, Kevin Beyer et al. · 2002 · 2.3K citations
David Eppstein · SIAM Journal on Computing · 1998 · 1.4K citations