Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps

Summary: Multi-hash bitmap encoding enables direct access to compressed bitmaps without decompression. It yields approx results with a tunable false-positive rate and guaranteed no misses, delivering 90–100% accuracy and 1–3 orders of magnitude speedups over WAH. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9497
Venue: VLDB
Year: 2006
Pagerank: 5.413565e-05
Overall Rank: 5,605 | 61.05%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,442	Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries	2008	VLDB	8.8067249e-05
2,841	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.0396876e-05
5,541	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	5.4501856e-05
12,303	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
121	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00045429472
1,033	Bitmap Index Design and Evaluation	1998	SIGMOD	0.0001453376
1,701	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010828605
1,955	Performance Measurements of Compressed Bitmap Indices	1999	VLDB	9.9641178e-05
2,065	Optimizing Queries On Compressed Bitmaps	2000	VLDB	9.6467359e-05
2,984	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB	7.7768363e-05
3,918	Compressing Large Boolean Matrices Using Reordering Techniques	2004	VLDB	6.6267457e-05
4,532	Query Optimization for Selections using Bitmaps	1999	SIGMOD	6.1027943e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,775	Indexing Mixed Types for Approximate Retrieval	2005	VLDB	4.6494306e-05
9,633	Compressed Spatial Hierarchical Bitmap (cSHB) Indexes for Efficiently Processing Spatial Range Query Workloads	2015	VLDB	4.309053e-05
1,098	Query Optimization In Compressed Database Systems	2001	SIGMOD	0.00014070252
689	Efficiently Supporting Ad Hoc Queries in Large Datasets of Time Sequences	1997	SIGMOD	0.00018069077
2,821	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	8.0639288e-05
1,033	Bitmap Index Design and Evaluation	1998	SIGMOD	0.0001453376
2,065	Optimizing Queries On Compressed Bitmaps	2000	VLDB	9.6467359e-05
1,955	Performance Measurements of Compressed Bitmap Indices	1999	VLDB	9.9641178e-05
2,984	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB	7.7768363e-05
1,701	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010828605