{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:14:49Z","timestamp":1750220089335,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T00:00:00Z","timestamp":1646784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62025201, 61972144"],"award-info":[{"award-number":["62025201, 61972144"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF Electrical, Communications and Cyber Systems","award":["1731238 and 2030063"],"award-info":[{"award-number":["1731238 and 2030063"]}]},{"name":"NSF Communication and Information Foundations","award":["2007313"],"award-info":[{"award-number":["2007313"]}]},{"name":"Hunan Provincial Innovation Foundation for Postgraduate Studies","award":["CX20200437"],"award-info":[{"award-number":["CX20200437"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>\n            Multi-set membership query is a fundamental issue for network functions such as packet processing and state machines monitoring. Given the rigid query speed and memory requirements, it would be promising if a multi-set query algorithm can be designed based on Bloom filter (BF), a space-efficient probabilistic data structure. However, existing efforts on multi-set query based on BF suffer from at least one of the following drawbacks: low query speed, low query accuracy, limitation in only supporting insertion and query operations, or limitation in the set size. To address the issues, we design a novel B\n            <jats:italic>\n              <jats:sub>h<\/jats:sub>\n            <\/jats:italic>\n            sequence-based Bloom filter (B\n            <jats:italic>\n              <jats:sub>h<\/jats:sub>\n            <\/jats:italic>\n            BF) for multi-set query, which supports four operations: insertion, query, deletion, and update. In B\n            <jats:italic>\n              <jats:sub>h<\/jats:sub>\n            <\/jats:italic>\n            BF, the set ID is encoded as a code in a B\n            <jats:italic>\n              <jats:sub>h<\/jats:sub>\n            <\/jats:italic>\n            sequence. Exploiting good properties of B\n            <jats:italic>\n              <jats:sub>h<\/jats:sub>\n            <\/jats:italic>\n            sequences, we can correctly decode the BF cells to obtain the set IDs even when the number of hash collisions is high, which brings high query accuracy. In B\n            <jats:italic>\n              <jats:sub>h<\/jats:sub>\n            <\/jats:italic>\n            BF, we propose two strategies to further speed up the query speed and increase the query accuracy. On the theoretical side, we analyze the false positive and classification failure rate of our B\n            <jats:italic>\n              <jats:sub>h<\/jats:sub>\n            <\/jats:italic>\n            BF. Our results from extensive experiments over two real datasets demonstrate that B\n            <jats:italic>\n              <jats:sub>h<\/jats:sub>\n            <\/jats:italic>\n            BF significantly advances state-of-the-art multi-set query algorithms.\n          <\/jats:p>","DOI":"10.1145\/3502735","type":"journal-article","created":{"date-parts":[[2022,3,10]],"date-time":"2022-03-10T14:03:20Z","timestamp":1646921000000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["B\n            <sub>\n              <i>h<\/i>\n            <\/sub>\n            BF: A Bloom Filter Using B\n            <sub>\n              <i>h<\/i>\n            <\/sub>\n            Sequences for Multi-set Membership Query"],"prefix":"10.1145","volume":"16","author":[{"given":"Shuyu","family":"Pei","sequence":"first","affiliation":[{"name":"the College of Computer Science and Electronic Engineering, Hunan University, Hunan Province, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kun","family":"Xie","sequence":"additional","affiliation":[{"name":"the College of Computer Science and Electronic Engineering, Hunan University, Hunan Province, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xin","family":"Wang","sequence":"additional","affiliation":[{"name":"the Department of Electrical and Computer Engineering, the State University of New Yorkat Stony Brook, Stony Brook, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gaogang","family":"Xie","sequence":"additional","affiliation":[{"name":"the Computer Network Information Center, Chinese Academy of Sciences, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kenli","family":"Li","sequence":"additional","affiliation":[{"name":"the College of Computer Science and Electronic Engineering, Hunan University, Changsha, Hunan Province, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Li","sequence":"additional","affiliation":[{"name":"the College of Computer Science and Electronic Engineering, Hunan University, Changsha, Hunan Province, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanbiao","family":"Li","sequence":"additional","affiliation":[{"name":"the Computer Network Information Center, Chinese Academy of Sciences, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jigang","family":"Wen","sequence":"additional","affiliation":[{"name":"the Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,3,9]]},"reference":[{"unstructured":"Hash website. Retrieved on 11 Jan. 2022 from https:\/\/guava.dev\/releases\/19.0\/api\/docs\/com\/google\/common\/hash\/Hashing.html.","key":"e_1_3_1_2_2"},{"doi-asserted-by":"publisher","key":"e_1_3_1_3_2","DOI":"10.1145\/362686.362692"},{"doi-asserted-by":"publisher","key":"e_1_3_1_4_2","DOI":"10.1145\/1151659.1159950"},{"key":"e_1_3_1_5_2","volume-title":"Theorems in the Additive Theory of Numbers","author":"Bose Raj Chandra","year":"1960","unstructured":"Raj Chandra Bose and Sarvadaman Chowla. 1960. Theorems in the Additive Theory of Numbers. Technical Report. North Carolina State University. Dept. of Statistics."},{"unstructured":"The CAIDA Anonymized Internet Traces. Retrieved on 11 Jan. 2022 from http:\/\/www.caida.org\/data\/.","key":"e_1_3_1_6_2"},{"doi-asserted-by":"publisher","key":"e_1_3_1_7_2","DOI":"10.1109\/INFCOM.2004.1354643"},{"doi-asserted-by":"publisher","key":"e_1_3_1_8_2","DOI":"10.1016\/j.is.2015.01.002"},{"doi-asserted-by":"publisher","key":"e_1_3_1_9_2","DOI":"10.1145\/2896377.2901451"},{"doi-asserted-by":"publisher","key":"e_1_3_1_10_2","DOI":"10.1109\/TIT.2004.824915"},{"doi-asserted-by":"publisher","key":"e_1_3_1_11_2","DOI":"10.1109\/90.851975"},{"doi-asserted-by":"publisher","key":"e_1_3_1_12_2","DOI":"10.1109\/Allerton.2011.6120248"},{"doi-asserted-by":"publisher","key":"e_1_3_1_13_2","DOI":"10.1109\/TNET.2011.2173351"},{"doi-asserted-by":"publisher","key":"e_1_3_1_14_2","DOI":"10.1109\/TNET.2018.2869851"},{"doi-asserted-by":"publisher","key":"e_1_3_1_15_2","DOI":"10.1109\/COMST.2018.2889329"},{"doi-asserted-by":"publisher","key":"e_1_3_1_16_2","DOI":"10.1109\/INFOCOM.2019.8737454"},{"unstructured":"The MAWI Working Group Traffic Archive. [n.d.]. Retrieved on 11 Jan. 2022 from http:\/\/mawi.nezu.wide.ad.jp\/mawi\/.","key":"e_1_3_1_17_2"},{"doi-asserted-by":"publisher","key":"e_1_3_1_18_2","DOI":"10.1109\/TKDE.2016.2535286"},{"doi-asserted-by":"publisher","key":"e_1_3_1_19_2","DOI":"10.1109\/TNET.2018.2850536"},{"doi-asserted-by":"publisher","key":"e_1_3_1_20_2","DOI":"10.1109\/TNET.2016.2536618"},{"doi-asserted-by":"publisher","key":"e_1_3_1_21_2","DOI":"10.1109\/TNET.2013.2272604"},{"doi-asserted-by":"publisher","key":"e_1_3_1_22_2","DOI":"10.1007\/BF01455900"},{"doi-asserted-by":"publisher","key":"e_1_3_1_23_2","DOI":"10.1109\/INFOCOM.2019.8737499"},{"doi-asserted-by":"publisher","key":"e_1_3_1_24_2","DOI":"10.1109\/SURV.2011.031611.00024"},{"doi-asserted-by":"publisher","key":"e_1_3_1_25_2","DOI":"10.1109\/ICDE.2019.00105"},{"doi-asserted-by":"publisher","key":"e_1_3_1_26_2","DOI":"10.1109\/TCC.2014.2385063"},{"doi-asserted-by":"publisher","key":"e_1_3_1_27_2","DOI":"10.1109\/TNET.2017.2730227"},{"doi-asserted-by":"publisher","key":"e_1_3_1_28_2","DOI":"10.1145\/2619239.2626297"},{"doi-asserted-by":"publisher","key":"e_1_3_1_29_2","DOI":"10.1109\/INFOCOM.2014.6848077"},{"doi-asserted-by":"publisher","key":"e_1_3_1_30_2","DOI":"10.1145\/1658939.1658975"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3502735","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3502735","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:47Z","timestamp":1750183787000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3502735"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,9]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3502735"],"URL":"https:\/\/doi.org\/10.1145\/3502735","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2022,3,9]]},"assertion":[{"value":"2021-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}