The Bloomier filter: an efficient data structure for static support lookup tables
作者： Ronitt Rubinfeld , Bernard Chazelle , Joe Kilian , Ayellet Tal
关键词: Bloom filter 、 Encoding (memory) 、 Function (mathematics) 、 Mathematics 、 Filter (video) 、 Algorithm 、 Lookup table 、 Set (abstract data type) 、 Theoretical computer science 、 Data structure 、 Hash function
摘要: We introduce the Bloomier filter, a data structure for compactly encoding function with static support in order to approximate evaluation queries. Our construction generalizes classical Bloom an ingenious hashing scheme heavily used networks and databases, whose main attribute---space efficiency---is achieved at expense of tiny false-positive rate. Whereas filters can handle only set membership queries, our deal arbitrary functions. give several designs varying simplicity optimality, we provide lower bounds prove (near) optimality constructions.
acm.org
princeton.edu 
sci-hub.st 参考文章(29)
Cristian Estan, George Varghese, New directions in traffic measurement and accounting Proceedings of the First ACM SIGCOMM Workshop on Internet Measurement - IMW '01. ,vol. 32, pp. 323- 336 ,(2001) , 10.1145/505202.505212
Daniel J. Kleitman, Joel Spencer, Families of k-independent sets Discrete Mathematics. ,vol. 6, pp. 255- 262 ,(1973) , 10.1016/0012-365X(73)90098-8
Andrei Broder, Michael Mitzenmacher, Network Applications of Bloom Filters: A Survey Internet Mathematics. ,vol. 1, pp. 485- 509 ,(2004) , 10.1080/15427951.2004.10129096
A. A. Razborov, Applications of matrix methods to the theory of lower bounds in computational complexity Combinatorica. ,vol. 10, pp. 81- 93 ,(1990) , 10.1007/BF02122698
Hector Garcia-Molina, Rajeev Motwani, Narayanan Shivakumar, Jeffrey D. Ullman, Min Fang, Computing Iceberg Queries Efficiently very large data bases. pp. 299- 310 ,(1998)
Saar Cohen, Yossi Matias, Spectral bloom filters international conference on management of data. pp. 241- 252 ,(2003) , 10.1145/872757.872787
Pai-Hsiang Hsiao, Geographical Region Summary Service for geographical routing ACM SIGMOBILE Mobile Computing and Communications Review. ,vol. 5, pp. 25- 39 ,(2001) , 10.1145/509506.509515
Andrej Brodnik, J. Ian Munro, Membership in Constant Time and Almost-Minimum Space SIAM Journal on Computing. ,vol. 28, pp. 1627- 1640 ,(1999) , 10.1137/S0097539795294165
H. Buhrman, P. B. Miltersen, J. Radhakrishnan, S. Venkatesh, Are bitvectors optimal symposium on the theory of computing. pp. 449- 458 ,(2000) , 10.1145/335305.335357
Jonathan Ledlie, Jacob M. Taylor, Laura Serban, Margo Seltzer, Self-organization in peer-to-peer systems Proceedings of the 10th workshop on ACM SIGOPS European workshop: beyond the PC - EW10. pp. 125- 132 ,(2002) , 10.1145/1133373.1133397