PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimizing Bloom Filter: Challenges, Solutions, and Comparisons

Lailong Luo, Deke Guo, Richard T. B. Ma, Ori Rottenstreich, Xueshan Luo

arXiv:1804.04777v2cs.DS

TL;DR

Bloom-filter research has produced many variants, but existing surveys are outdated and insufficiently explain their optimization design philosophy. This survey synthesizes more than 60 variants across performance and generalization, then compares their capabilities and complexities. It identifies techniques for reducing false positives and implementation costs while extending Bloom filters to diverse sets and richer functions.

  • Problem

    Existing surveys mainly focus on applications, are outdated, and do not adequately explain optimization techniques for newer Bloom filter variants.

  • Method

    The survey analyzes more than 60 Bloom filter variants across performance and generalization, organizing techniques by Bloom-filter components and comparing capabilities and complexities.

  • Results

    The surveyed variants reduce false positives and implementation costs while supporting diverse sets and additional functionalities beyond standard membership queries.

  • Takeaways & Limitations

    Bloom-filter designs can be selected and redesigned according to application context, including requirements for performance, set diversity, and functionality.

Abstract

from arXiv · show

Bloom filter (BF) has been widely used to support membership query, i.e., to judge whether a given element x is a member of a given set S or not. Recent years have seen a flourish design explosion of BF due to its characteristic of space-efficiency and the functionality of constant-time membership query. The existing reviews or surveys mainly focus on the applications of BF, but fall short in covering the current trends, thereby lacking intrinsic understanding of their design philosophy. To this end, this survey provides an overview of BF and its variants, with an emphasis on the optimization techniques. Basically, we survey the existing variants from two dimensions, i.e., performance and generalization. To improve the performance, dozens of variants devote themselves to reducing the false positives and implementation costs. Besides, tens of variants generalize the BF framework in more scenarios by diversifying the input sets and enriching the output functionalities. To summarize the existing efforts, we conduct an in-depth study of the existing literature on BF optimization, covering more than 60 variants. We unearth the design philosophy of these variants and elaborate how the employed optimization techniques improve BF. Furthermore, comprehensive analysis and qualitative comparison are conducted from the perspectives of BF components. Lastly, we highlight the future trends of designing BFs. This is, to the best of our knowledge, the first survey that accomplishes such goals.

I. INTRODUCTION

This survey addresses outdated, application-focused reviews by systematically analyzing more than 60 Bloom filter variants through performance and generalization perspectives. It examines optimization techniques for false positives, implementation, diverse input sets, and enriched functionality.

  • Motivation: Existing surveys are outdated and mainly emphasize applications rather than the optimization techniques underlying newer Bloom filter variants.The latest cited survey covered about 25 variants and was published five years earlier.
  • Contributions: More than 60 up-to-date designs are reviewed and qualitatively analyzed to explain how their optimization techniques improve Bloom filters.The survey presents this systematic synthesis as its distinguishing contribution.
  • Survey scope: The survey organizes Bloom filter improvements into false-positive reduction, implementation optimization, diverse-set representation, and functionality enrichment.These four angles address both performance and generalization of the Bloom filter framework.
  • Framework: Bloom filters represent sets with a bit vector and support membership queries through k hash-selected positions, but false positives remain possible.The basic framework initializes m bits to zero and sets k positions for each inserted element.
  • Framework: Careful parameter selection minimizes the theoretical false-positive rate, while maintaining a fixed rate requires m to increase linearly with n.The optimal number of hash functions is derived from minimizing the approximate false-positive expression.
  • Framework: Standard Bloom filters do not support deletion because resetting shared 1-bits can create false negatives for other elements.Counting Bloom filters address this limitation by replacing bits with counters that can be incremented and decremented.

B. Intrinsic characteristics of Bloom filter

