DBScholar

Back to papers

A Memory Efficient Reachability Data Structure Through Bit Vector Compression

Summary: Memory-efficient reachability data structure for transitive closure using a novel bit-vector compression based on WAH with word partitions to exploit clustering of reachable vertices. Demonstrates tighter compactness than interval lists, fast membership tests, and scalability to graphs far larger than prior methods (Path-Tree/3-HOP) in experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
4504
Venue
SIGMOD
Year
2011
Pagerank
0.00011255351
Overall Rank
1,301 | 91.08%
DOI
10.1145/1989323.1989419

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{schaik_sigmod11,
        title = {{A Memory Efficient Reachability Data Structure Through Bit Vector Compression}},
        author = {van Schaik, Sebastiaan J. and de Moor, Oege},
        series = {{SIGMOD} '11},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1989323.1989419},
        url = {https://dl.acm.org/doi/10.1145/1989323.1989419},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank Citing Paper Year Venue Pagerank
1,242 Druid: A Real-time Analytical Data Store 2014 SIGMOD 0.00011516162
1,336 Query Preserving Graph Compression 2012 SIGMOD 0.00011118804
1,533 TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013 SIGMOD 0.00010467148
1,796 Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014 SIGMOD 9.7380494e-05
2,575 K-Reach: Who is in Your Small World 2012 VLDB 8.3982298e-05
2,700 Landmark Indexing for Evaluation of Label-Constrained Reachability Queries 2017 SIGMOD 8.2411888e-05
3,021 SCARAB: Scaling Reachability Computation on Large Graphs 2012 SIGMOD 7.8401031e-05
3,278 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 7.5712342e-05
3,979 Reachability Querying: An Independent Permutation Labeling Approach 2014 VLDB 6.9754185e-05
5,044 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 6.3883109e-05
5,590 Microblog Entity Linking with Social Temporal Context 2015 SIGMOD 6.1557283e-05
6,002 Compression of Uncertain Trajectories in Road Networks 2020 VLDB 6.0133202e-05
6,603 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 5.824568e-05
7,089 Labeling Workflow Views with Fine-Grained Dependencies 2012 VLDB 5.7066232e-05
7,707 DAG Reduction: Fast Answering Reachability Queries 2017 SIGMOD 5.5636745e-05
8,651 Distributed Set Reachability 2016 SIGMOD 5.3916003e-05
9,625 I/O Efficient Label-Constrained Reachability Queries in Large Graphs 2024 VLDB 5.2434488e-05
10,052 Top-k Relevant Semantic Place Retrieval on Spatial RDF Data 2016 SIGMOD 5.1685424e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Previous Page 1 / 1 Next

Semantically Similar Papers