{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,2]],"date-time":"2025-03-02T05:56:59Z","timestamp":1740895019811,"version":"3.38.0"},"reference-count":43,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2016,7,28]],"date-time":"2016-07-28T00:00:00Z","timestamp":1469664000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of High Performance Computing Applications"],"published-print":{"date-parts":[[2016,8]]},"abstract":"<jats:p> Compared with a hash table, a Bloom filter (BF) is more space efficient for supporting fast matching through a controllable and acceptable false positive probability. The space size of the basic BF is predetermined based on the expected number of elements to be stored. However, we cannot predict the space scale of a BF for dynamic sets. It is still challenging for the two existing solutions, scalable BF (SBF) and dynamic BF (DBF), to manipulate dynamic data sets with low memory overhead but achieving high performance. This article presents a partitioned BF (Par-BF) for dynamic data sets. Compared with DBF and SBF, Par-BF is able to leverage a sweet spot between high performance and low overhead by a group of formulas to support fast concurrent matching. Specifically, the size and the range of the false positive probability in Par-BF can be deliberately derived. From our trace-driven experimental results, the input\/output operations per second of Par-BF outperforms that of DBF and SBF by 10\u00d7 to 14\u00d7 and by 3\u00d7 to 8\u00d7, respectively. Besides, through our proposed garbage collection policy, Par-BF consumes less than half of the memory usage of SBF. <\/jats:p>","DOI":"10.1177\/1094342015618452","type":"journal-article","created":{"date-parts":[[2015,12,25]],"date-time":"2015-12-25T02:03:11Z","timestamp":1451008991000},"page":"259-275","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":3,"title":["Par-BF: A parallel partitioned Bloom filter for dynamic data sets"],"prefix":"10.1177","volume":"30","author":[{"given":"Yi","family":"Liu","sequence":"first","affiliation":[{"name":"Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen, China"}]},{"given":"Xiongzi","family":"Ge","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN, USA"}]},{"given":"David Hung-Chang","family":"Du","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN, USA"}]},{"given":"Xiaoxia","family":"Huang","sequence":"additional","affiliation":[{"name":"Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen, China"}]}],"member":"179","published-online":{"date-parts":[[2016,7,28]]},"reference":[{"key":"bibr1-1094342015618452","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687731"},{"key":"bibr2-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.10.007"},{"key":"bibr3-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1145\/1555349.1555355"},{"key":"bibr4-1094342015618452","first-page":"29","volume-title":"Proceedings of the 7th USENIX conference on networked systems design and implementation","volume":"10","author":"Anand A","year":"2010"},{"key":"bibr5-1094342015618452","unstructured":"Appleby A (2009) Murmurhash 64 bits variant. Available at: https:\/\/sites.google.com\/site\/murmurhash\/ (accessed 1 June 2013)."},{"key":"bibr6-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1145\/320064.320065"},{"key":"bibr7-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"bibr8-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_61"},{"key":"bibr9-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129096"},{"key":"bibr10-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511803888"},{"key":"bibr11-1094342015618452","first-page":"30","volume-title":"Proceedings of the fifteenth annual ACM-SIAM symposium on discrete algorithms","author":"Chazelle B","year":"2004"},{"key":"bibr12-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872787"},{"key":"bibr13-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"bibr14-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTER.2011.49"},{"key":"bibr15-1094342015618452","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1921015"},{"key":"bibr16-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2011.44"},{"key":"bibr17-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791194094"},{"key":"bibr18-1094342015618452","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920908"},{"key":"bibr19-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1109\/90.851975"},{"key":"bibr20-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1972.5009071"},{"key":"bibr21-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"bibr22-1094342015618452","first-page":"1","volume":"2007","author":"Gantz J","year":"2012","journal-title":"IDC iView: IDC Analyze the Future"},{"key":"bibr23-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1145\/2619239.2631426"},{"key":"bibr24-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.57"},{"key":"bibr25-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1145\/1269899.1254916"},{"key":"bibr26-1094342015618452","first-page":"2304","volume-title":"2006 IEEE International Symposium on Information Theory","author":"Jehoshua B","year":"2006"},{"key":"bibr27-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_42"},{"key":"bibr28-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1145\/2401603.2401626"},{"key":"bibr29-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2011.5934921"},{"key":"bibr30-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2012.6232390"},{"key":"bibr31-1094342015618452","first-page":"149","volume-title":"VLDB\u201986 Twelfth International Conference on Very Large Data Bases","author":"Mackert LF","year":"1986"},{"key":"bibr32-1094342015618452","doi-asserted-by":"publisher","DOI":"10.14236\/ewic\/VOCS2010.6"},{"key":"bibr33-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1109\/AINA.2007.80"},{"key":"bibr34-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2002.803864"},{"key":"bibr35-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1109\/32.52778"},{"key":"bibr36-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"bibr37-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2011.6114208"},{"key":"bibr38-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1145\/2391229.2391233"},{"key":"bibr39-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1145\/1030083.1030089"},{"key":"bibr40-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1145\/1080091.1080114"},{"key":"bibr41-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2011.031611.00024"},{"key":"bibr42-1094342015618452","doi-asserted-by":"publisher","DOI":"10.1145\/1658939.1658975"},{"key":"bibr43-1094342015618452","first-page":"269","volume-title":"Proceedings of the Fast\u201908","volume":"8","author":"Zhu B","year":"2008"}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342015618452","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/1094342015618452","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342015618452","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T21:23:20Z","timestamp":1740864200000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/1094342015618452"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,28]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,8]]}},"alternative-id":["10.1177\/1094342015618452"],"URL":"https:\/\/doi.org\/10.1177\/1094342015618452","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"type":"print","value":"1094-3420"},{"type":"electronic","value":"1741-2846"}],"subject":[],"published":{"date-parts":[[2016,7,28]]}}}