{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T06:52:08Z","timestamp":1777013528537,"version":"3.51.4"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2020,3,13]],"date-time":"2020-03-13T00:00:00Z","timestamp":1584057600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100008433","name":"Comunidad de Madrid","doi-asserted-by":"publisher","award":["P2018\/TCS-4496"],"award-info":[{"award-number":["P2018\/TCS-4496"]}],"id":[{"id":"10.13039\/501100008433","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1563710, CCF-1535795, CCF- 1320231, and CNS-1228598"],"award-info":[{"award-number":["CCF-1563710, CCF-1535795, CCF- 1320231, and CNS-1228598"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010669","name":"H2020 LEIT Information and Communication Technologies","doi-asserted-by":"publisher","award":["762057"],"award-info":[{"award-number":["762057"]}],"id":[{"id":"10.13039\/100010669","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010198","name":"Ministerio de Econom\u00eda, Industria y Competitividad, Gobierno de Espa\u00f1a","doi-asserted-by":"crossref","award":["TEC2016-80339-R"],"award-info":[{"award-number":["TEC2016-80339-R"]}],"id":[{"id":"10.13039\/501100010198","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2020,12,6]]},"abstract":"<jats:p>We introduce the adaptive cuckoo filter (ACF), a data structure for approximate set membership that extends cuckoo filters by reacting to false positives, removing them for future queries. As an example application, in packet processing queries may correspond to flow identifiers, so a search for an element is likely to be followed by repeated searches for that element. Removing false positives can therefore significantly lower the false-positive rate. The ACF, like the cuckoo filter, uses a cuckoo hash table to store fingerprints. We allow fingerprint entries to be changed in response to a false positive in a manner designed to minimize the effect on the performance of the filter. We show that the ACF is able to significantly reduce the false-positive rate by presenting both a theoretical model for the false-positive rate and simulations using both synthetic data sets and real packet traces.<\/jats:p>","DOI":"10.1145\/3339504","type":"journal-article","created":{"date-parts":[[2020,3,13]],"date-time":"2020-03-13T12:03:13Z","timestamp":1584100993000},"page":"1-20","source":"Crossref","is-referenced-by-count":29,"title":["Adaptive Cuckoo Filters"],"prefix":"10.1145","volume":"25","author":[{"given":"Michael","family":"Mitzenmacher","sequence":"first","affiliation":[{"name":"Harvard University, Cambridge MA, USA"}]},{"given":"Salvatore","family":"Pontarelli","sequence":"additional","affiliation":[{"name":"Consorzio Nazionale Interuniversitario per le Telecomunicazioni (CNIT), Rome, Italy"}]},{"given":"Pedro","family":"Reviriego","sequence":"additional","affiliation":[{"name":"Universidad Carlos III de Madrid, Madrid, Spain"}]}],"member":"320","published-online":{"date-parts":[[2020,3,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00026"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129096"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2006.261978"},{"key":"e_1_2_1_5_1","unstructured":"CAIDA. 2018. Realtime Passive Network Monitors. Retrieved from http:\/\/www.caida.org\/data\/realtime\/passive.  CAIDA. 2018. Realtime Passive Network Monitors. Retrieved from http:\/\/www.caida.org\/data\/realtime\/passive."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904)","author":"Chazelle Bernard","year":"2004","unstructured":"Bernard Chazelle , Joe Kilian , Ronitt Rubinfeld , and Ayellet Tal . 2004 . The bloomier filter: An efficient data structure for static support lookup tables . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904) . Society for Industrial and Applied Mathematics, Philadelphia, PA, 30--39. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=982792.982797. Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, and Ayellet Tal. 2004. The bloomier filter: An efficient data structure for static support lookup tables. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904). Society for Industrial and Applied Mathematics, Philadelphia, PA, 30--39. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=982792.982797."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.054"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1368436.1368454"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 7th Workshop on Distributed Data and Structures (WDAS\u201906)","author":"Erlingsson Ulfar","year":"2006","unstructured":"Ulfar Erlingsson , Mark Manasse , and Frank McSherry . 2006 . A cool and practical alternative to traditional hash tables . In Proceedings of the 7th Workshop on Distributed Data and Structures (WDAS\u201906) . Ulfar Erlingsson, Mark Manasse, and Frank McSherry. 2006. A cool and practical alternative to traditional hash tables. In Proceedings of the 7th Workshop on Distributed Data and Structures (WDAS\u201906)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1195-x"},{"key":"e_1_2_1_12_1","volume-title":"64 and IA-32 Architectures Software Developer\u2019s Manual","unstructured":"Intel. 2011. 64 and IA-32 Architectures Software Developer\u2019s Manual , Volume 2 . Intel. 2011. 64 and IA-32 Architectures Software Developer\u2019s Manual, Volume 2."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1957995.1958011"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13389-015-0110-5"},{"key":"e_1_2_1_15_1","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Eli Upfal . 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis . Cambridge University Press . Michael Mitzenmacher and Eli Upfal. 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 746--755","author":"Mitzenmacher Michael","year":"2008","unstructured":"Michael Mitzenmacher and Salil Vadhan . 2008 . Why simple hash functions work: Exploiting the entropy in a data stream . In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 746--755 . Michael Mitzenmacher and Salil Vadhan. 2008. Why simple hash functions work: Exploiting the entropy in a data stream. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 746--755."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2015.2417524"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2096149.2096152"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400798"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3339504","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3339504","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3339504","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:08Z","timestamp":1750204448000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3339504"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,13]]},"references-count":20,"alternative-id":["10.1145\/3339504"],"URL":"https:\/\/doi.org\/10.1145\/3339504","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,13]]}}}