jagielkads / brandnewlabeling Goto Github PK

#About Author: Jagsly(Frank) Li

Organization: University of Macau

#Briefing This bunch of code is my implementation of two state-of-the-art 2-hop labeling techniques for all pairs shortest path indexing, PLL and HopDoubling. Details can be found in their papers[1][2]. Also thanks to the two major authors for their codes and slides[3][4][5] which help me great a lot to understand these techniques.

For any one who is interested in this topic of research, I have shared a SODA'02 paper[6] which proposes several theoretical properties of 2-hop indexing.

#References

1. Akiba, Takuya, Yoichi Iwata, and Yuichi Yoshida. "Fast exact shortest-path distance queries on large networks by pruned landmark labeling." Proceedings of the 2013 international conference on Management of data. ACM, 2013.
2. Minhao Jiang, Ada Wai-Chee Fu, Raymond Chi-Wing Wong and Yanyan Xu, "Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks", the 40th International Conference on Very Large Data Bases (VLDB'14), Hangzhou, China on 1-5 Sept, 2014.
3. Takuya Akiba: http://www-imai.is.s.u-tokyo.ac.jp/~takiba/ (i used to get slides in his page but now you have to try emails)
4. https://github.com/iwiwi/pruned-landmark-labeling (takuya's githubpage for pll)
5. Minhao Jiang: http://www.cse.ust.hk/~raywong/ (actually it is his supervisor's homepage, but you can find every sources you need)
6. Cohen, Edith, et al. "Reachability and distance queries via 2-hop labels." SIAM Journal on Computing 32.5 (2003): 1338-1355. APA.