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: 5777
Venue: SIGMOD
Year: 2020
Pagerank: 5.3367636e-05
Overall Rank: 5,762 | 59.96%
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,971	Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses	2024	SIGMOD	4.8738633e-05
7,482	RTScan: Efficient Scan with Ray Tracing Cores	2024	VLDB	4.7135369e-05
7,837	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB	4.6342964e-05
8,439	Cabin: a Compressed Adaptive Binned Scan Index	2024	SIGMOD	4.5058812e-05
9,975	Raster is Faster: Rethinking Ray Tracing in Database Indexing	2026	CIDR	4.1905499e-05
10,105	RABIT: Efficient Range Queries with Bitmap Indexing	2026	SIGMOD	4.1905499e-05
10,302	RayDB: Building Databases with Ray Tracing Cores	2026	VLDB	4.1905499e-05
11,508	LES3: Learning-based Exact Set Similarity Search	2021	VLDB	4.1905499e-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.0040465394
20	C-Store: A Column-oriented DBMS	2005	VLDB	0.00086163998
52	Database Architecture Optimized for the new Bottleneck: Memory Access	1999	VLDB	0.00066322421
121	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00045429472
132	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.00043697853
307	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00028226342
343	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00026756534
367	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00025518228
826	Main-Memory Scan Sharing For Multi-Core CPUs	2008	VLDB	0.00016161625
934	SharedDB: Killing One Thousand Queries With One Stone	2012	VLDB	0.00015201246
959	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD	0.00015034808
1,027	Cooperative Scans: Dynamic Bandwidth Sharing in a DBMS	2007	VLDB	0.0001458537
1,033	Bitmap Index Design and Evaluation	1998	SIGMOD	0.0001453376
1,134	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013751593
1,267	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.00012917585
1,473	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD	0.00011786148
1,701	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010828605
1,726	Fast Updates on Read-Optimized Databases Using Multi-Core CPUs	2012	VLDB	0.00010734339
1,993	Column Imprints: A Secondary Index Structure	2013	SIGMOD	9.8403548e-05
2,390	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	8.9006978e-05
2,821	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	8.0639288e-05
2,890	Database Compression on Graphics Processors	2010	VLDB	7.9586083e-05
2,928	Shared Workload Optimization	2014	VLDB	7.881485e-05
3,611	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	6.9178844e-05
3,731	Skipping-oriented Partitioning for Columnar Layouts	2017	VLDB	6.8074069e-05
4,160	Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?	2017	SIGMOD	6.3886736e-05
4,964	Sharing Data and Work Across Concurrent Analytical Queries	2013	VLDB	5.7974073e-05
6,807	Adaptive Data Skipping in Main-Memory Systems	2016	SIGMOD	4.915939e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,341	UpBit: Scalable In-Memory Updatable Bitmap Indexing	2016	SIGMOD	5.5592799e-05
3,611	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	6.9178844e-05
5,605	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB	5.413565e-05
1,701	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010828605
1,993	Column Imprints: A Secondary Index Structure	2013	SIGMOD	9.8403548e-05
3,136	FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems	2022	VLDB	7.4926368e-05
6,742	DEX: Scalable Range Indexing on Disaggregated Memory	2024	VLDB	4.9385502e-05
1,033	Bitmap Index Design and Evaluation	1998	SIGMOD	0.0001453376
10,179	LiveBin: A Localized and Version-Aware Binned Scan Index	2026	SIGMOD	4.1905499e-05
8,439	Cabin: a Compressed Adaptive Binned Scan Index	2024	SIGMOD	4.5058812e-05