Bloom filters are space-efficient and provide constant-time membership queries with one-sided errors, but their practical use is constrained by false positives, implementation costs, fixed capacity, and limited functionality.

  • Intrinsic characteristics: Bloom filters use space proportional to the number of elements rather than element length, supporting space-efficient set representation.The bit-vector length m is proportional to n and is independent of the number of bits needed to represent each element.
  • Intrinsic characteristics: With constant k, Bloom-filter insertion and query both have O(1) complexity.Querying checks the k corresponding bits, giving O(k) complexity before k is treated as constant.
  • Intrinsic characteristics: Bloom filters have one-sided errors: negative results are trustworthy, whereas positive results may be false positives.The structure does not produce false negatives under its standard membership-query behavior.
  • Challenges: False positives can harm upper-level applications, while reducing them may require additional space or more complicated operations.Increasing the filter length has diminishing effects, and identifying false positives can be difficult for large datasets.
  • Challenges: Implementation bottlenecks include O(k) memory accesses, low bit utilization, and expensive hash computation, especially on lightweight hardware.These costs worsen as the dataset contains more elements.
  • Challenges: Fixed parameters and immutable set bits restrict standard Bloom filters to static sets and prevent adaptive resizing.The representation also loses internal relationships such as distance, similarity, and precedence.
  • Challenges: The original Bloom filter supports insertion and membership queries but not deletion, decoding, multiplicity queries, or shared-set identification.Additional design is required to provide these operations and query types.

III. APPLICATIONS OF BLOOM FILTERS

Bloom filters support constant-time, space-efficient membership queries across caching, storage, wired and wireless networking, and privacy-preserving applications. Variants adapt the basic framework to routing, name lookup, multicast, and diverse sensitive datasets.

  • Caching and storage: BFs summarize cache contents to screen unnecessary accesses while preserving constant-time membership testing.False positives can still redirect accesses to main memory, but negative cache lookups are avoided.
  • Wired networking: On-chip and in-packet BFs support fast IP lookup, multicast routing, and named-data forwarding under space constraints.Applications include longest-prefix matching, forwarding through multicast trees, and NDN name lookups.
  • Wired networking: Multicast-routing variants reduce flow leakage by partitioning trees into layers or adapting hash functions to group presence probabilities.These designs adjust filter lengths or hash-function counts to address false positives in different routing settings.
  • Wired networking: A two-stage NDN design splits names into a BF-processed prefix and trie-processed suffix, achieving a lower false positive rate than NameFilter.Prefix and suffix lengths are dynamically throttled according to popularity.
  • Wireless networking: In wireless networks, BFs represent routing tables, events, cached paths, and pre-calculated routes to support fast lookups and reduce communication overhead.Examples span wireless routing, sensor networks, wireless NDN, and mobile robots.
  • Privacy preservation: BFs anonymize locations, biometric templates, and linkage records while enabling membership or approximate-matching queries.Applications include location privacy, biometric authentication, and privacy-preserving record linkage.

D. Network security

Bloom filters are used in security and privacy applications, but their false positives and implementation costs remain important design concerns. Their benefits include constant-time queries, space and access savings, and content anonymization across diverse systems.

  • Network security: Security applications use BFs for authentication, anonymity, firewalling, traceback, attack detection, and node-replication detection across wireless and wired networks.These applications are summarized in prior survey work on network security.
  • Network security: BF-based certificate-revocation schemes help smart meters identify and nullify false positives despite geographically distributed, scalable AMI deployments.The motivating challenge is the maintenance and access of large certificate revocation lists.
  • Benefits: Constant-time membership queries provide higher throughput than trees with O(log n) queries and tables or lists with O(n) queries.This is the common performance gain across BF applications.
  • Benefits: BF space cost depends on the target false positive rate and represented-element count, not element size, making filters storage- and communication-friendly.The bit-vector representation supports compact deployment and transmission.
  • Benefits: BFs refine memory access by directing requests to the filter first and denying queries whose membership result is negative.Positive results trigger a subsequent memory check, while false positives can cause unnecessary accesses.
  • Benefits: BFs anonymize element contents by exposing bit vectors for membership queries instead of the original data.This supports privacy preservation and data security.
  • False-positive measures: False positive proportion is empirical and variable, whereas false positive rate is theoretical, fixed by the BF framework, and commonly estimated by FPP.The distinction separates observed query errors from the filter’s theoretical error probability.
  • False-positive measures: Reducing false positives requires either lowering FPR through more space or controlling FPP with case-dependent techniques.Increasing vector size reduces FPR but incurs space overhead and may be unsuitable in space-scarce settings.

