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
h2bb15a0c15d6b0bf
Venue
SIGMOD
Year
2011
Pagerank
0.00011000029
Overall Rank
1,329 | 91.07%
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,236 Druid: A Real-time Analytical Data Store 2014 SIGMOD 0.00011402848
1,375 Query Preserving Graph Compression 2012 SIGMOD 0.00010877488
1,563 TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013 SIGMOD 0.00010224369
1,849 Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014 SIGMOD 9.5068688e-05
2,563 SCARAB: Scaling Reachability Computation on Large Graphs 2012 SIGMOD 8.2934229e-05
2,604 K-Reach: Who is in Your Small World 2012 VLDB 8.2302549e-05
2,734 Landmark Indexing for Evaluation of Label-Constrained Reachability Queries 2017 SIGMOD 8.0789676e-05
3,348 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 7.3926236e-05
4,049 Reachability Querying: An Independent Permutation Labeling Approach 2014 VLDB 6.8302372e-05
5,000 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 6.3202341e-05
5,717 Microblog Entity Linking with Social Temporal Context 2015 SIGMOD 6.0191048e-05
6,130 Compression of Uncertain Trajectories in Road Networks 2020 VLDB 5.8783975e-05
6,177 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 5.8598586e-05
7,237 Labeling Workflow Views with Fine-Grained Dependencies 2012 VLDB 5.5785819e-05
7,840 DAG Reduction: Fast Answering Reachability Queries 2017 SIGMOD 5.442834e-05
8,789 Distributed Set Reachability 2016 SIGMOD 5.2767294e-05
9,805 I/O Efficient Label-Constrained Reachability Queries in Large Graphs 2024 VLDB 5.1257999e-05
10,247 Top-k Relevant Semantic Place Retrieval on Spatial RDF Data 2016 SIGMOD 5.0525742e-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