{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T05:35:32Z","timestamp":1791437732517,"version":"4.3.3"},"reference-count":83,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,5]]},"abstract":"<jats:p>\n            Approximate set membership data structures (ASMDSs) are ubiquitous in computing. They trade a tunable, often small, error rate (\n            <jats:italic>\u03f5<\/jats:italic>\n            ) for large space savings. The canonical ASMDS is the Bloom filter, which supports lookups and insertions but not deletions in its simplest form. Cuckoo filters (CFs), a recently proposed class of ASMDSs, add deletion support and often use fewer bits per item for equal\n            <jats:italic>\u03f5<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            This work introduces the Morton filter (MF), a novel AS-MDS that introduces several key improvements to CFs. Like CFs, MFs support lookups, insertions, and deletions, but improve their respective throughputs by 1.3x to 2.5x, 0.9x to 15.5x, and 1.3x to 1.6x. MFs achieve these improvements by (1) introducing a compressed format that permits a logically sparse filter to be stored compactly in memory, (2) leveraging succinct embedded metadata to prune unnecessary memory accesses, and (3) heavily biasing insertions to use a single hash function. With these optimizations, lookups, insertions, and deletions often only require accessing a single hardware cache line from the filter. These improvements are not at a loss in space efficiency, as MFs typically use comparable to slightly less space than CFs for the same\n            <jats:italic>epsis;<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.14778\/3213880.3213884","type":"journal-article","created":{"date-parts":[[2018,6,12]],"date-time":"2018-06-12T18:15:11Z","timestamp":1528827311000},"page":"1041-1055","source":"Crossref","is-referenced-by-count":70,"title":["Morton filters"],"prefix":"10.14778","volume":"11","author":[{"given":"Alex D.","family":"Breslow","sequence":"first","affiliation":[{"name":"Advanced Micro Devices, Inc."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nuwan S.","family":"Jayasena","sequence":"additional","affiliation":[{"name":"Advanced Micro Devices, Inc."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.10.007"},{"key":"e_1_2_1_2_1","first-page":"476","volume-title":"Data Compression Conference, 1995. DCC '95. Proceedings","author":"Antoshenkov G."},{"key":"e_1_2_1_3_1","unstructured":"A. Appleby. MurmurHash. https:\/\/sites.google.com\/site\/murmurhash 2008. Accessed: 2018-02-05.  A. Appleby. MurmurHash. https:\/\/sites.google.com\/site\/murmurhash 2008. Accessed: 2018-02-05."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288490"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350275"},{"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.5555\/645925.671364"},{"key":"e_1_2_1_9_1","first-page":"225","volume-title":"CIDR 2005, Second Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 4--7, 2005, Online Proceedings","author":"Boncz P. A.","year":"2005"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_61"},{"key":"e_1_2_1_11_1","volume-title":"Forty-Fourth Annual Allerton Conference","author":"Bonomi F.","year":"2006"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/645912.671296"},{"key":"e_1_2_1_13_1","first-page":"281","volume-title":"2016 USENIX Annual Technical Conference, USENIX ATC 2016","author":"Breslow A. D.","year":"2016"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129096"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804332"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2325"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872787"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.05.018"},{"key":"e_1_2_1_20_1","volume-title":"July 27, 2011. Accessed:  2017-01-25","author":"Dean J."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142477"},{"key":"e_1_2_1_22_1","volume-title":"CIDR 2017, 8th Biennial Conference on Innovative Data Systems Research, Chaminade, CA, USA, January 8--11, 2017, Online Proceedings","author":"Dong S.","year":"2017"},{"key":"e_1_2_1_23_1","volume-title":"Random House","author":"Seuss Dr.","year":"1940"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2017.2685530"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056115"},{"key":"e_1_2_1_26_1","volume-title":"Proc. 7th Workshop on Distributed Data and Structures (WDAS06)","author":"Erlingsson U.","year":"2006"},{"key":"e_1_2_1_27_1","first-page":"371","volume-title":"Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2013","author":"Fan B.","year":"2013"},{"key":"e_1_2_1_28_1","unstructured":"B. Fan D. G. Andersen and M. Kaminsky. Cuckoo filter. https:\/\/github.com\/efficient\/cuckoofilter 2017. Accessed: 2017-11-19.  B. Fan D. G. Andersen and M. Kaminsky. Cuckoo filter. https:\/\/github.com\/efficient\/cuckoofilter 2017. Accessed: 2017-11-19."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.851975"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1972.5009071"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_2_1_33_1","volume-title":"Inc.","author":"George L.","year":"2011"},{"key":"e_1_2_1_34_1","volume-title":"Poster Proc.","volume":"38","author":"Gonz\u00e1lez R.","year":"2005"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/800046.801647"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.68"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816675"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63533"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745844.2745867"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1973.5009159"},{"key":"e_1_2_1_41_1","volume-title":"CIDR 2015, Seventh Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 4--7, 2015, Online Proceedings","author":"Kornacker M.","year":"2015"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/378993.379239"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1773912.1773922"},{"key":"e_1_2_1_44_1","volume-title":"June 27, 2016. Accessed:  2017-07-01","author":"Lemire D."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592820"},{"key":"e_1_2_1_46_1","first-page":"1","volume-title":"Intel White Paper","author":"Lomont C.","year":"2011"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/321992.322000"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/645913.671480"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-12-333"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/383962.384004"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.963420"},{"key":"e_1_2_1_52_1","volume-title":"Cambridge University Press","author":"Mitzenmacher M.","year":"2017"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxx046"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/3092586"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/2791188.2791194"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/7902.7904"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035963"},{"key":"e_1_2_1_60_1","doi-asserted-by":"crossref","unstructured":"P. Pandey and R. Johnson. A general-purpose counting filter: counting quotient filter. https:\/\/github.com\/splatlab\/cqf 2017. Accessed: 2017-11-09.  P. Pandey and R. Johnson. A general-purpose counting filter: counting quotient filter. https:\/\/github.com\/splatlab\/cqf 2017. Accessed: 2017-11-09.","DOI":"10.1145\/3035918.3035963"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2747645"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498698.1594230"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545411"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/40.865866"},{"key":"e_1_2_1_65_1","first-page":"1297","volume-title":"Proceedings of the 23rd International Conference on Data Engineering, ICDE 2007, The Marmara Hotel","author":"Ross K. A.","year":"2007"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2013.2272604"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213862"},{"key":"e_1_2_1_68_1","unstructured":"T. Sigaev A. Korotkov and O. Bartunov. PostgreSQL 10 documentation: F.5. bloom. https:\/\/www.postgresql.org\/docs\/10\/static\/bloom.html 2017. Accessed: 2018-01-25.  T. Sigaev A. Korotkov and O. Bartunov. PostgreSQL 10 documentation: F.5. bloom. https:\/\/www.postgresql.org\/docs\/10\/static\/bloom.html 2017. Accessed: 2018-01-25."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.5555\/800052.801871"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.50912"},{"key":"e_1_2_1_71_1","first-page":"553","volume-title":"2017 USENIX Annual Technical Conference, USENIX ATC 2017","author":"Sun Y.","year":"2017"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359175"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1967.6011"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/232973.232993"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/223982.224449"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796480"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064007"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/76263.76337"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132863.1132864"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.136"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809984"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/360128.360134"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3213880.3213884","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:02:31Z","timestamp":1672221751000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3213880.3213884"}},"subtitle":["faster, space-efficient cuckoo filters via biasing, compression, and decoupled logical sparsity"],"short-title":[],"issued":{"date-parts":[[2018,5]]},"references-count":83,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["10.14778\/3213880.3213884"],"URL":"https:\/\/doi.org\/10.14778\/3213880.3213884","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,5]]}}}