Cuckoo Index: A Lightweight Secondary Index Structure

Summary: CI is an approximate secondary index using a Cuckoo filter with compressed bitmaps to prune partitions for equality lookups in read-only workloads. It reduces space compared to per-partition Bloom filters for low-to-medium cardinality data and remains competitive for high cardinality, with configurable false-positive control. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h6dc3037c4d39a085
Venue: VLDB
Year: 2020
Pagerank: 6.4102054e-05
Overall Rank: 4,773 | 68.01%
DOI: 10.14778/3424573.3424577
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Andreas Kipf (Massachusetts Institute of Technology)
2. Damian Chromejko (Google)
3. Alexander Hall (RelationalAI)
4. Peter Boncz (Centrum Wiskunde & Informatica)
5. David G. Andersen (Carnegie Mellon University)

BibTeX Citation

@article{kipf_vldb20,
        title = {{Cuckoo Index: A Lightweight Secondary Index Structure}},
        author = {Kipf, Andreas and Chromejko, Damian and Hall, Alexander and Boncz, Peter and Andersen, David G.},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {13},
        pages = {3559--3572},
        doi = {10.14778/3424573.3424577},
        url = {https://doi.org/10.14778/3424573.3424577},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,303	Cloud Analytics Benchmark	2023	VLDB	7.4212268e-05
4,092	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	6.7958327e-05
4,915	Can Learned Models Replace Hash Functions?	2023	VLDB	6.3452789e-05
6,250	Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses	2024	SIGMOD	5.818039e-05
7,264	Pruning in Snowflake: Working Smarter, Not Harder	2025	SIGMOD	5.5557256e-05
7,383	Optimizing Collections of Bloom Filters within a Space Budget	2024	VLDB	5.5222465e-05
8,222	Sieve: A Learned Data-Skipping Index for Data Analytics	2023	VLDB	5.3585489e-05
8,604	Conditional Cuckoo Filters	2021	SIGMOD	5.2899825e-05
9,818	NEXT: A New Secondary Index Framework for LSM-based Data Storage	2025	SIGMOD	5.1111219e-05
10,748	RadixGraph: A Fast, Space-Optimized Data Structure for Dynamic Graph Storage	2026	SIGMOD	4.9605343e-05
11,195	Dynamic Pruning for Recursive Joins	2025	SIGMOD	4.9605343e-05
11,610	Breathing New Life into An Old Tree: Resolving Logging Dilemma of B+-tree on Modern Computational Storage Drives	2024	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061463175
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046249672
48	Weaving Relations for Cache Performance	2001	VLDB	0.00043770511
52	The Snowflake Elastic Data Warehouse	2016	SIGMOD	0.00041439488
107	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033376274
216	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00024446892
814	SlimDB: A Space-Efficient Key-Value Storage Engine For Semi-Sorted Data	2017	VLDB	0.00013697533
834	Benchmarking Learned Indexes	2021	VLDB	0.00013539098
870	Learning Multi-dimensional Indexes	2020	SIGMOD	0.0001332034
892	SuRF: Practical Range Query Filtering with Fast Succinct Tries	2018	SIGMOD	0.00013207671
894	Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation	2016	SIGMOD	0.00013179915
1,190	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011564169
1,212	Processing a Trillion Cells per Mouse Click	2012	VLDB	0.00011493478
1,532	Column Imprints: A Secondary Index Structure	2013	SIGMOD	0.00010312002
1,625	Mesa: Geo-Replicated, Near Real-Time, Scalable Data Warehousing	2014	VLDB	0.00010028153
2,249	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.7479608e-05
2,965	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	7.7894987e-05
3,297	Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput	2019	VLDB	7.4280812e-05
4,789	UpBit: Scalable In-Memory Updatable Bitmap Indexing	2016	SIGMOD	6.4016324e-05
8,516	Tree-Encoded Bitmaps	2020	SIGMOD	5.3110731e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,120	Workload-Aware Column Imprints	2020	SIGMOD
2	1,856	Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity	2018	VLDB
3	1,991	Chucky: A Succinct Cuckoo Filter for LSM-Tree	2021	SIGMOD
4	4,646	Stacked Filters: Learning to Filter by Structure	2021	VLDB
5	9,678	Hourglass: An Adaptive Range Filter with Lightweight Hybrid Encoding	2026	SIGMOD
6	10,183	A four-dimensional Analysis of Partitioned Approximate Filters	2021	VLDB
7	3,297	Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput	2019	VLDB
8	11,787	A Learned Cuckoo Filter for Approximate Membership Queries over Variable-sized Sliding Windows on Data Streams	2023	SIGMOD
9	1,532	Column Imprints: A Secondary Index Structure	2013	SIGMOD
10	8,604	Conditional Cuckoo Filters	2021	SIGMOD