This is the implementation of paper Planting Trees for scalable and efficient Canonical Hub Labeling. The codes are developed by Qing Dong and Kartik Lakhotia. We provide efficient Canonical Hub Labeling algorithms on both shared-memory and distributed-memory platform. Please go to the corresponding folder to see detailed introduction and instructions for each algorithm. All implementations take two inputs, one is the graph file (graph topology, in DIMACS, METIS, SNAP or edgelist format) and the other one is the ranking function (a total ordering on all vertices).
- In shared memory platform (shared_memory), Global Local Labeling
- In distributed platform (distributed_memory), Hybrid algorithm of plant and Distributed GLL
We provided four datasets for testing. They are as following. Please go to corrsponding folder to see running instructions for each algorithm.
- AUT (coAuther network)
- CAL (California road network)
- WND (University of Notre Dame webpages)
- YTB (Youtube social network)
We also used some other datasets for testing. We do not push them on github because file size limit. They can be found by clicking the links below.
- EAS (Eastern USA road network)
- CTR (Central USA road network)
- USA (Full USA road network)
- SKIT (Skitter Autonomous Systems)
- ACT (Actor Collaboration Network)
- BDU (Baidu HyperLink Network)
- POK (Social network Pokec)
- LIJ (Live Journal Social Network)
We used betweeness-based ordering for road networks and degree-based ordering for scale-free networks.
Some basic functions in our code are based on the implementation given in savrus's code