A. Reducing FP with prior knowledge

Prior knowledge and one-sided-error properties enable BF variants that identify or reduce false positives more selectively than standard filters. These methods trade additional computation, queries, or space against lower false-positive exposure.

  • Multicast routing: Multi-class BF adapts its design to multicast-group presence probabilities to minimize traffic leakage.The probability combines multicast-group size with data-center topology, assigning lower-impact treatment to groups with higher presence probability.
  • Multicast routing: FPF-MBF reduces false positive proportion by encoding each multicast-tree stage separately and adjusting each stage filter using included and excluded element counts.Its design targets (T−S)∩(Q−S)=∅ using prior knowledge of ρ and ζ.
  • Bloom paradox: Selective Bloom-filter insertion and querying avoid operations when known memory-cache conditions indicate the Bloom paradox.For |M|=10^10, |C|=10^4, and fp=10^-3, almost 1−10^-3 of positive results are false positives.
  • Optihash: Optihash selects transformed hash values that minimize the volume of false-positive elements when the queried set Q is known.It generates 2^mα2^mβ candidate hash-value sets, at the cost of complicated computation.
  • One-sided error: Ancestor queries can test positive trie nodes because a negative result for an ancestor is certainly correct under BF’s one-sided-error property.The strategy extends to sets whose elements share strong internal dependencies.
  • Cross-checking BF: Cross-checking BFs use disjoint subsets to identify main-filter positives that are negative in every relevant cross-checking filter.The architecture lowers false positives but requires more queries and space overhead.
  • Complement BF: A complement BF reduces off-chip hash-table accesses by requiring both the main and complement filters to return positive.Access frequency decreases from T(S) to T(S)∩T(SC), although a large complement set can consume substantial on-chip memory.

C. Reducing FP via bit resetting

False-positive reduction variants modify bit organization, clearing policies, hash-function selection, or encoding constraints. These designs improve accuracy through hierarchical storage, selective resetting, differentiated hash placement, or finite-universe guarantees, but introduce computation, memory, or workload constraints.

  • Retouched BF: Retouched BF removes selected false positives by clearing bits, but this can generate random false negatives.Randomized clearing resets bits randomly, whereas selective clearing targets bits known to trigger false positives.
  • Generalized BF: Generalized BF uses reset and set hash-function groups, trading false-positive reduction for possible false negatives.A positive result requires the reset-group positions to remain 0 and the set-group positions to remain 1.
  • MPCBF: MPCBF reconstructs each word hierarchically so membership uses level 1, reducing false positives versus conventional counter storage.It records membership with 8 bits instead of four 4-bit cells, at the cost of slightly more computation overhead.
  • Selected hash functions: Partitioned hashing selects hash functions that produce the fewest additional 1s for each element group, achieving as much as a ten-fold accuracy increase over standard BF.The method tests candidate hash-function groups before insertion and uses a greedy algorithm to accelerate selection.
  • EGH filter: EGH filter guarantees false-positive-free operations for a finite universe when the stored set remains within a restricted size.Its parameters are constrained by the universe size, number of stored elements, memory length, and selected prime numbers.

E. Reducing FP by differentiated representation

Differentiated representations reduce false positives by preserving more information about elements mapped to shared counters. VI-CBF uses variable increments, while FP-CBF stores fingerprints, with both methods requiring additional counter or fingerprint memory.

  • Variable-increment counting BF: VI-CBF increments counters by hashed values and queries exact counter values to distinguish elements sharing a cell.It uses two counter vectors: one records collision counts and the other records sums of distinct increments.
  • Variable-increment counting BF: VI-CBF improves false positive rate over CBF for fixed bits per element, but uses more bits per counter and therefore fewer counters.Its increment set is constructed so possible sums remain distinct.
  • Fingerprint counting BF: FP-CBF stores a fingerprint and counter in each cell, then uses fingerprints to recognize false-positive matches when a counter equals 1.The fingerprint is compared with the queried element’s fingerprint after checking the corresponding counters.
  • Summary and lessons learned: The survey groups false-positive reduction strategies into prior knowledge, hash selection, multiple filters or queries, bit resetting, and differential element representation.These approaches generally trade reduced false positives against additional memory or computation.

