A second look at bloom filters

ABSTRACT

This note deals with a paper by Gremillion demonstrating the simulation approach to the design of a Bloom filter. It is shown that an analytical approach can yield insights into competing filter design and give expected values for the goodness-of-hash transformations not available with simulation. On the other hand, simulation gives insight into what can be expected with available hash transformation not available from an analytic approach.

REFERENCES

• 1: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 2: Lee L. Gremillion, Designing a Bloom filter for differential file access, Communications of the ACM, v.25 n.9, p.600-604, Sept 1982 [doi>10.1145/358628.358632]
• 3: V. Y. Lum , P. S. T. Yuen , M. Dodd, Key-to-address transform techniques: a fundamental performance study on large existing formatted files, Communications of the ACM, v.14 n.4, p.228-239, April 1971 [doi>10.1145/362575.362578]

INDEX TERMS

Primary Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

General Terms:
Performance, Theory

Keywords:
bloom, differential file, filter