Bloom Filters(BFs)are compact and probabilistic data structures designed for efficient set membership queries.They offer high query and storage efficiency,making them particularly useful in network and distributed sys...Bloom Filters(BFs)are compact and probabilistic data structures designed for efficient set membership queries.They offer high query and storage efficiency,making them particularly useful in network and distributed systems.However,the scalability of BFs in accommodating“big data”is limited by increased false positive rates,inflexible hash functions,and inefficient matching with dynamic datasets.To address these limitations,we introduce the Extensible Bloom Filter(EBF),which incorporates a flexible expansion mechanism and an adaptive hash function generation scheme.The EBF design features a set of BF vectors that expand according to the rate of incoming data,with each vector sized to suit the characteristics of the data.Adaptive hash functions,derived from common base matrices,streamline the process by leveraging strong inter-hash relationships.This reduces overhead and simplifies queries across multiple BF vector sizes.Performance evaluations have shown that the EBF consistently achieves a low false positive rate and minimal query time,even amid dynamic data arrivals and large data sets.With its extensibility and adaptability,the EBF provides a robust solution for applications requiring dynamic set representations with stringent accuracy requirements.It enhances the capabilities of network and distributed systems,making them more efficient in handling complex data scenarios.展开更多
基金supported in part by the National Natural Science Foundation of China(Nos.62025201 and 62472167)in part by the Hunan Provincial Natural Science Foundation of China(Nos.2024JJ3014 and 2024JJ5165)in part by the Key Research and Development Program of Hunan Province(No.2023GK2001).
文摘Bloom Filters(BFs)are compact and probabilistic data structures designed for efficient set membership queries.They offer high query and storage efficiency,making them particularly useful in network and distributed systems.However,the scalability of BFs in accommodating“big data”is limited by increased false positive rates,inflexible hash functions,and inefficient matching with dynamic datasets.To address these limitations,we introduce the Extensible Bloom Filter(EBF),which incorporates a flexible expansion mechanism and an adaptive hash function generation scheme.The EBF design features a set of BF vectors that expand according to the rate of incoming data,with each vector sized to suit the characteristics of the data.Adaptive hash functions,derived from common base matrices,streamline the process by leveraging strong inter-hash relationships.This reduces overhead and simplifies queries across multiple BF vector sizes.Performance evaluations have shown that the EBF consistently achieves a low false positive rate and minimal query time,even amid dynamic data arrivals and large data sets.With its extensibility and adaptability,the EBF provides a robust solution for applications requiring dynamic set representations with stringent accuracy requirements.It enhances the capabilities of network and distributed systems,making them more efficient in handling complex data scenarios.
