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: 9496
Venue: VLDB
Year: 2006
Pagerank: 5.4181535e-05
Overall Rank: 5,596 | 61.08%
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,444	Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries	2008	VLDB	8.8076551e-05
2,837	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.0414149e-05
5,532	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	5.4548897e-05
12,295	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS	4.1945683e-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.00045447517
1,035	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00014532778
1,704	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.000108332
1,951	Performance Measurements of Compressed Bitmap Indices	1999	VLDB	9.9685919e-05
2,061	Optimizing Queries On Compressed Bitmaps	2000	VLDB	9.6529345e-05
2,986	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB	7.778912e-05
3,916	Compressing Large Boolean Matrices Using Reordering Techniques	2004	VLDB	6.6328898e-05
4,528	Query Optimization for Selections using Bitmaps	1999	SIGMOD	6.1083382e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,777	Indexing Mixed Types for Approximate Retrieval	2005	VLDB	4.653704e-05
9,633	Compressed Spatial Hierarchical Bitmap (cSHB) Indexes for Efficiently Processing Spatial Range Query Workloads	2015	VLDB	4.3131863e-05
1,100	Query Optimization In Compressed Database Systems	2001	SIGMOD	0.00014072277
693	Efficiently Supporting Ad Hoc Queries in Large Datasets of Time Sequences	1997	SIGMOD	0.00018077335
2,862	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	7.9898539e-05
1,035	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00014532778
2,061	Optimizing Queries On Compressed Bitmaps	2000	VLDB	9.6529345e-05
1,951	Performance Measurements of Compressed Bitmap Indices	1999	VLDB	9.9685919e-05
2,986	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB	7.778912e-05
1,704	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.000108332