{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T17:18:50Z","timestamp":1790702330903,"version":"4.1.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:p>In modern data warehousing, data skipping is essential for high query performance. While index structures such as B-trees or hash tables allow for precise pruning, their large storage requirements make them impractical for indexing secondary columns. Therefore, many systems rely on approximate indexes such as min\/max sketches (ZoneMaps) or Bloom filters for cost-effective data pruning. For example, Google PowerDrill skips more than 90% of data on average using such indexes.<\/jats:p>\n          <jats:p>In this paper, we introduce Cuckoo Index (CI), an approximate secondary index structure that represents the many-to-many relationship between keys and data partitions in a highly space-efficient way. At its core, CI associates variable-sized fingerprints in a Cuckoo filter with compressed bitmaps indicating qualifying partitions. With our approach, we target equality predicates in a read-only (immutable) setting and optimize for space efficiency under the premise of practical build and lookup performance.<\/jats:p>\n          <jats:p>In contrast to per-partition (Bloom) filters, CI produces correct results for lookups with keys that occur in the data. CI allows to control the ratio of false positive partitions for lookups with non-occurring keys. Our experiments with real-world and synthetic data show that CI consumes significantly less space than per-partition filters for the same pruning power for low-to-medium cardinality columns. For high cardinality columns, CI is on par with its baselines.<\/jats:p>","DOI":"10.14778\/3424573.3424577","type":"journal-article","created":{"date-parts":[[2020,10,28]],"date-time":"2020-10-28T01:15:32Z","timestamp":1603847732000},"page":"3559-3572","source":"Crossref","is-referenced-by-count":17,"title":["Cuckoo index"],"prefix":"10.14778","volume":"13","author":[{"given":"Andreas","family":"Kipf","sequence":"first","affiliation":[{"name":"MIT CSAIL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Damian","family":"Chromejko","sequence":"additional","affiliation":[{"name":"Google"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"Hall","sequence":"additional","affiliation":[{"name":"RelationalAI"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Boncz","sequence":"additional","affiliation":[{"name":"CWI"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David G.","family":"Andersen","sequence":"additional","affiliation":[{"name":"CMU"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,10,27]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"LevelDB. https:\/\/github.com\/google\/leveldb\/.  LevelDB. https:\/\/github.com\/google\/leveldb\/."},{"key":"e_1_2_1_2_1","unstructured":"Vehicle snowmobile and boat registrations. https:\/\/catalog.data.gov\/dataset\/vehicle-snowmobile-and-boat-registrations.  Vehicle snowmobile and boat registrations. https:\/\/catalog.data.gov\/dataset\/vehicle-snowmobile-and-boat-registrations."},{"key":"e_1_2_1_3_1","unstructured":"Xor Filter. https:\/\/github.com\/FastFilter\/xor\\_singleheader\/.  Xor Filter. https:\/\/github.com\/FastFilter\/xor\\_singleheader\/."},{"key":"e_1_2_1_4_1","unstructured":"Zstandard Compression. https:\/\/facebook.github.io\/zstd\/.  Zstandard Compression. https:\/\/facebook.github.io\/zstd\/."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/645927.672367"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915964"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2325"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/982792.982797"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2903741"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2040572.2040639"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_32"},{"key":"e_1_2_1_13_1","volume-title":"Tsunami: A learned multi-dimensional index for correlated data and skewed workloads. CoRR, abs\/2006.13282","author":"Ding J.","year":"2020"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976007.14"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585996"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194281185"},{"key":"e_1_2_1_18_1","volume-title":"Invertible Bloom Lookup Tables. CoRR, abs\/1101.2245","author":"Goodrich M. T.","year":"2011"},{"key":"e_1_2_1_19_1","volume-title":"Xor Filters: Faster and smaller than Bloom and Cuckoo Filters. CoRR, abs\/1912.08258","author":"Graf T. M.","year":"2019"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732999"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350259"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196911"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_1_24_1","volume-title":"NeurIPS Workshop on Machine Learning for Systems","author":"Kipf A.","year":"2019"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3401071.3401659"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380588"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882925"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303757"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2009.08.006"},{"key":"e_1_2_1_32_1","volume-title":"Benchmarking learned indexes. CoRR, abs\/2006.12804","author":"Marcus R.","year":"2020"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/645924.671173"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380579"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/253262.253268"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151106.3151108"},{"key":"e_1_2_1_38_1","volume-title":"Technische Universit\u00e4t Ilmenau","author":"Rink M.","year":"2015"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2019.8888050"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465306"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132863.1132864"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319861"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2791347.2791372"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3424573.3424577","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:19:11Z","timestamp":1672219151000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3424573.3424577"}},"subtitle":["a lightweight secondary index structure"],"short-title":[],"issued":{"date-parts":[[2020,9]]},"references-count":44,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["10.14778\/3424573.3424577"],"URL":"https:\/\/doi.org\/10.14778\/3424573.3424577","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,9]]}}}