Autoscaling Bloom Filter: Controlling Trade-off Between True and False Positives
作者： Denis Kleyko , Abbas Rahimi , Ross W. Gayler , Evgeny Osipov
DOI: 10.1007/S00521-019-04397-1
关键词: False positive rate 、 Autoscaling 、 Data structure 、 Algorithm 、 Set (abstract data type) 、 Minification 、 Probabilistic logic 、 Mathematics 、 Bloom filter 、 False positive paradox
摘要: A Bloom filter is a simple data structure supporting membership queries on set. The standard does not support the delete operation, therefore, many applications use counting to enable deletion. This paper proposes generalization of approach, called "autoscaling filters", which allows adjustment its capacity with probabilistic bounds false positives and true positives. In essence, autoscaling binarized an adjustable binarization threshold. We present mathematical analysis performance as well give procedure for minimization positive rate.
arxiv.org
sci-hub.se 参考文章(34)
Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, George Varghese, An Improved Construction for Counting Bloom Filters Lecture Notes in Computer Science. pp. 684- 695 ,(2006) , 10.1007/11841036_61
Heng Ma, Ying-Chih Tseng, Lu-I. Chen, A CMAC-based scheme for determining membership with classification of text strings Neural Computing and Applications. ,vol. 27, pp. 1959- 1967 ,(2016) , 10.1007/S00521-015-1989-6
Bin Fan, Dave G. Andersen, Michael Kaminsky, Michael D. Mitzenmacher, Cuckoo Filter: Practically Better Than Bloom conference on emerging network experiment and technology. pp. 75- 88 ,(2014) , 10.1145/2674005.2674994
Andrei Broder, Michael Mitzenmacher, Network Applications of Bloom Filters: A Survey Internet Mathematics. ,vol. 1, pp. 485- 509 ,(2004) , 10.1080/15427951.2004.10129096
C.L. Wu, K.W. Chau, Rainfall–runoff modeling using artificial neural network coupled with singular spectrum analysis Journal of Hydrology. ,vol. 399, pp. 394- 409 ,(2011) , 10.1016/J.JHYDROL.2011.01.017
Ken Christensen, Allen Roginsky, Miguel Jimeno, A new analysis of the false positive rate of a Bloom filter Information Processing Letters. ,vol. 110, pp. 944- 949 ,(2010) , 10.1016/J.IPL.2010.07.024
David Hutchison, Nuno Preguiça, Carlos Baquero Moreno, Paulo Sérgio Almeida, Paulo Sérgio Almeida, Carlos Baquero Moreno, Nuno Preguiça, David Hutchison, Scalable Bloom Filters Information Processing Letters. ,vol. 101, pp. 255- 261 ,(2007) , 10.1016/J.IPL.2006.10.007
Salvatore Pontarelli, Pedro Reviriego, Michael Mitzenmacher, Improving the performance of Invertible Bloom Lookup Tables Information Processing Letters. ,vol. 114, pp. 185- 191 ,(2014) , 10.1016/J.IPL.2013.11.015
Pentti Kanerva, Hyperdimensional Computing: An Introduction to Computing in Distributed Representation with High-Dimensional Random Vectors Cognitive Computation. ,vol. 1, pp. 139- 159 ,(2009) , 10.1007/S12559-009-9009-8
Sasu Tarkoma, Christian Esteve Rothenberg, Eemil Lagerspetz, Theory and Practice of Bloom Filters for Distributed Systems IEEE Communications Surveys and Tutorials. ,vol. 14, pp. 131- 155 ,(2012) , 10.1109/SURV.2011.031611.00024