The Bloomier filter: an efficient data structure for static support lookup tables

ABSTRACT

We introduce the Bloomier filter, a data structure for compactly encoding a function with static support in order to support approximate evaluation queries. Our construction generalizes the classical Bloom filter, an ingenious hashing scheme heavily used in networks and databases, whose main attribute---space efficiency---is achieved at the expense of a tiny false-positive rate. Whereas Bloom filters can handle only set membership queries, our Bloomier filters can deal with arbitrary functions. We give several designs varying in simplicity and optimality, and we provide lower bounds to prove the (near) optimality of our constructions.

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: Broder, A., Mitzenmacher, M. Network applications of Bloom filters: a survey, Allerton 2002.
• 3: Andrej Brodnik , J. Ian Munro, Membership in Constant Time and Almost-Minimum Space, SIAM Journal on Computing, v.28 n.5, p.1627-1640, April/May 1999 [doi>10.1137/S0097539795294165]
• 4: H. Buhrman , P. B. Miltersen , J. Radhakrishnan , S. Venkatesh, Are bitvectors optimal?, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.449-458, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335357]
• 5: John Byers , Jeffrey Considine , Michael Mitzenmacher , Stanislav Rost, Informed content delivery across adaptive overlay networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 6: Michael Capalbo , Omer Reingold , Salil Vadhan , Avi Wigderson, Randomness conductors and constant-degree lossless expanders, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510003]
• 7: Saar Cohen , Yossi Matias, Spectral bloom filters, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872787]
• 8: Cuena-Acuna, F. M., Peery, C., Martin, R. P., Nguyen, T. D. PlanetP: Using gossiping to build content addressable peer-to-peer information sharing communities, Rutgers Technical Report DCS-TR-487, 2002.
• 9: 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
• 10: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol, IEEE/ACM Transactions on Networking (TON), v.8 n.3, p.281-293, June 2000 [doi>10.1109/90.851975]
• 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: Feng, W.-C., Shin, K. G., Kandlur, D., Saha, D. Stochastic fair blue: A queue management algorithm for enforcing fairness, INFOCOM '01 (2001), 1520--1529.
• 13: Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
• 14: 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]
• 15: Pai-Hsiang Hsiao, Geographical Region Summary Service for geographical routing, ACM SIGMOBILE Mobile Computing and Communications Review, v.5 n.4, October 2001 [doi>10.1145/509506.509515]
• 16: Kleitman, D. J., Spencer, J. Families of k-independent sets, Discrete Math 6 (1973), 255--262.
• 17: Ledlie, J., Taylor, J., Serban, L., Seltzer, M. Self-organization in peer-to-peer systems, Proc. 10th European SIGOPS Workshop, September 2002.
• 18: Zhe Li , Kenneth A. Ross, PERF join: an alternative to two-way semijoin and bloomjoin, Proceedings of the fourth international conference on Information and knowledge management, p.137-144, November 29-December 02, 1995, Baltimore, Maryland, United States [doi>10.1145/221270.221360]
• 19: Michael Luby, LT Codes, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.271, November 16-19, 2002
• 20: 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
• 21: 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]
• 22: McIlroy, M. D. Development of a spelling list, IEEE Trans. on Communications, COM-30 (1982), 91--99.
• 23: Michael Mitzenmacher, Compressed bloom filters, IEEE/ACM Transactions on Networking (TON), v.10 n.5, p.604-612, October 2002 [doi>10.1109/TNET.2002.803864]
• 24: J. K. Mullin, Optimal Semijoins for Distributed Database Systems, IEEE Transactions on Software Engineering, v.16 n.5, p.558-560, May 1990 [doi>10.1109/32.52778]
• 25: Razborov, A. A. Applications of matrix methods to the theory of lower bounds in computational complexity, Combinatorica 10 (1990), 81--93.
• 26: Rhea, S. C., Kubiatowicz, J. Probabilistic location and routing, Proceedings of INFOCOM 2002.
• 27: Alex Rousskov , Duane Wessels, Cache digests, Computer Networks and ISDN Systems, v.30 n.22-23, p.2155-2168, Nov. 25, 1998 [doi>10.1016/S0169-7552(98)00251-7]
• 28: Sipser, M., Spielman, D. A. Expander codes, IEEE Trans. Inform. Theory 42 (1996), 1710--1722.
• 29: Alex C. Snoeren, Hash-based IP traceback, ACM SIGCOMM Computer Communication Review, v.31 n.4, p.3-14, October 2001
• 30: Whitaker, A., Wetherall, D. Forwarding without loops in Icarus, Proc. 5th OPENARCH (2002), 63--75.