UpBit: Scalable In-Memory Updatable Bitmap Indexing

Summary: UpBit delivers scalable, in-memory updatable bitmap indexing with a main bitvector and a sparse update bitvector. Fence pointers in update bitvectors enable fast access; 15–29x faster updates and competitive reads vs update- and read-optimized baselines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5342
Venue: SIGMOD
Year: 2016
Pagerank: 6.4107392e-05
Overall Rank: 4,988 | 65.78%
DOI: 10.1145/2882903.2915964

Incoming Non-self Citations Over Time

Authors

1. Manos Athanassoulis (Harvard University)
2. Zheng Yan (Harvard University; University of Maryland)
3. Stratos Idreos (Harvard University)

BibTeX Citation

@inproceedings{athanassoulis_sigmod16,
        title = {{UpBit: Scalable In-Memory Updatable Bitmap Indexing}},
        author = {Athanassoulis, Manos and Yan, Zheng and Idreos, Stratos},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2915964},
        url = {https://dl.acm.org/doi/10.1145/2882903.2915964},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
790	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.0001401445
2,224	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	8.9183396e-05
2,866	Optimal Column Layout for Hybrid Workloads	2019	VLDB	8.0175489e-05
3,413	Slalom: Coasting Through Raw Data via Adaptive Partitioning and Indexing	2017	VLDB	7.4326381e-05
3,598	Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?	2017	SIGMOD	7.2718988e-05
4,782	Cuckoo Index: A Lightweight Secondary Index Structure	2020	VLDB	6.5115802e-05
4,826	Design Tradeoffs of Data Access Methods	2016	SIGMOD	6.4904836e-05
7,960	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB	5.5181056e-05
8,349	Tree-Encoded Bitmaps	2020	SIGMOD	5.4460774e-05
10,395	RABIT: Efficient Range Queries with Bitmap Indexing	2026	SIGMOD	5.093636e-05
10,468	LiveBin: A Localized and Version-Aware Binned Scan Index	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
12	C-Store: A Column-oriented DBMS	2005	VLDB	0.00069513174
104	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033932213
216	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00024498128
293	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00022259273
696	Main-Memory Scan Sharing For Multi-Core CPUs	2008	VLDB	0.00014891322
794	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00013969303
970	Sybase IQ Multiplex – Designed For Analytics	2004	VLDB	0.00012882125
1,136	Bit Transposed Files	1985	VLDB	0.00012027691
1,464	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010689981
1,606	Mesa: Geo-Replicated, Near Real-Time, Scalable Data Warehousing	2014	VLDB	0.00010228576
5,564	MaSM: Efficient Online Updates in Data Warehouses	2011	SIGMOD	6.1716245e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,773	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB
2	1,894	Optimizing Queries On Compressed Bitmaps	2000	VLDB
3	1,867	Performance Measurements of Compressed Bitmap Indices	1999	VLDB
4	1,464	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD
5	5,423	Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices	2023	SIGMOD
6	1,551	Updatable Learned Index with Precise Positions	2021	VLDB
7	794	Bitmap Index Design and Evaluation	1998	SIGMOD
8	5,472	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB
9	10,395	RABIT: Efficient Range Queries with Bitmap Indexing	2026	SIGMOD
10	7,960	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB