Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps

Summary: Introduces a multiply hashed bitmap encoding that supports direct, selective access without decompression. It trades space for controllable approximation: no false negatives, estimable false positives, and 1–3 orders-of-magnitude faster queries than WAH. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h03226cd9fb485a43
Venue: VLDB
Year: 2006
Pagerank: 6.0709132e-05
Overall Rank: 5,600 | 62.35%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Tan Apaydin (Ohio State University)
2. Hakan Ferhatosmanoglu (Ohio State University)
3. Guadalupe Canahuate (Ohio State University)
4. Ali Şaman Tosun (University of Texas at San Antonio)

BibTeX Citation

@article{apaydin_vldb06,
        title = {{Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps}},
        author = {Apaydin, Tan and Ferhatosmanoglu, Hakan and Canahuate, Guadalupe and Tosun, Ali Şaman},
        journal = {PVLDB},
        series = {{VLDB} '06},
        pages = {846--857},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,155	Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries	2008	VLDB	8.9456729e-05
2,329	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.6292256e-05
5,213	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.2250048e-05
12,780	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS	4.9793485e-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
107	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033460288
773	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00014084831
1,497	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010478458
1,896	Performance Measurements of Compressed Bitmap Indices	1999	VLDB	9.4099587e-05
1,930	Optimizing Queries On Compressed Bitmaps	2000	VLDB	9.351027e-05
2,819	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB	7.9715832e-05
3,987	Compressing Large Boolean Matrices Using Reordering Techniques	2004	VLDB	6.8721548e-05
4,748	Query Optimization for Selections using Bitmaps	1999	SIGMOD	6.4371799e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,245	Indexing Mixed Types for Approximate Retrieval	2005	VLDB
2	9,941	Compressed Spatial Hierarchical Bitmap (cSHB) Indexes for Efficiently Processing Spatial Range Query Workloads	2015	VLDB
3	900	Query Optimization In Compressed Database Systems	2001	SIGMOD
4	621	Efficiently Supporting Ad Hoc Queries in Large Datasets of Time Sequences	1997	SIGMOD
5	2,201	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD
6	773	Bitmap Index Design and Evaluation	1998	SIGMOD
7	1,930	Optimizing Queries On Compressed Bitmaps	2000	VLDB
8	1,896	Performance Measurements of Compressed Bitmap Indices	1999	VLDB
9	2,819	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB
10	1,497	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD