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: h7cff4d73e6e1832f
Venue: SIGMOD
Year: 2016
Pagerank: 6.4050834e-05
Overall Rank: 4,810 | 67.67%
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 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
779	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014030069
2,201	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	8.8726671e-05
2,882	Optimal Column Layout for Hybrid Workloads	2019	VLDB	7.9116043e-05
3,445	Slalom: Coasting Through Raw Data via Adaptive Partitioning and Indexing	2017	VLDB	7.2943981e-05
3,599	Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?	2017	SIGMOD	7.1773938e-05
4,756	Cuckoo Index: A Lightweight Secondary Index Structure	2020	VLDB	6.43221e-05
4,885	Design Tradeoffs of Data Access Methods	2016	SIGMOD	6.3706825e-05
7,481	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB	5.5128501e-05
8,500	Tree-Encoded Bitmaps	2020	SIGMOD	5.3296886e-05
10,591	RABIT: Efficient Range Queries with Bitmap Indexing	2026	SIGMOD	4.9793485e-05
10,655	LiveBin: A Localized and Version-Aware Binned Scan Index	2026	SIGMOD	4.9793485e-05
10,830	Bridging the Indexing Gap in Fused GPU Query Engines	2026	VLDB	4.9793485e-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.00068998927
107	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033460288
219	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00024363532
287	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00021970198
705	Main-Memory Scan Sharing For Multi-Core CPUs	2008	VLDB	0.00014657491
773	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00014084831
980	Sybase IQ Multiplex – Designed For Analytics	2004	VLDB	0.00012720677
1,151	Bit Transposed Files	1985	VLDB	0.00011808563
1,497	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010478458
1,622	Mesa: Geo-Replicated, Near Real-Time, Scalable Data Warehousing	2014	VLDB	0.00010051462
5,637	MaSM: Efficient Online Updates in Data Warehouses	2011	SIGMOD	6.0569403e-05

Semantically Similar Papers

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