ChainTree and PathTree (TODS) [Improved Version of Path-Tree in SIGMOD'08]
ChainTree and PathTree are the implementation of algorithms for answering reachability query in DAG (directed acyclic graph). The algorithms are discussed in our TODS paper, Path-Tree: An Efficient Reachability Indexing Scheme for Large Directed Graphs. (Note that, this implementation is the improved version of path-tree used in SIGMOD'08 paper, Efficiently Answering Reachability Queries on Very Large Directed Graph)- Code and Datasets: pathtree_TODS
- NEW: this is latest version of pathtree implementation for our SIGMOD and TODS paper. pathtree_v1.1
SCARAB (SIGMOD'12)
SCARAB is a unified reachability computation framework which not only can scale the existing state-of-the-art reachability indices, but also can help speed up the online query answering approaches. The algorithm is presented in our SIGMOD'12 paper, SCARAB: scaling reachability computation on large graphs.- Code: SCARAB
HCL (SIGMOD'12)
Highway-Centric Labeling (HCL) is a novel labeling schema for answering distance queries in a large sparse graph. The algorithm is presented in our SIGMOD'12 paper, A highway-centric labeling approach for answering distance queries on large sparse graphs.- Code: HCL