Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2023 Sep 9;23(18):7775.
doi: 10.3390/s23187775.

PSBF: p-adic Integer Scalable Bloom Filter

Wenlong Yi  1 , Chuang Wang  1 , Qiliang Xie  1 , Yingding Zhao  1 , Jing Jia  1
Affiliations

PSBF: p-adic Integer Scalable Bloom Filter

Wenlong Yi et al. Sensors (Basel). .

Abstract

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 p-adic integers to introduce an innovative approach for dynamically expanding the p-adic 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 p-adic 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.

Keywords: access optimization; bloom filter; number theory; p-adic; scalable.

PubMed Disclaimer

Conflict of interest statement

The authors declare no conflict of interest.

Figures

Figure 1
Figure 1
Data structure of a standard bloom filter.
Figure 2
Figure 2
Data structure of 3-adic Integer Scalable Bloom Filter.
Figure 3
Figure 3
Storage status of the PSBF.
Figure 4
Figure 4
Time comparison of selecting different expansion prime numbers p from 2 to 31 intervals. (a) Insertion operation; (b) query operation.
Figure 5
Figure 5
Time comparison of eight various hash functions. (a) Insertion operation; (b) query operation.
Figure 6
Figure 6
Time comparison of the different bloom filters. (a) Insertion operation; (b) query operation.
Figure 7
Figure 7
Storage space usage rate of four various bloom filters.
Figure 8
Figure 8
Number of misjudgments of four different bloom filters.
See this image and copyright information in PMC

References

    1. Singh A., Garg S., Kaur K., Batra S., Kumar N., Choo K.-K.R. Fuzzy-folded bloom filter-as-a-service for big data storage in the cloud. IEEE Trans. Ind. Inform. 2018;15:2338–2348. doi: 10.1109/TII.2018.2850053. - DOI
    1. Singh A., Garg S., Batra S., Kumar N., Rodrigues J.J. Bloom filter based optimization scheme for massive data handling in IoT environment. Future Gener. Comput. Syst. 2018;82:440–449. doi: 10.1016/j.future.2017.12.016. - DOI
    1. Yang C., Tao X., Zhao F., Wang Y. Secure data transfer and deletion from counting bloom filter in cloud computing. Chin. J. Electron. 2020;29:273–280. doi: 10.1049/cje.2020.02.015. - DOI
    1. Luo L., Guo D., Ma R.T., Rottenstreich O., Luo X. Optimizing bloom filter: Challenges, solutions, and comparisons. IEEE Commun. Surv. Tutor. 2018;21:1912–1949. doi: 10.1109/COMST.2018.2889329. - DOI
    1. Hou R., Zhang L., Wu T., Mao T., Luo J. Bloom-filter-based request node collaboration caching for named data networking. Clust. Comput. 2019;22:6681–6692. doi: 10.1007/s10586-018-2403-9. - DOI

LinkOut - more resources