Yi Wenlong, Wang Chuang, Xie Qiliang, Zhao Yingding, Jia Jing
School of Software, Jiangxi Agricultural University, Nanchang 330045, China.
Sensors (Basel). 2023 Sep 9;23(18):7775. doi: 10.3390/s23187775.
Given the challenges associated with the dynamic expansion of the conventional bloom filter's capacity, the prevalence of false positives, and the subpar access performance, this study employs the algebraic and topological characteristics of integers to introduce an innovative approach for dynamically expanding the Integer Scalable Bloom Filter (PSBF). The proposed method involves converting the target element into an integer using a string hash function, followed by the conversion of said integer into a integer through algebraic properties. This process automatically establishes the topological tree access structure of the PSBF. The experiment involved a comparison of access performance among the standard bloom filter, dynamic bloom filter, and scalable bloom filter. The findings indicate that the PSBF offers advantages such as avoidance of a linear storage structure, enhanced efficiency in element insertion and query, improved storage space utilization, and reduced likelihood of false positives. Consequently, the PSBF presents a novel approach to the dynamic extensibility of bloom filters.
鉴于传统布隆过滤器在容量动态扩展、误报率高以及访问性能欠佳等方面存在的挑战，本研究利用整数的代数和拓扑特性，引入一种创新方法来动态扩展整数可扩展布隆过滤器（PSBF）。所提出的方法包括使用字符串哈希函数将目标元素转换为整数，然后通过代数性质将该整数转换为另一个整数。此过程自动建立了PSBF的拓扑树访问结构。实验对标准布隆过滤器、动态布隆过滤器和可扩展布隆过滤器的访问性能进行了比较。结果表明，PSBF具有避免线性存储结构、提高元素插入和查询效率、改善存储空间利用率以及降低误报可能性等优点。因此，PSBF为布隆过滤器的动态可扩展性提供了一种新方法。
