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.0483079e-05
Overall Rank: 5,614 | 62.37%
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,168	Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries	2008	VLDB	8.9159881e-05
2,337	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.6002736e-05
5,236	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.2037372e-05
12,829	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS	4.9605343e-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.00033376274
776	Bitmap Index Design and Evaluation	1998	SIGMOD	0.0001406101
1,496	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010460047
1,902	Performance Measurements of Compressed Bitmap Indices	1999	VLDB	9.3884754e-05
1,939	Optimizing Queries On Compressed Bitmaps	2000	VLDB	9.3280163e-05
2,810	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB	7.9609074e-05
4,003	Compressing Large Boolean Matrices Using Reordering Techniques	2004	VLDB	6.8465541e-05
4,770	Query Optimization for Selections using Bitmaps	1999	SIGMOD	6.4130719e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,267	Indexing Mixed Types for Approximate Retrieval	2005	VLDB
2	9,981	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	625	Efficiently Supporting Ad Hoc Queries in Large Datasets of Time Sequences	1997	SIGMOD
5	2,017	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD
6	776	Bitmap Index Design and Evaluation	1998	SIGMOD
7	1,939	Optimizing Queries On Compressed Bitmaps	2000	VLDB
8	1,902	Performance Measurements of Compressed Bitmap Indices	1999	VLDB
9	2,810	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB
10	1,496	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD