Efficient Top-K Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling
Abstract
We propose an indexing scheme for top-k shortest-path distance queries on graphs, which is useful in a wide range of important applications such as network-aware search and link prediction. While considerable effort has been made for efficiently answering standard (top-1) distance queries, none of previous methods can be directly extended for top-k distance queries. We propose a new framework for top-k distance queries based on 2-hop cover and then present an efficient indexing algorithm based on the simple but effective recent notion of pruned landmark labeling. Extensive experimental results on real social and web graphs show the scalability, efficiency and robustness of our method. Moreover, we demonstrate the usefulness of top-k distance queries through an application to link prediction.
Cite
Text
Akiba et al. "Efficient Top-K Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling." AAAI Conference on Artificial Intelligence, 2015. doi:10.1609/AAAI.V29I1.9154Markdown
[Akiba et al. "Efficient Top-K Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling." AAAI Conference on Artificial Intelligence, 2015.](https://mlanthology.org/aaai/2015/akiba2015aaai-efficient/) doi:10.1609/AAAI.V29I1.9154BibTeX
@inproceedings{akiba2015aaai-efficient,
title = {{Efficient Top-K Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling}},
author = {Akiba, Takuya and Hayashi, Takanori and Nori, Nozomi and Iwata, Yoichi and Yoshida, Yuichi},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2015},
pages = {2-8},
doi = {10.1609/AAAI.V29I1.9154},
url = {https://mlanthology.org/aaai/2015/akiba2015aaai-efficient/}
}