Basket Bloom Filters for Membership Queries
作者： Kun Xie , Yinghua Min , Dafang Zhang , Gaogang Xie , Jigang Wen
DOI: 10.1109/TENCON.2005.301258
关键词:
摘要: A bloom filter is a space-efficient data structure allowing membership queries over sets with allowable errors. It widely used in databases, networks, and distributed systems. This paper presents novel filter, called basket (BBF). The BBF deals different elements set depending on their query invalidation cost, by clustering into baskets. total cost function defined. In order to minimize the genetic algorithm employed find optimal number of hash functions for every basket. Simulation results show that, has 40% lower than standard filters under same executing time.
sci-hub.se 参考文章(17)
David E. Goldberg, Genetic algorithms in search, optimization, and machine learning ,(1988)
P. Druschel, A. Rowstron, PAST: a large-scale, persistent peer-to-peer storage utility Proceedings Eighth Workshop on Hot Topics in Operating Systems. pp. 75- 80 ,(2001) , 10.1109/HOTOS.2001.990064
Andrei Broder, Michael Mitzenmacher, Network Applications of Bloom Filters: A Survey Internet Mathematics. ,vol. 1, pp. 485- 509 ,(2004) , 10.1080/15427951.2004.10129096
Saar Cohen, Yossi Matias, Spectral bloom filters international conference on management of data. pp. 241- 252 ,(2003) , 10.1145/872757.872787
A. Whitaker, D. Wetherall, Forwarding without loops in Icarus 2002 IEEE Open Architectures and Network Programming Proceedings. OPENARCH 2002 (Cat. No.02EX571). pp. 63- 75 ,(2002) , 10.1109/OPNARC.2002.1019229
Ion Stoica, Robert Morris, David Liben-Nowell, David R Karger, M Frans Kaashoek, Frank Dabek, Hari Balakrishnan, None, Chord: a scalable peer-to-peer lookup protocol for Internet applications IEEE ACM Transactions on Networking. ,vol. 11, pp. 17- 32 ,(2003) , 10.1109/TNET.2002.808407
Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors Communications of the ACM. ,vol. 13, pp. 422- 426 ,(1970) , 10.1145/362686.362692
Li Fan, Pei Cao, J. Almeida, A.Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol IEEE ACM Transactions on Networking. ,vol. 8, pp. 281- 293 ,(2000) , 10.1109/90.851975
M. Mitzenmacher, Compressed Bloom filters IEEE ACM Transactions on Networking. ,vol. 10, pp. 604- 612 ,(2002) , 10.1109/TNET.2002.803864
M. McIlroy, Development of a Spelling List IEEE Transactions on Communications. ,vol. 30, pp. 91- 99 ,(1982) , 10.1109/TCOM.1982.1095395