{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:01:22Z","timestamp":1760241682807,"version":"build-2065373602"},"reference-count":36,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2018,7,2]],"date-time":"2018-07-02T00:00:00Z","timestamp":1530489600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National key R&amp;D project of ministry of science and technology of China","award":["2017YFB0306400"],"award-info":[{"award-number":["2017YFB0306400"]}]},{"DOI":"10.13039\/501100001809","name":"the National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61562056"],"award-info":[{"award-number":["61562056"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>Regardless of the type of data, traditional Bloom filters treat each element of a set as a string, and by iterating every character of the string, they discretize all data randomly and uniformly. However, with the data size and dimension increases, these variants are inefficient. To better discretize vectors with high numerical dimensions, this paper improves the string hashes to integer hashes. Based on the integer hashes and a counter array, we propose a new variant\u2014high-dimensional bloom filter (HDBF)\u2014to extend the Bloom filter into high-dimensional spaces, which can represent and query numerical vectors of a big set with a low false positive probability. This paper theoretically analyzes the feasibility of the integer hashes on discretizing data and discusses the relationship of parameters of the HDBF. The experiments illustrate that, in high-dimensional numerical spaces, the HDBF shows better randomness on distribution and entropy than that of the counting Bloom filter. Compared with the parallel Bloom filters, for a fixed false positive probability, the HDBF displays time-space overheads, and is more suitable to deal with the numerical vectors with high dimensions.<\/jats:p>","DOI":"10.3390\/info9070159","type":"journal-article","created":{"date-parts":[[2018,7,2]],"date-time":"2018-07-02T10:56:52Z","timestamp":1530529012000},"page":"159","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Bloom Filter for High Dimensional Vectors"],"prefix":"10.3390","volume":"9","author":[{"given":"Chunyan","family":"Shuai","sequence":"first","affiliation":[{"name":"Faculty of Transportation Engineering, Kunming University of Science and Technology, Kunming 650221, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hengcheng","family":"Yang","sequence":"additional","affiliation":[{"name":"Faculty of Electric Power Engineering, Kunming University of Science and Technology, Kunming 650221, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xin","family":"Ouyang","sequence":"additional","affiliation":[{"name":"Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650221, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zeweiyi","family":"Gong","sequence":"additional","affiliation":[{"name":"Faculty of Electric Power Engineering, Kunming University of Science and Technology, Kunming 650221, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,7,2]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Hunt, W., Mark, W.R., and Stoll, G. (2006, January 18\u201320). Fast kd-tree construction with an adaptive error-bounded heuristic. Proceedings of the IEEE Symposium on Interactive Ray Tracing, Salt Lake City, UT, USA.","DOI":"10.1109\/RT.2006.280218"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Burkhardt, S., Crauser, A., Ferragina, P., Lenhof, H., Rivals, E., and Vingron, M. (1999, January 11\u201314). q-gram based database searching using a suffix array (QUASAR). Proceedings of the Third Annual International Conference on Computational Molecular Biology, Lyon, France.","DOI":"10.1145\/299432.299460"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/362686.362692","article-title":"Space\/Time Trade-Offs in Hash Coding with Allowable Errors","volume":"13","author":"Burton","year":"1970","journal-title":"Commun. ACM"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1080\/15427951.2004.10129096","article-title":"Network applications of bloom filters: A survey","volume":"1","author":"Broder","year":"2004","journal-title":"Internet Math."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1109\/SURV.2011.031611.00024","article-title":"Theory and practice of bloom filters for distributed systems","volume":"14","author":"Tarkoma","year":"2012","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Ju, H.M., and Lim, H. (2016). New Approach for Efficient IP Address Lookup Using a Bloom filter in Trie-Based Algorithms. IEEE Trans. Comput., 65.","DOI":"10.1109\/TC.2015.2444850"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Kwon, M., Reviriego, P., and Pontarelli, S. (2016, January 10\u201314). A length-aware cuckoo filter for faster IP lookup. Proceedings of the 2016 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), San Francisco, CA, USA.","DOI":"10.1109\/INFCOMW.2016.7562258"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.comcom.2015.05.002","article-title":"isBF: Scalable in-packet bloom filter based multicast","volume":"70","author":"Nikolaevskiy","year":"2015","journal-title":"Comput. Commun."},{"key":"ref_9","first-page":"305","article-title":"A fast and accurate hardware string matching module with Bloom filters","volume":"28","author":"Zengin","year":"2017","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1008","DOI":"10.1109\/TVLSI.2008.2012011","article-title":"Realizing a sub-linear time string-matching algorithm with a hardware accelerator using bloom filters","volume":"17","author":"Lin","year":"2009","journal-title":"IEEE Trans. Very Large Scale Integr. Syst."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"2956","DOI":"10.1109\/TPDS.2014.2363458","article-title":"Cooperative Web Caching Using Dynamic Interest-Tagged filtered Bloom filters","volume":"26","author":"Alexander","year":"2015","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1463","DOI":"10.1109\/TNET.2013.2281614","article-title":"Denial-of-service attacks in bloom-filter-based forwarding","volume":"22","author":"Antikainen","year":"2014","journal-title":"Trans. Netw. IEEE\/ACM"},{"key":"ref_13","unstructured":"Parthasarathy, S., and Kundur, D. (May, January 29). Bloom filter based intrusion detection for smart grid SCADA. Proceedings of the IEEE Canadian Conference on Electrical & Computer Engineering (CCECE), Montreal, QC, Canada."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Meghana, V., Suresh, M., Sandhya, S., Aparna, R., and Gururaj, C. (2016, January 20\u201321). SoC implementation of network intrusion detection using counting bloom filter. Proceedings of the 2016 IEEE International Conference on Recent Trends in Electronics, Information & Communication Technology (RTEICT), Bangalore, India.","DOI":"10.1109\/RTEICT.2016.7808154"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Aldwairi, M., and Al-Khamaiseh, K. (2015, January 21\u201323). Exhaust: Optimizing Wu-Manber pattern matching for intrusion detection using Bloom filters. Proceedings of the IEEE Web Applications and Networking, Sousse, Tunisia.","DOI":"10.1109\/WSWAN.2015.7209081"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1016\/j.ipl.2008.05.018","article-title":"On the false-positive rate of Bloom filters","volume":"108","author":"Bose","year":"2008","journal-title":"Inf. Process. Lett."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"944","DOI":"10.1016\/j.ipl.2010.07.024","article-title":"A new analysis of the false positive rate of a Bloom filter","volume":"110","author":"Christensen","year":"2010","journal-title":"Inf. Process. Lett."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1109\/TNET.2014.2306060","article-title":"The bloom paradox: When not to use a Bloom filter","volume":"23","author":"Rottenstreich","year":"2015","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Lim, H., Lee, J., and Yim, C. (2015). Complement Bloom filter for Identifying True Positiveness of a Bloom filter. IEEE Commun. Lett., 19.","DOI":"10.1109\/LCOMM.2015.2478462"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1109\/90.851975","article-title":"Summary cache: A scalable wide-area Web cache sharing protocol","volume":"8","author":"Fan","year":"2000","journal-title":"Trans. Netw. IEEE\/ACM"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1092","DOI":"10.1109\/TNET.2013.2272604","article-title":"The variable-increment counting Bloom filter","volume":"22","author":"Rottenstreich","year":"2014","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1986","DOI":"10.1109\/TPDS.2013.223","article-title":"Bloom filter based associative deletion","volume":"25","author":"Qian","year":"2014","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"408","DOI":"10.14778\/2876473.2876476","article-title":"A shifting bloom filter framework for set queries","volume":"9","author":"Yang","year":"2016","journal-title":"Proc. VLDB Endow."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/j.ipl.2006.10.007","article-title":"Scalable bloom filters","volume":"101","author":"Almeida","year":"2007","journal-title":"Inf. Process. Lett."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1109\/TKDE.2009.57","article-title":"The Dynamic Bloom filters","volume":"22","author":"Guo","year":"2010","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_26","first-page":"1","article-title":"Par-BF: A Parallel Partitioned Bloom filter for Dynamic Data Sets","volume":"30","author":"Liu","year":"2015","journal-title":"Int. J. High Perform. Comput. Appl."},{"key":"ref_27","first-page":"241","article-title":"Split bloom filter","volume":"32","author":"Xiao","year":"2004","journal-title":"Acta Electron. Sin."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1109\/TPDS.2009.39","article-title":"Using Parallel Bloom filters for Multiattribute Representation on Network Services","volume":"21","author":"Xiao","year":"2010","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Kirsch, A., and Mitzenmacher, M. (2006, January 22\u201326). Distance-sensitive bloom filters. Proceedings of the 8th Workshop on Algorithm Engineering and Experiments\/3rd Workshop on Analytic Algorithms and Combinatorics, Miami, FL, USA.","DOI":"10.1137\/1.9781611972863.4"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1109\/TC.2011.108","article-title":"Locality-Sensitive Bloom filter for Approximate Membership Query","volume":"61","author":"Hua","year":"2012","journal-title":"IEEE Trans. Comput."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"3500","DOI":"10.1109\/TC.2015.2401011","article-title":"Multi-Granularity Locality-Sensitive Bloom filter","volume":"64","author":"Qian","year":"2015","journal-title":"IEEE Trans. Comput."},{"key":"ref_32","first-page":"2125","article-title":"Integer-Granularity Locality-Sensitive Bloom filter","volume":"20","author":"Qian","year":"2016","journal-title":"IEEE Trans. Comput."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Wu, W., Wu, S., Zhang, L., Zou, J., and Dong, L. (2013, January 27). LHash: A Light weight Hash Function. Proceedings of the International Conference on Information Security and Cryptology, Guangzhou, China.","DOI":"10.1007\/978-3-319-12087-4_19"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/s00145-007-9002-x","article-title":"Cryptographic Hash Functions from Expander Graphs","volume":"22","author":"Charles","year":"2009","journal-title":"J. Cryptol."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Fagin, R., Kumar, R., and Sivakumar, D. (2003, January 9\u201312). Efficient similarity search and classification via rank aggregation. Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, CA, USA.","DOI":"10.1145\/872757.872795"},{"key":"ref_36","unstructured":"(2018, June 19). Datasets for Approximate Nearest Neighbor Search. Available online: http:\/\/corpus-texmex.irisa.fr\/."}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/9\/7\/159\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:10:56Z","timestamp":1760195456000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/9\/7\/159"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,2]]},"references-count":36,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2018,7]]}},"alternative-id":["info9070159"],"URL":"https:\/\/doi.org\/10.3390\/info9070159","relation":{},"ISSN":["2078-2489"],"issn-type":[{"type":"electronic","value":"2078-2489"}],"subject":[],"published":{"date-parts":[[2018,7,2]]}}}