A. Computation optimization

Computation optimization targets hashing, query checks, and response time through hash reuse, parallelism, and hardware-aware layouts. These techniques can reduce computation or memory-access costs, but some require capable hardware, extra hash functions, or accept higher false-positive rates.

  • Hash computation: Double hashing generates k hash functions from two pseudorandom seeds without increasing the asymptotic false positive rate.The functions use gi(x)=h1(x)+i×h2(x) mod m.
  • Hash computation: OHBF generates k hash values from one hash function by partitioning the bit vector into uneven parts.Its design separates machine-word hashing from modulo mapping.
  • Parallelism: Parallelized variants can reduce response time to 1/ξ when ξ instances operate in parallel.Multiple vector segments may be accessed simultaneously, although some segmented designs require sequential checking.
  • Parallelism: DLB-BF divides one vector into k BFs that can be accessed simultaneously, but requires g×k hash functions.The parallel layout accelerates access while making hash computation challenging.
  • SIMD: SIMD parallelizes hash computation and membership checks, but requires competent computing units unavailable to some lightweight devices.UFBF is also reported to have a higher false positive rate than standard BF.
  • Memory-aware designs: OMASS uses block and sub-block partitioning to solve set separation with one memory access without increasing the false positive rate.Hash-function outputs are isolated across sets to prevent memory-sharing interference.

C. Space efficiency

Space-efficiency improvements address BF's limited bit utilization, transmission overhead, storage placement, and implementation costs. Other variants reduce energy or memory costs, often introducing trade-offs such as higher false positives, latency, or complexity.

  • Space utilization: At the optimal false positive rate, standard BF uses only 50% of its bits, motivating space-efficiency optimizations.The survey identifies bit utilization as a central space challenge for local storage and distributed dissemination.
  • Transmission: Compressed BF enlarges the uncompressed bit array under a fixed compressed transmission budget, while Compacted BF condenses the vector without time-consuming compression.Compacted BF can introduce both false positive and false negative errors, with rates controlled by parameters.
  • Dynamic storage: dlCBF replaces conventional counting-BF hashing with d-left hashing and supports insertion, querying, and deletion through fingerprints and counters.Compared with CBF, dlCBF achieves nearly 50% space saving at the same false positive guarantee and a two-magnitude false-positive reduction at the same space scale.
  • Specialized representations: Matrix BF stores each document in a row and estimates pairwise copy-paste similarity using bitwise AND and the number of resulting 1s.Adding or deleting a row enables document-level scalability and deletion while balancing accuracy, speed, space, and privacy protection.
  • Secondary storage: Forest-structured BF partitions filters into flash-page-sized sub-filters organized as a block forest, using RAM as storage or buffering when SSD is required.Queries descend to corresponding child blocks when a sub-filter does not identify the element; the cascaded structure raises overall false positives to 1−(1−fr)^l.
  • Energy and implementation: Pipelined and energy-efficient BFs reduce negative-query work by staging hash checks, but staged checking can increase latency and implementation complexity.Pipelined BF preserves the standard BF false positive rate, while EABF adaptively moves stage-2 hash functions according to workload.

E. Summary and lessons learned

