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.4309508e-05
Overall Rank: 4,755 | 68.05%
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,311	Cloud Analytics Benchmark	2023	VLDB	7.4364696e-05
4,070	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	6.8183785e-05
4,890	Can Learned Models Replace Hash Functions?	2023	VLDB	6.3663299e-05
6,240	Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses	2024	SIGMOD	5.8373399e-05
7,247	Pruning in Snowflake: Working Smarter, Not Harder	2025	SIGMOD	5.5734736e-05
7,362	Optimizing Collections of Bloom Filters within a Space Budget	2024	VLDB	5.540567e-05
8,207	Sieve: A Learned Data-Skipping Index for Data Analytics	2023	VLDB	5.3763264e-05
8,587	Conditional Cuckoo Filters	2021	SIGMOD	5.3075325e-05
9,786	NEXT: A New Secondary Index Framework for LSM-based Data Storage	2025	SIGMOD	5.1280785e-05
10,687	RadixGraph: A Fast, Space-Optimized Data Structure for Dynamic Graph Storage	2026	SIGMOD	4.9769913e-05
11,135	Dynamic Pruning for Recursive Joins	2025	SIGMOD	4.9769913e-05
11,561	Breathing New Life into An Old Tree: Resolving Logging Dilemma of B+-tree on Modern Computational Storage Drives	2024	VLDB	4.9769913e-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.00061067652
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046363107
48	Weaving Relations for Cache Performance	2001	VLDB	0.00043795812
52	The Snowflake Elastic Data Warehouse	2016	SIGMOD	0.00041210636
107	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033459417
216	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00024485637
817	SlimDB: A Space-Efficient Key-Value Storage Engine For Semi-Sorted Data	2017	VLDB	0.00013685662
835	Benchmarking Learned Indexes	2021	VLDB	0.00013575971
869	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013363241
889	SuRF: Practical Range Query Filtering with Fast Succinct Tries	2018	SIGMOD	0.00013243846
907	Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation	2016	SIGMOD	0.00013157412
1,188	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011598149
1,210	Processing a Trillion Cells per Mouse Click	2012	VLDB	0.0001152237
1,531	Column Imprints: A Secondary Index Structure	2013	SIGMOD	0.00010344951
1,623	Mesa: Geo-Replicated, Near Real-Time, Scalable Data Warehousing	2014	VLDB	0.00010047769
2,237	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.7738349e-05
2,954	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	7.8119682e-05
3,285	Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput	2019	VLDB	7.4525495e-05
4,771	UpBit: Scalable In-Memory Updatable Bitmap Indexing	2016	SIGMOD	6.4223645e-05
8,500	Tree-Encoded Bitmaps	2020	SIGMOD	5.3286931e-05

Semantically Similar Papers

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