{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,8]],"date-time":"2025-11-08T13:46:46Z","timestamp":1762609606474,"version":"3.44.0"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T00:00:00Z","timestamp":1701993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"nsfc","doi-asserted-by":"crossref","award":["U20A20179, 62372009"],"award-info":[{"award-number":["U20A20179, 62372009"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,12,8]]},"abstract":"<jats:p>Membership (membership query\/membership testing) is a fundamental problem across databases, networks and security. However, previous research has primarily focused on either approximate solutions, such as Bloom Filters, or exact methods, like perfect hashing and dictionaries, without attempting to develop an integral theory. In this paper, we propose a unified and complete theory, namely chain rule, for general membership problems, which encompasses both approximate and exact membership as extreme cases. Building upon the chain rule, we introduce a straightforward yet versatile algorithm framework, namely ChainedFilter, to combine different elementary filters without losing information. Our evaluation results demonstrate that ChainedFilter improves performance of many applications including static dictionary, lossless data compression, Cuckoo Hashing, LSM-Tree and Learned Filters.<\/jats:p>","DOI":"10.1145\/3626721","type":"journal-article","created":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T14:01:21Z","timestamp":1702389681000},"page":"1-27","source":"Crossref","is-referenced-by-count":2,"title":["ChainedFilter: Combining Membership Filters by Chain Rule"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-5822-4629","authenticated-orcid":false,"given":"Haoyu","family":"Li","sequence":"first","affiliation":[{"name":"UT Austin &amp; Peking University, Austin, TX, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-0771-6441","authenticated-orcid":false,"given":"Liuhui","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-4020-6772","authenticated-orcid":false,"given":"Qizhi","family":"Chen","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-0726-1210","authenticated-orcid":false,"given":"Jianan","family":"Ji","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7115-5390","authenticated-orcid":false,"given":"Yuhan","family":"Wu","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2495-7774","authenticated-orcid":false,"given":"Yikai","family":"Zhao","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2402-5854","authenticated-orcid":false,"given":"Tong","family":"Yang","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5920-170X","authenticated-orcid":false,"given":"Aditya","family":"Akella","sequence":"additional","affiliation":[{"name":"UT Austin, Austin, TX, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2011.031611.00024"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129096"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2013.09.003"},{"key":"e_1_2_2_4_1","volume-title":"Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems (TOCS), 26(2):1--26","author":"Chang Fay","year":"2008","unstructured":"Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C Hsieh, Deborah A Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E Gruber. Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems (TOCS), 26(2):1--26, 2008."},{"key":"e_1_2_2_5_1","volume-title":"Optimal bloom filters and adaptive merging for lsm-trees. ACM Transactions on Database Systems (TODS), 43(4):1--48","author":"Dayan Niv","year":"2018","unstructured":"Niv Dayan, Manos Athanassoulis, and Stratos Idreos. Optimal bloom filters and adaptive merging for lsm-trees. ACM Transactions on Database Systems (TODS), 43(4):1--48, 2018."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415546"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1185347.1185356"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2011.6089061"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSM.2020.3024680"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/Allerton.2011.6120248"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341302.3342082"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/BLOC.2019.8751297"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804332"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_2_15_1","volume-title":"Rocksdb: Evolution of development priorities in a key-value store serving large-scale applications. ACM Transactions on Storage (TOS), 17(4):1--32","author":"Dong Siying","year":"2021","unstructured":"Siying Dong, Andrew Kryczka, Yanqin Jin, and Michael Stumm. Rocksdb: Evolution of development priorities in a key-value store serving large-scale applications. ACM Transactions on Storage (TOS), 17(4):1--32, 2021."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_2_17_1","first-page":"31","article-title":"A model for learned bloom filters and optimizing by sandwiching","author":"Mitzenmacher Michael","year":"2018","unstructured":"Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. Advances in Neural Information Processing Systems, 31, 2018.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407830"},{"key":"e_1_2_2_19_1","first-page":"11700","article-title":"Adaptive learned bloom filter (ada-bf): efficient utilization of the classifier with application to real-time information filtering on the web","volume":"33","author":"Dai Zhenwei","year":"2020","unstructured":"Zhenwei Dai and Anshumali Shrivastava. Adaptive learned bloom filter (ada-bf): efficient utilization of the classifier with application to real-time information filtering on the web. Advances in Neural Information Processing Systems, 33:11700--11710, 2020.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_2_20_1","unstructured":"The open source code of chainedfilter. https:\/\/github.com\/ChainedFilter."},{"key":"e_1_2_2_21_1","first-page":"30","volume-title":"Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms","author":"Chazelle Bernard","year":"2004","unstructured":"Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, and Ayellet Tal. The bloomier filter: an efficient data structure for static support lookup tables. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 30--39. Citeseer, 2004."},{"key":"e_1_2_2_22_1","first-page":"259","volume-title":"Proceedings 16","author":"Charles Denis","year":"2008","unstructured":"Denis Charles and Kumar Chellapilla. Bloomier filters: A second look. In Algorithms-ESA 2008: 16th Annual European Symposium, Karlsruhe, Germany, September 15--17, 2008. Proceedings 16, pages 259--270. Springer, 2008."},{"key":"e_1_2_2_23_1","volume-title":"Xor filters: Faster and smaller than bloom and cuckoo filters. Journal of Experimental Algorithmics (JEA), 25:1--16","author":"Graf Thomas Mueller","year":"2020","unstructured":"Thomas Mueller Graf and Daniel Lemire. Xor filters: Faster and smaller than bloom and cuckoo filters. Journal of Experimental Algorithmics (JEA), 25:1--16, 2020."},{"key":"e_1_2_2_24_1","volume-title":"Binary fuse filters: Fast and smaller than xor filters. Journal of Experimental Algorithmics (JEA), 27(1):1--15","author":"Graf Thomas Mueller","year":"2022","unstructured":"Thomas Mueller Graf and Daniel Lemire. Binary fuse filters: Fast and smaller than xor filters. Journal of Experimental Algorithmics (JEA), 27(1):1--15, 2022."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.131"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2018.2820067"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00105"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.80"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/120867044"},{"key":"e_1_2_2_31_1","unstructured":"Murmur hashing source code. https:\/\/github.com\/aappleby\/smhasher\/blob\/master\/src\/MurmurHash3.cpp."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"e_1_2_2_33_1","volume-title":"Asymmetric numeral systems: entropy coding combining speed of huffman coding with compression rate of arithmetic coding. arXiv preprint arXiv:1311.2540","author":"Duda Jarek","year":"2013","unstructured":"Jarek Duda. Asymmetric numeral systems: entropy coding combining speed of huffman coding with compression rate of arithmetic coding. arXiv preprint arXiv:1311.2540, 2013."},{"key":"e_1_2_2_34_1","first-page":"730","volume-title":"Proceedings 17","author":"Hreinsson J\u00f3hannes B","year":"2009","unstructured":"J\u00f3hannes B Hreinsson, Morten Kr\u00f8yer, and Rasmus Pagh. Storing a compressed function with constant time access. In Algorithms-ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7--9, 2009. Proceedings 17, pages 730--741. Springer, 2009."},{"key":"e_1_2_2_35_1","volume-title":"Approximate membership query filters with a false positive free set. arXiv preprint arXiv:2111.06856","author":"Reviriego Pedro","year":"2021","unstructured":"Pedro Reviriego, Alfonso S\u00e1nchez-Maci\u00e1n, Stefan Walzer, and Peter C Dillinger. Approximate membership query filters with a false positive free set. arXiv preprint arXiv:2111.06856, 2021."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.963420"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00032-8"},{"key":"e_1_2_2_39_1","volume-title":"Summary cache: a scalable wide-area web cache sharing protocol","author":"Fan Li","year":"2000","unstructured":"Li Fan, Pei Cao, Jussara Almeida, and Andrei Z Broder. Summary cache: a scalable wide-area web cache sharing protocol. IEEE\/ACM transactions on networking, 8(3):281--293, 2000."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2818716"},{"key":"e_1_2_2_41_1","article-title":"A short introduction to boosting","author":"Freund Yoav","year":"1999","unstructured":"Yoav Freund, Robert Schapire, and Naoki Abe. A short introduction to boosting. Journal-Japanese Society For Artificial Intelligence, 14(771--780):1612, 1999.","journal-title":"Journal-Japanese Society For Artificial Intelligence, 14(771--780):1612"},{"key":"e_1_2_2_42_1","unstructured":"The open source code of learned filter. https:\/\/github.com\/karthikeya20\/Learned-Bloom-Filters."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2021.3067713"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3221111"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3523210.3523220"},{"issue":"1","key":"e_1_2_2_46_1","first-page":"1","article-title":"Filtering infrequent items with small memory and time overhead","volume":"1","author":"Li Yuanpeng","year":"2023","unstructured":"Yuanpeng Li, Feiyu Wang, Xiang Yu, Yilong Yang, Kaicheng Yang, Tong Yang, Zhuo Ma, Bin Cui, and Steve Uhlig. Ladderfilter: Filtering infrequent items with small memory and time overhead. Proceedings of the ACM on Management of Data, 1(1):1--21, 2023.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580305.3599505"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00158"},{"key":"e_1_2_2_49_1","first-page":"743","volume-title":"19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22)","author":"Namkung Hun","year":"2022","unstructured":"Hun Namkung, Zaoxing Liu, Daehyeok Kim, Vyas Sekar, and Peter Steenkiste. {SketchLib}: Enabling efficient sketch-based monitoring on programmable switches. In 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22), pages 743--759, 2022."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/IWQoS57198.2023.10188743"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3200045"},{"key":"e_1_2_2_52_1","first-page":"1273","volume-title":"20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23)","author":"Namkung Hun","year":"2023","unstructured":"Hun Namkung, Zaoxing Liu, Daehyeok Kim, Vyas Sekar, and Peter Steenkiste. Sketchovsky: Enabling ensembles of sketches on programmable switches. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23), pages 1273--1292, 2023."},{"key":"e_1_2_2_53_1","unstructured":"Zirui Liu Chaozhe Kong Kaicheng Yang Tong Yang Ruijie Miao Qizhi Chen Yikai Zhao Yaofeng Tu and Bin Cui. Hypercalm sketch: One-pass mining periodic batches in data streams."},{"key":"e_1_2_2_54_1","first-page":"385","volume-title":"35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7--11, 2008, Proceedings, Part I 35","author":"Dietzfelbinger Martin","year":"2008","unstructured":"Martin Dietzfelbinger and Rasmus Pagh. Succinct data structures for retrieval and approximate membership. In Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7--11, 2008, Proceedings, Part I 35, pages 385--396. Springer, 2008."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03351-3_25"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/39.6.547"},{"key":"e_1_2_2_57_1","volume-title":"Storing a sparse table with 0 (1) worst case access time. Journal of the ACM (JACM), 31(3):538--544","author":"Fredman Michael L","year":"1984","unstructured":"Michael L Fredman, J\u00e1nos Koml\u00f3s, and Endre Szemer\u00e9di. Storing a sparse table with 0 (1) worst case access time. Journal of the ACM (JACM), 31(3):538--544, 1984."},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0049398"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795294165"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369909"},{"key":"e_1_2_2_61_1","volume-title":"A space-efficient dynamic dictionary for multisets with constant time operations. arXiv preprint arXiv:2005.02143","author":"Bercea Ioana Oriana","year":"2020","unstructured":"Ioana Oriana Bercea and Guy Even. A space-efficient dynamic dictionary for multisets with constant time operations. arXiv preprint arXiv:2005.02143, 2020."},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/1070432.1070548"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626721","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626721","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T13:00:34Z","timestamp":1755867634000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626721"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,8]]},"references-count":62,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,8]]}},"alternative-id":["10.1145\/3626721"],"URL":"https:\/\/doi.org\/10.1145\/3626721","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2023,12,8]]}}}