The survey organizes BF optimization around computation, implementation, input-set diversity, and output functionality. Its reviewed variants extend BFs to multiset queries and other scenarios while exposing trade-offs among space, computation, accuracy, and robustness.

  • Performance optimization: BF computation can be optimized by reducing the amount of hashing or accelerating it through computation-friendly functions, fewer hash functions, or parallelization.The survey groups Pipelined BF, EABF, and L-CBF among designs targeting lower membership-query energy consumption.
  • Performance optimization: Real implementations strengthen BF performance by optimizing computation cost, memory access, space efficiency, and energy consumption.These variants are candidates for scenarios where such implementation metrics are sensitive.
  • Diverse sets: BF variants generalize input representation to multisets, dynamic and weighted datasets, key-value systems, sequence data, and spatial data.Multisets require recording element multiplicity, while dynamic datasets require capacity expansion or shrinkage on demand.
  • Multisets: Space-Code BF estimates multiplicity from the number of hash-function groups indicating an element, using maximum likelihood estimation.Multi-Resolution SCBF addresses high multiplicities by enabling multiple SCBFs, but estimation becomes computation-intensive and may overestimate or underestimate.
  • Multisets: Spectral BF estimates multiplicity with the minimum of k counters, supports deletion, and can suffer inaccurate queries when hash collisions occur.Its space overhead can be slightly higher than standard BF.
  • Multisets: Invertible Counting BF synchronizes multisets by encoding identifiers and counts in cells, then subtracting and decoding to find differences.Hash collisions can cause both false positive and false negative synchronization errors, while exchanging filters consumes link bandwidth.
  • Multisets: Shifting BF stores membership bits and offset-derived auxiliary bits, enabling customized queries such as multiplicity while allowing a counting version for deletion.The existence and auxiliary information may interfere within the bit vector.
  • Multisets: Multiplicity can be represented with counters or additional set bits, creating trade-offs between extra space and membership-query accuracy.Counter-based approaches include Space-Code, Spectral, Invertible Counting, and Loglog BFs; Adaptive and Shifting BFs use additional bits.

B. Dynamic sets

Dynamic-set variants extend Bloom filters to accommodate insertions, deletions, and changing capacity, but trade these capabilities against space, false positives, computation, or deletion safety.

  • Dynamic capacity: Dynamic BF activates reserved homogeneous filters as earlier filters fill, while Scalable BF uses heterogeneous filters with geometrically increasing false positive rates.Scalable BF reduces the need for identical sub-filters but requires more hash calculations because sub-filters cannot share hash functions.
  • Deletion: DBF deletion resets bits only when exactly one filter indicates the element; otherwise it aborts to avoid false negatives for other elements.DBF can also merge two active filters through union operations.
  • Trade-offs: DBF’s false positive rate is 1−(1−fr)^s, exceeding the designed rate fr of each individual filter.Multiple filters increase false-positive risk, and failed deletions can leave positive results for removed elements.
  • Trade-offs: Dynamic BF, Scalable BF, DBA, and Par-BF reserve or activate additional filters dynamically, but unknown dataset size creates space-reservation and aggregate-error challenges.Their aggregate false positive rates increase with the number of initialized filters.
  • Skewed datasets: Weighted BF allocates more hash functions to frequently queried elements with lower membership probability, whereas Popularity Conscious BF optimizes allocation under a fixed kmax.Popularity Conscious BF provides polynomial-time 2-approximation and (2+ε)-approximation algorithms.

D. Key-values

Key-value variants adapt Bloom-filter storage and querying to key-value systems, while sequence and spatial variants specialize representation for structured datasets and domain-specific operations.

  • Key-value stores: BloomStore partitions the key space across instances containing RAM-resident buffers and secondary-memory Bloom-filter chains and data pages.Homogeneous filters in each chain share hash outputs, enabling parallel checking and natural scalability.
  • Key-value stores: BloomStore supports deletion by inserting a null value into the corresponding filter bits, but its aggregated false positive possibility is relatively high.The design trades storage-system functionality and scalability against aggregate false positives.
  • Key-value stores: kBF converts values into fixed-length bit-string encodings stored in cells with counters and original-or-XOR encoding fields.This representation enables update, deletion, join, and compression operations, but decoding has O(N^2) time complexity and can fail on nondecodable cells.
  • Key-value stores: Invertible Bloom lookup table supports key-value insertion, deletion, lookup, and high-probability complete listing when the pair count remains below a designed threshold.Decoding repeatedly removes anchor cells containing one key-value pair; listing may stop when no anchor cell exists.
  • Sequence sets: k-mer BF uses dependencies between adjacent k-mers, which share k−1 characters, to identify some false positives through neighbor queries.Although compact for sequence sets, it supports only membership queries and not traversal, deletion, permutation, or inversion.
  • Spatial sets: Spatial BF assigns location cells class labels based on Manhattan-distance categories, preserving higher labels under collisions for privacy-aware positioning.Its abstraction oversimplifies spatial data and cannot track motion when a user remains within one class.

