BinDex: A Two-Layered Index for Fast and Robust Scans

Summary: BinDex is a two-layer in-memory index using binned bitmaps to filter data. By tuning the first-layer bitmaps, it trades memory for speed, surpassing prior work with less memory than a B+-tree and up to 2.9x faster scans, removing the scan-type choice. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hac62a700dae0cff2
Venue: SIGMOD
Year: 2020
Pagerank: 6.0630987e-05
Overall Rank: 5,618 | 62.23%
DOI: 10.1145/3318464.3380563

Incoming Non-self Citations Over Time

Authors

1. Linwei Li (Fudan University)
2. Kai Zhang (Fudan University)
3. Jiading Guo (Fudan University)
4. Wen He (Fudan University)
5. Zhenying He (Fudan University)
6. Yinan Jing (Fudan University)
7. Weili Han (Fudan University)
8. X. Sean Wang (Fudan University)

BibTeX Citation

@inproceedings{li_sigmod20,
        title = {{BinDex: A Two-Layered Index for Fast and Robust Scans}},
        author = {Li, Linwei and Zhang, Kai and Guo, Jiading and He, Wen and He, Zhenying and Jing, Yinan and Han, Weili and Wang, X. Sean},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3380563},
        url = {https://dl.acm.org/doi/10.1145/3318464.3380563},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,240	Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses	2024	SIGMOD	5.8382355e-05
6,444	RTScan: Efficient Scan with Ray Tracing Cores	2024	VLDB	5.7825648e-05
7,481	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB	5.5128501e-05
8,533	Cabin: a Compressed Adaptive Binned Scan Index	2024	SIGMOD	5.3215439e-05
9,741	LES3: Learning-based Exact Set Similarity Search	2021	VLDB	5.1349531e-05
10,348	Raster is Faster: Rethinking Ray Tracing in Database Indexing	2026	CIDR	4.9793485e-05
10,591	RABIT: Efficient Range Queries with Bitmap Indexing	2026	SIGMOD	4.9793485e-05
10,937	RayDB: Building Databases with Ray Tracing Cores	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 28 of 28 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023947656
12	C-Store: A Column-oriented DBMS	2005	VLDB	0.00068998927
27	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.0005158963
61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.000392237
107	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033460288
216	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00024485024
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
627	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD	0.00015460957
667	SharedDB: Killing One Thousand Queries With One Stone	2012	VLDB	0.00014978213
705	Main-Memory Scan Sharing For Multi-Core CPUs	2008	VLDB	0.00014657491
762	Cooperative Scans: Dynamic Bandwidth Sharing in a DBMS	2007	VLDB	0.00014140446
773	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00014084831
873	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.00013338838
910	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013123912
1,036	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD	0.00012377471
1,335	Fast Updates on Read-Optimized Databases Using Multi-Core CPUs	2012	VLDB	0.0001099401
1,497	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010478458
1,529	Column Imprints: A Secondary Index Structure	2013	SIGMOD	0.00010348765
1,723	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.7931223e-05
2,185	Database Compression on Graphics Processors	2010	VLDB	8.8948351e-05
2,201	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	8.8726671e-05
2,225	Shared Workload Optimization	2014	VLDB	8.8081001e-05
2,952	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	7.8153507e-05
3,081	Skipping-oriented Partitioning for Columnar Layouts	2017	VLDB	7.6653727e-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,392	Sharing Data and Work Across Concurrent Analytical Queries	2013	VLDB	6.6213651e-05
6,782	Adaptive Data Skipping in Main-Memory Systems	2016	SIGMOD	5.6835894e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,952	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD
2	4,810	UpBit: Scalable In-Memory Updatable Bitmap Indexing	2016	SIGMOD
3	5,600	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB
4	1,497	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD
5	1,529	Column Imprints: A Secondary Index Structure	2013	SIGMOD
6	2,277	FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems	2022	VLDB
7	5,949	DEX: Scalable Range Indexing on Disaggregated Memory	2024	VLDB
8	773	Bitmap Index Design and Evaluation	1998	SIGMOD
9	10,655	LiveBin: A Localized and Version-Aware Binned Scan Index	2026	SIGMOD
10	8,533	Cabin: a Compressed Adaptive Binned Scan Index	2024	SIGMOD