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: 9687
Venue: VLDB
Year: 2006
Pagerank: 6.2058219e-05
Overall Rank: 5,472 | 62.46%
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,150	Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries	2008	VLDB	9.081101e-05
2,302	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.7808696e-05
5,122	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.3573169e-05
12,490	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS	5.093636e-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
104	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033932213
794	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00013969303
1,464	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010689981
1,867	Performance Measurements of Compressed Bitmap Indices	1999	VLDB	9.5903618e-05
1,894	Optimizing Queries On Compressed Bitmaps	2000	VLDB	9.5268052e-05
2,773	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB	8.1382209e-05
3,912	Compressing Large Boolean Matrices Using Reordering Techniques	2004	VLDB	7.0231849e-05
4,656	Query Optimization for Selections using Bitmaps	1999	SIGMOD	6.5834278e-05

Semantically Similar Papers

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