Spectral bloom filters

ABSTRACT

A Bloom Filter is a space-efficient randomized data structure allowing membership queries over sets with certain allowable errors. It is widely used in many applications which take advantage of its ability to compactly represent a set, and filter out effectively any element that does not belong to the set, with small error probability. This paper introduces the Spectral Bloom Filter (SBF), an extension of the original Bloom Filter to multi-sets, allowing the filtering of elements whose multiplicities are below a threshold given at query time. Using memory only slightly larger than that of the original Bloom Filter, the SBF supports queries on the multiplicities of individual keys with a guaranteed, small error probability. The SBF also supports insertions and deletions over the data set. We present novel methods for reducing the probability and magnitude of errors. We also present an efficient data structure and algorithms to build it incrementally and maintain it over streaming data, as well as over materialized data with arbitrary insertions and deletions. The SBF does not assume any a priori filtering threshold and effectively and efficiently maintains information over the entire data-set, allowing for ad-hoc queries with arbitrary parameters and enabling a range of new applications.

REFERENCES

• 1: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 2: 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]
• 3: A. Broder and M. Mitzenmacher. Network applications of Bloom Filters: A survey. In Proc. of Allerton Conference, 2002.
• 4: A. Z. Broder. Personal communication.
• 5: S. Cohen and Y. Matias. Spectral bloom filters, Technical Report. Tel Aviv University, 2003.
• 6: Mayur Datar , Aristides Gionis , Piotr Indyk , Rajeev Motwani, Maintaining stream statistics over sliding windows: (extended abstract), Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.635-644, January 06-08, 2002, San Francisco, California
• 7: P. Elias. Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, 21(2):194--202, 1975.
• 8: Cristian Estan , George Varghese, New directions in traffic measurement and accounting, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 9: L. Fan, P. Cao, and J. Almeida. A prototype implementation of summary-cache enhanced icp in squid 1.1.14. www.cs.wisc.edu/~cao/sc-icp.html.
• 10: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area Web cache sharing protocol, ACM SIGCOMM Computer Communication Review, v.28 n.4, p.254-265, Oct. 1998
• 11: Min Fang , Narayanan Shivakumar , Hector Garcia-Molina , Rajeev Motwani , Jeffrey D. Ullman, Computing Iceberg Queries Efficiently, Proceedings of the 24rd International Conference on Very Large Data Bases, p.299-310, August 24-27, 1998
• 12: Sumit Ganguly , Phillip B. Gibbons , Yossi Matias , Avi Silberschatz, Bifocal sampling for skew-resistant join size estimation, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.271-281, June 04-06, 1996, Montreal, Quebec, Canada
• 13: Phillip B. Gibbons , Yossi Matias, New sampling-based summary statistics for improving approximate query answers, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.331-342, June 01-04, 1998, Seattle, Washington, United States
• 14: Phillip B. Gibbons , Yossi Matias, Synopsis data structures for massive data sets, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 15: 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]
• 16: Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Arun N. Swami, Fixed-precision estimation of join selectivity, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.190-201, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153875]
• 17: Lothar F. Mackert , Guy M. Lohman, R* Optimizer Validation and Performance Evaluation for Distributed Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.149-159, August 25-28, 1986
• 18: Udi Manber , Sun Wu, An algorithm for approximate membership checking with application to password security, Information Processing Letters, v.50 n.4, p.191-197, May 25, 1994 [doi>10.1016/0020-0190(94)00032-8]
• 19: G. S. Manku and R. Motwani. Approximate frequency counts over data streams. In Proc. of the 28th International Conference on Very Large Data Bases, VLDB, 2002.
• 20: Y. Matias. Bloom Histograms, July 2001.
• 21: Michael Mitzenmacher, Compressed bloom filters, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.144-150, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384004]
• 22: S. Rhea and J. Kubiatowicz. Probabilistic location and routing. In Proc. of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2002.
• 23: Squid Web Proxy Cache. http://www.squid-cache.org.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Set theory

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

General Terms:
Algorithms, Design, Experimentation, Performance