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: 5776
Venue: SIGMOD
Year: 2020
Pagerank: 5.3418923e-05
Overall Rank: 5,749 | 60.01%
DOI: 10.1145/3318464.3380563

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,972	Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses	2024	SIGMOD	4.8785237e-05
7,483	RTScan: Efficient Scan with Ray Tracing Cores	2024	VLDB	4.7180617e-05
7,831	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB	4.6387445e-05
8,447	Cabin: a Compressed Adaptive Binned Scan Index	2024	SIGMOD	4.5102052e-05
9,976	Raster is Faster: Rethinking Ray Tracing in Database Indexing	2026	CIDR	4.1945683e-05
10,105	RABIT: Efficient Range Queries with Bitmap Indexing	2026	SIGMOD	4.1945683e-05
10,290	RayDB: Building Databases with Ray Tracing Cores	2026	VLDB	4.1945683e-05
11,504	LES3: Learning-based Exact Set Similarity Search	2021	VLDB	4.1945683e-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.0040449103
21	C-Store: A Column-oriented DBMS	2005	VLDB	0.00086087497
52	Database Architecture Optimized for the new Bottleneck: Memory Access	1999	VLDB	0.00066474881
121	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00045447517
131	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.0004370331
305	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00028248614
343	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00026768139
368	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.000254931
830	Main-Memory Scan Sharing For Multi-Core CPUs	2008	VLDB	0.00016171897
940	SharedDB: Killing One Thousand Queries With One Stone	2012	VLDB	0.00015173166
958	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD	0.00015045316
1,026	Cooperative Scans: Dynamic Bandwidth Sharing in a DBMS	2007	VLDB	0.00014589172
1,035	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00014532778
1,134	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013761456
1,270	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.00012926086
1,477	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD	0.00011770865
1,704	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.000108332
1,731	Fast Updates on Read-Optimized Databases Using Multi-Core CPUs	2012	VLDB	0.0001073454
1,989	Column Imprints: A Secondary Index Structure	2013	SIGMOD	9.8478437e-05
2,390	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	8.9084657e-05
2,862	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	7.9898539e-05
2,882	Database Compression on Graphics Processors	2010	VLDB	7.9661218e-05
2,925	Shared Workload Optimization	2014	VLDB	7.888494e-05
3,608	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	6.924272e-05
3,737	Skipping-oriented Partitioning for Columnar Layouts	2017	VLDB	6.8033227e-05
4,161	Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?	2017	SIGMOD	6.3938006e-05
4,959	Sharing Data and Work Across Concurrent Analytical Queries	2013	VLDB	5.8029448e-05
6,809	Adaptive Data Skipping in Main-Memory Systems	2016	SIGMOD	4.9206606e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,608	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	6.924272e-05
5,346	UpBit: Scalable In-Memory Updatable Bitmap Indexing	2016	SIGMOD	5.5561846e-05
5,596	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB	5.4181535e-05
1,704	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.000108332
1,989	Column Imprints: A Secondary Index Structure	2013	SIGMOD	9.8478437e-05
3,131	FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems	2022	VLDB	7.4985793e-05
6,741	DEX: Scalable Range Indexing on Disaggregated Memory	2024	VLDB	4.9432931e-05
1,035	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00014532778
10,179	LiveBin: A Localized and Version-Aware Binned Scan Index	2026	SIGMOD	4.1945683e-05
8,447	Cabin: a Compressed Adaptive Binned Scan Index	2024	SIGMOD	4.5102052e-05