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: 4442
Venue: SIGMOD
Year: 2011
Pagerank: 0.00011402871
Overall Rank: 1,553 | 89.20%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Sebastiaan J. van Schaik
2. Oege de Moor

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,579	Query Preserving Graph Compression	2012	SIGMOD	0.00011283792
1,588	Druid: A Real-time Analytical Data Store	2014	SIGMOD	0.00011239313
1,777	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.00010589591
1,880	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010226347
2,756	K-Reach: Who is in Your Small World	2012	VLDB	8.1682536e-05
3,127	SCARAB: Scaling Reachability Computation on Large Graphs	2012	SIGMOD	7.5046522e-05
3,213	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	7.3669794e-05
3,671	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	6.8560247e-05
4,478	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.1506256e-05
5,479	Microblog Entity Linking with Social Temporal Context	2015	SIGMOD	5.4850984e-05
5,540	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	5.4498271e-05
6,004	Compression of Uncertain Trajectories in Road Networks	2020	VLDB	5.2415551e-05
6,533	Labeling Workflow Views with Fine-Grained Dependencies	2012	VLDB	5.0245193e-05
6,795	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9242446e-05
7,596	DAG Reduction: Fast Answering Reachability Queries	2017	SIGMOD	4.7016964e-05
8,669	Distributed Set Reachability	2016	SIGMOD	4.4718257e-05
9,483	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3341665e-05
9,898	Top-k Relevant Semantic Place Retrieval on Spatial RDF Data	2016	SIGMOD	4.2600049e-05

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.

Rank	Cited Paper	Year	Venue	Pagerank
246	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00030949575
279	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029113513
788	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016650034
815	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB	0.00016369666

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,777	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.00010589591
10,161	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD	4.1945683e-05
880	Efficient Transitive Closure Algorithms	1988	VLDB	0.00015667998
7,596	DAG Reduction: Fast Answering Reachability Queries	2017	SIGMOD	4.7016964e-05
9,483	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3341665e-05
246	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00030949575
788	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016650034
5,492	Mixed-Approach Algorithms for Transitive Closure	1991	PODS	5.4771871e-05
1,579	Query Preserving Graph Compression	2012	SIGMOD	0.00011283792
279	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029113513