Name
Abstract | ||
|---|---|---|
A Bloom filter is an effective, space-efficient data structure for concisely representing a set, and supporting approximate membership queries. Traditionally, the Bloom filter and its variants just focus on how to represent a static set and decrease the false positive probability to a sufficiently low level. By investigating mainstream applications based on the Bloom filter, we reveal that dynamic data sets are more common and important than static sets. However, existing variants of the Bloom filter cannot support dynamic data sets well. To address this issue, we propose dynamic Bloom filters to represent dynamic sets, as well as static sets and design necessary item insertion, membership query, item deletion, and filter union algorithms. The dynamic Bloom filter can control the false positive probability at a low level by expanding its capacity as the set cardinality increases. Through comprehensive mathematical analysis, we show that the dynamic Bloom filter uses less expected memory than the Bloom filter when representing dynamic sets with an upper bound on set cardinality, and also that the dynamic Bloom filter is more stable than the Bloom filter due to infrequent reconstruction when addressing dynamic sets without an upper bound on set cardinality. Moreover, the analysis results hold in stand-alone applications, as well as distributed applications. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/TKDE.2009.57 | IEEE Trans. Knowl. Data Eng. |
Keywords | Field | DocType |
set cardinality,bloom filter,set cardinality increase,false positive probability,dynamic bloom filter,dynamic bloom filters,low level,dynamic data,dynamic data set,static set,dynamic set,bloom filters,distributed application,data structure,data structures,algorithm design and analysis,band pass filters,false positive,mathematical analysis,application software,probability,upper bound,indexing terms | Data mining,Computer science,Upper and lower bounds,Cardinality,Theoretical computer science,Dynamic data,Artificial intelligence,Data structure,Bloom filter,Algorithm design,Band-pass filter,Cardinal number,Algorithm,Machine learning | Journal |
Volume | Issue | ISSN |
22 | 1 | 1041-4347 |
Citations | PageRank | References |
35 | 1.07 | 23 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Deke Guo | 1 | 326 | 47.25 |
| Jie Wu | 2 | 8307 | 592.07 |
| Honghui Chen | 3 | 129 | 24.44 |
| Ye Yuan | 4 | 38 | 4.92 |
| Xueshan Luo | 5 | 129 | 18.12 |