B. Element decay

Element-decay variants proactively remove stale information to make room for new data, using either changing cell values or rotating multiple filter vectors, with false negatives as a recurring trade-off.

  • Decay mechanisms: Decay differs from deletion because it is proactive and does not know which or how many elements will be removed.Decay is executed periodically or aperiodically, unlike user-invoked deletion.
  • Single-vector decay: Stable BF decays streaming-data state by decrementing randomly selected cells and resetting inserted elements’ mapped cells to Max.Its zero fraction becomes fixed after numerical iterations, irrespective of the initial state.
  • Single-vector decay: Temporal Counting BF assigns inserted counters an initial counter value and continuously decreases all counters according to a decay factor.Tuning these parameters controls differentiated decay granularity, while collisions can produce false negatives and the scheme can increase false positives.
  • Multi-vector decay: Double buffering rotates active and warm-up filters, flushing the warm-up filter when the active filter fills to evict stale elements in FIFO order.The warm-up filter stores a subset of active data before the switch.
  • Multi-vector decay: A2 buffering stores twice as many elements as double buffering in best-case scenarios and as many in worst-case scenarios.Its global false positive rate is f =1−(1−fr)^2 when each filter has rate fr.
  • Multi-vector decay: Forgetful BF maintains future, present, and past filters and periodically refreshes them to evict the oldest stale elements.This is another multi-vector approach to decay recorded elements.

C. Approximate membership query

Approximate-membership variants use locality-sensitive hashing and verification or thresholding to judge whether a query is close to a stored element, extending Bloom filters beyond exact membership.

  • Distance-sensitive filters: Distance-sensitive BF partitions the vector into k disjoint arrays, maps each element through distance-sensitive hashes, and sums the queried positions’ bits.If B(x) exceeds threshold t, x is judged far from S; otherwise it is judged close.
  • Distance-sensitive filters: Distance-sensitive BF requires two hash families, is difficult to configure, lacks scalability, and assumes a static set.Its parameters are customized to the current dataset and cannot be generalized to other datasets.
  • Locality-sensitive filters: LSBF replaces independent uniform hashes with locality-sensitive hashes and accepts a query only when all corresponding bits are non-zero.It adds a verification Bloom filter to identify some false positives and an overflow scheme to reduce false negatives.
  • Multi-granularity filters: MLBF supports multiple distance granularities through a basic multi-granularity locality-sensitive filter and a verification filter.Queries check a virtual level first and then the verification filter, but the design still has false positives, false negatives, and substantial construction and query overhead.
  • Semantic enrichment: Bloomier filter generalizes Bloom-filter semantics from Boolean membership functions to arbitrary functions and their associated values.It therefore supports constant-time queries of function values associated with elements.
  • Semantic enrichment: Parallel BF represents multi-attribute elements with a matrix of counting filters and an auxiliary hash table that verifies attribute dependencies.The matrix enlarges false positives relative to a single counting filter, while the hash table identifies most of those errors at added hash, space, and memory-access costs.

VIII. CLASSIFICATION AND COMPARISON

The survey classifies Bloom filter variants by performance and generalization, then analyzes how they optimize elements, hash functions, and bit vectors. These strategies reduce false positives or implementation costs, diversify represented sets, and enrich functionality.

  • Classification: Bloom filter variants are organized along performance and generalization dimensions.Performance-oriented variants reduce false positives or ease implementation, while generalization-oriented variants diversify input sets and enrich output functionality.
  • Bit vector: Bit-vector variants change representation or semantics by extending cells, compressing vectors, or deploying multiple vectors.These changes support additional information, transmission efficiency, scalability, or richer operations beyond basic membership representation.
  • Elements: Element-oriented techniques exploit dataset structure through fingerprints, preprocessing, or grouping.Fingerprinting distinguishes elements, while grouping isolates interference and can improve memory access and query throughput.
  • Hash functions: Hash-function variants adjust hash-function count, use multiple groups, or select hashes on demand.Multiple groups may be required for secondary filters or parallel queries, but their main cost is computation overhead.
  • Hash functions: Hash-based optimizations also include extra functions for candidate selection and differentiated increments for inserted elements.These designs use additional hashing to choose fingerprints, cells, blocks, or increments, with differentiated increments helping avoid some false positives.

