Please use this identifier to cite or link to this item:
Title: An experimental study on hub labeling based shortest path algorithms
Authors: Li, Y
Hou, UL
Yiu, ML 
Kou, NM
Issue Date: 2017
Publisher: Association for Computing Machinery
Source: Proceedings of the VLDB Endowment, Dec. 2017, v. 11, no. 4, p. 445-457 How to cite?
Journal: Proceedings of the VLDB Endowment 
Abstract: Shortest path distance retrieval is a core component in many important applications. For a decade, hub labeling (HL) techniques have been considered as a practical solution with fast query response time (e.g., 1-3 orders of magnitude faster), competitive indexing time, and slightly larger storage overhead (e.g., several times larger). These techniques enhance query throughput up to hundred thousands queries per second, which is particularly helpful in large user environment. Despite the importance of HL techniques, we are not aware of any comprehensive experimental study on HL techniques. Thus it is difficult for a practitioner to adopt HL techniques for her applications. To address the above issues, we provide a comprehensive experimental study on the state-of-the-art HL technique with analysis of their efficiency, effectiveness and applicability. From insightful summary of different HL techniques, we further develop a simple yet effective HL techniques called Significant path based Hub Pushing (SHP) which greatly improves indexing time of previous techniques while retains good query performance. We also complement extensive comparisons between HL techniques and other shortest path solutions to demonstrate robustness and efficiency of HL techniques.
ISSN: 2150-8097
DOI: 10.1145/3164135.3164141
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

Citations as of Dec 17, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.