TY - JOUR AU - Akiba, Takuya AU - Hayashi, Takanori AU - Nori, Nozomi AU - Iwata, Yoichi AU - Yoshida, Yuichi PY - 2015/02/09 Y2 - 2024/03/29 TI - Efficient Top-k Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 29 IS - 1 SE - AAAI Technical Track: AI and the Web DO - 10.1609/aaai.v29i1.9154 UR - https://ojs.aaai.org/index.php/AAAI/article/view/9154 SP - AB - <p> 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. </p> ER -