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.4016324e-05
Overall Rank: 4,789 | 67.90%
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
774	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014063511
2,017	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	9.169662e-05
2,891	Optimal Column Layout for Hybrid Workloads	2019	VLDB	7.887378e-05
3,456	Slalom: Coasting Through Raw Data via Adaptive Partitioning and Indexing	2017	VLDB	7.2673968e-05
3,606	Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?	2017	SIGMOD	7.1528863e-05
4,773	Cuckoo Index: A Lightweight Secondary Index Structure	2020	VLDB	6.4102054e-05
4,897	Design Tradeoffs of Data Access Methods	2016	SIGMOD	6.3489205e-05
7,505	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB	5.4920201e-05
8,516	Tree-Encoded Bitmaps	2020	SIGMOD	5.3110731e-05
10,664	RABIT: Efficient Range Queries with Bitmap Indexing	2026	SIGMOD	4.9605343e-05
10,727	LiveBin: A Localized and Version-Aware Binned Scan Index	2026	SIGMOD	4.9605343e-05
10,901	Bridging the Indexing Gap in Fused GPU Query Engines	2026	VLDB	4.9605343e-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.00068985264
107	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033376274
218	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00024342426
289	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00021955394
707	Main-Memory Scan Sharing For Multi-Core CPUs	2008	VLDB	0.00014613324
776	Bitmap Index Design and Evaluation	1998	SIGMOD	0.0001406101
980	Sybase IQ Multiplex – Designed For Analytics	2004	VLDB	0.0001268915
1,149	Bit Transposed Files	1985	VLDB	0.00011771401
1,496	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010460047
1,625	Mesa: Geo-Replicated, Near Real-Time, Scalable Data Warehousing	2014	VLDB	0.00010028153
5,651	MaSM: Efficient Online Updates in Data Warehouses	2011	SIGMOD	6.0346713e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,810	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB
2	1,939	Optimizing Queries On Compressed Bitmaps	2000	VLDB
3	1,902	Performance Measurements of Compressed Bitmap Indices	1999	VLDB
4	1,496	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD
5	5,397	Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices	2023	SIGMOD
6	1,529	Updatable Learned Index with Precise Positions	2021	VLDB
7	776	Bitmap Index Design and Evaluation	1998	SIGMOD
8	5,614	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB
9	10,664	RABIT: Efficient Range Queries with Bitmap Indexing	2026	SIGMOD
10	7,505	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB