{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:12:49Z","timestamp":1750306369791,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,9,21]],"date-time":"2016-09-21T00:00:00Z","timestamp":1474416000000},"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":["61402509"],"award-info":[{"award-number":["61402509"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2016,9,21]]},"abstract":"<jats:p>\n            Bloom filters are frequently used to to check the membership of an item in a set. However, Bloom filters face a dilemma: the transmission bandwidth and the accuracy cannot be optimized simultaneously. This dilemma is particularly severe for transmitting Bloom filters to remote nodes when the network bandwidth is limited. We propose a novel Bloom filter called\n            <jats:bold>BloomTree<\/jats:bold>\n            that consists of a tree-structured organization of smaller Bloom filters, each using a set of independent hash functions. BloomTree spreads items across levels that are compressed to reduce the transmission bandwidth need. We show how to find optimal configurations for BloomTree and investigate in detail by how much BloomTree outperforms the standard Bloom filter or the compressed Bloom filter. Finally, we use the intersection of BloomTrees to predict the set intersection, decreasing the false-positive probabilities by several orders of magnitude compared to both the compressed Bloom filter and the standard Bloom filter.\n          <\/jats:p>","DOI":"10.1145\/2940324","type":"journal-article","created":{"date-parts":[[2016,9,21]],"date-time":"2016-09-21T13:13:56Z","timestamp":1474463636000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["False-Positive Probability and Compression Optimization for Tree-Structured Bloom Filters"],"prefix":"10.1145","volume":"1","author":[{"given":"Yongquan","family":"Fu","sequence":"first","affiliation":[{"name":"National Key Laboratory for Parallel and Distributed Processing; College of Computer Science, National University of Defense Technology, Hunan Province, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ernst","family":"Biersack","sequence":"additional","affiliation":[{"name":"Caipy, Valbonne, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,9,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556556"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060840"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879175"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.05.018"},{"key":"e_1_2_1_6_1","first-page":"4","article-title":"Network applications of bloom filters: A survey","volume":"1","author":"Broder Andrei Z.","year":"2003","unstructured":"Andrei Z. Broder and Michael Mitzenmacher . 2003 . Network applications of bloom filters: A survey . Internet Mathematics 1 , 4 . Andrei Z. Broder and Michael Mitzenmacher. 2003. Network applications of bloom filters: A survey. Internet Mathematics 1, 4.","journal-title":"Internet Mathematics"},{"key":"e_1_2_1_7_1","volume-title":"Andersen","author":"Cha Sang Kil","year":"2010","unstructured":"Sang Kil Cha , Iulian Moraru , Jiyong Jang , John Truelove , David Brumley , and David G . Andersen . 2010 . SplitScreen: Enabling efficient, distributed malware detection. In Proceedings of NSDI. 377--390. Sang Kil Cha, Iulian Moraru, Jiyong Jang, John Truelove, David Brumley, and David G. Andersen. 2010. SplitScreen: Enabling efficient, distributed malware detection. In Proceedings of NSDI. 377--390."},{"volume-title":"NetTube: Exploring social networks for peer-to-peer short video sharing","author":"Cheng Xu","key":"e_1_2_1_8_1","unstructured":"Xu Cheng and Jiangchuan Liu . 2009. NetTube: Exploring social networks for peer-to-peer short video sharing . In IEEE INFOCOM. 1152--1160. Xu Cheng and Jiangchuan Liu. 2009. NetTube: Exploring social networks for peer-to-peer short video sharing. In IEEE INFOCOM. 1152--1160."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.07.024"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2015.01.002"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199809)13:2%3C99::AID-RSA1%3E3.0.CO;2-M"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2018436.2018462"},{"key":"e_1_2_1_13_1","volume-title":"Ullman","author":"Fang Min","year":"1998","unstructured":"Min Fang , Narayanan Shivakumar , Hector Garcia-Molina , Rajeev Motwani , and Jeffrey D . Ullman . 1998 . Computing Iceberg queries efficiently. In Proceedings of VLDB. 299--310. Min Fang, Narayanan Shivakumar, Hector Garcia-Molina, Rajeev Motwani, and Jeffrey D. Ullman. 1998. Computing Iceberg queries efficiently. In Proceedings of VLDB. 299--310."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICC.2008.1090"},{"key":"e_1_2_1_15_1","volume-title":"7th International ICST Conference on Communications and Networking in China (CHINACOM\u201912)","author":"Fu Yongquan","year":"2012","unstructured":"Yongquan Fu and Yijie Wang . 2012 . BCE: A privacy-preserving common-friend estimation method for distributed online social networks without cryptography . In 7th International ICST Conference on Communications and Networking in China (CHINACOM\u201912) . 212--217. Yongquan Fu and Yijie Wang. 2012. BCE: A privacy-preserving common-friend estimation method for distributed online social networks without cryptography. In 7th International ICST Conference on Communications and Networking in China (CHINACOM\u201912). 212--217."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2012.11.001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2014.02.020"},{"volume-title":"Genetic Algorithms in Search, Optimization and Machine Learning","author":"Goldberg David E.","key":"e_1_2_1_18_1","unstructured":"David E. Goldberg . 1989. Genetic Algorithms in Search, Optimization and Machine Learning . Addison-Wesley Longman Publishing Co., Inc. , Boston, MA . David E. Goldberg. 1989. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston, MA."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1254882.1254916"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989551"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v33:2"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063643"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2011.6089061"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2007.10129136"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2805789.2805800"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2002.803864"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of SODA. 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 SODA. 746--755 . Michael Mitzenmacher and Salil Vadhan. 2008. Why simple hash functions work: Exploiting the entropy in a data stream. In Proceedings of SODA. 746--755."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498698.1594230"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2011.031611.00024"},{"volume-title":"Retrieved","year":"2016","key":"e_1_2_1_31_1","unstructured":"wikipedia.org. 2016 a. Integer Programming . Retrieved August 25, 2016 from https:\/\/en.wikipedia.org\/ wiki\/Integer_programming. wikipedia.org. 2016a. Integer Programming. Retrieved August 25, 2016 from https:\/\/en.wikipedia.org\/ wiki\/Integer_programming."},{"volume-title":"Retrieved","year":"2016","key":"e_1_2_1_32_1","unstructured":"wikipedia.org. 2016 b. Multi-objective optimization . Retrieved August 25, 2016 from https:\/\/en.wikipedia.org\/ wiki\/Multi-objective_optimization. wikipedia.org. 2016b. Multi-objective optimization. Retrieved August 25, 2016 from https:\/\/en.wikipedia.org\/ wiki\/Multi-objective_optimization."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2876473.2876476"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2014.6848077"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1658939.1658975"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2785956.2787503"}],"container-title":["ACM Transactions on Modeling and Performance Evaluation of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2940324","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2940324","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:27Z","timestamp":1750222587000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2940324"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,21]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,9,21]]}},"alternative-id":["10.1145\/2940324"],"URL":"https:\/\/doi.org\/10.1145\/2940324","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"type":"print","value":"2376-3639"},{"type":"electronic","value":"2376-3647"}],"subject":[],"published":{"date-parts":[[2016,9,21]]},"assertion":[{"value":"2015-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}