2) Optimization of hash implementation:

The survey reviews hash-implementation techniques that reduce computation or improve performance, while noting trade-offs from intensive selection procedures and specialized hardware. It also connects hash choices with advanced functionality and vector organization.

  • Hash generation: One or two hash functions can generate k hash values, reducing the need for k independent hash computations.Bloom-1 partitions hash bits, One hash uses diverse moduli, and Less hash generates requested values from two independent functions.
  • Hash selection: Hash groups can be tested or selected to reduce false positive proportion, but optimization may require multiple rounds of tests or queries.Optihash and Partition hashing are computation-intensive, whereas testing two groups offers a more moderate approach.
  • Hash implementation: SIMD parallelizes hash computation and can generate k hash values in 1/k time, but requires dedicated hardware and software environments.The hardware and software requirement reduces the generality of Ultra-fast BF.
  • Advanced hash techniques: d-left hashing selects a least-loaded cell and achieves nearly 50% space saving with the same false positive guarantee.With the same space scale, it also achieves a two-magnitude reduction in false positive rate.
  • Advanced hash techniques: Locality-sensitive hashing enables distance-oriented queries but introduces false positives, false negatives, and implementation complexity.It maps neighboring elements to nearby locations, supporting queries about whether an element is close to any set element.

3) The power of partition:

Partitioning and multi-vector designs adapt Bloom filters for access, capacity, semantics, and specialized functionality. These extensions broaden supported capabilities, but their benefits can involve space, complexity, or error trade-offs.

  • The power of partition: Partitioning the bit vector into k segments enables parallel access, at the cost of a slight false positive increase.Each hash function is assigned to one segment, while related designs place element information in word-size blocks for fewer memory accesses.
  • The power of partition: Hierarchical and multi-vector designs support dynamic insertion, deletion, scalability, grouping, and capacity management.MPCBF uses later levels for dynamic updates, while multiple BFs can be added or merged on demand for scalable datasets.
  • The power of partition: Resetting, marking, or flushing vector state supports decay and deletion while changing the filter’s error behavior.Retouched and Generalized BF reset bits, Ternary BF marks collision-prone bits as X, and buffering schemes flush stale filters.
  • The power of partition: Additional bits and multi-field cells enrich Bloom-filter semantics for multiplicity, association, key-value storage, decoding, and synchronization.Counters support counting and deletion, while IBLT, IBF, and ICBF use multi-field cells for recursive invertible decoding or multiset synchronization.
  • Qualitative comparison: The survey compares variants by counting, grouping, deletion, scalability, decay, parallelism, false negatives, and operation or access complexity.Table IV presents these capabilities and the complexities of insertion, query, deletion, and memory access.

2) Complexity comparison:

The survey compares Bloom-filter variants by operation and memory-access complexity alongside their capabilities, showing that richer functionality generally carries computational or access costs. It also identifies practical boundaries and future directions for scalable, relational, and hardware-aware designs.

  • Complexity comparison: Higher computation and memory-access complexity is the general penalty for adding capabilities such as counting, deletion, scalability, decay, or parallelism.The comparison considers insertion, query, deletion, and memory access, with some variants requiring upper- and lower-bound complexity reporting.
  • Complexity comparison: Insertion complexity is mainly determined by the number of hash functions, while query complexity often depends on insertion complexity.Adaptive BF has insertion complexity O(k+N+1), and recursive or neighboring-sequence designs introduce additional query work.
  • Complexity comparison: Deletion generally matches query complexity because the filter must check element existence before deletion.Variable length signatures is an outlier because deletion resets k−d bits after its threshold-based membership decision.
  • Complexity comparison: Shared-vector variants require k memory accesses because the target bits are dispersed across the vector.Partitioned or block-oriented designs reduce this cost by reorganizing where an element’s information is stored.
  • Open issues: Future designs should address extreme hardware, arbitrary-scale resizing, and representation of relationships between elements.Existing filters mostly represent elements independently; locality-sensitive variants capture proximity, but broader dependencies remain unsupported.
Loading 1804.04777v2…