Home > Research > Publications & Outputs > Scalable Bloom Filters

Research

Associated organisational units

Links

Text available via DOI:

Keywords

View graph of relations

Scalable Bloom Filters

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Scalable Bloom Filters. / Almeida, Paulo Sérgio; Baquero, Carlos; Preguiça, Nuno et al.
In: Information Processing Letters, Vol. 101, No. 6, 31.03.2007, p. 255-261.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Almeida, PS, Baquero, C, Preguiça, N & Hutchison, D 2007, 'Scalable Bloom Filters', Information Processing Letters, vol. 101, no. 6, pp. 255-261. https://doi.org/10.1016/j.ipl.2006.10.007

APA

Almeida, P. S., Baquero, C., Preguiça, N., & Hutchison, D. (2007). Scalable Bloom Filters. Information Processing Letters, 101(6), 255-261. https://doi.org/10.1016/j.ipl.2006.10.007

Vancouver

Almeida PS, Baquero C, Preguiça N, Hutchison D. Scalable Bloom Filters. Information Processing Letters. 2007 Mar 31;101(6):255-261. doi: 10.1016/j.ipl.2006.10.007

Author

Almeida, Paulo Sérgio ; Baquero, Carlos ; Preguiça, Nuno et al. / Scalable Bloom Filters. In: Information Processing Letters. 2007 ; Vol. 101, No. 6. pp. 255-261.

Bibtex

@article{0529f6f0626a406faeeab124c92e4c18,
title = "Scalable Bloom Filters",
abstract = "Bloom filters provide space-efficient storage of sets at the cost of a probability of false positives on membership queries. The size of the filter must be defined a priori based on the number of elements to store and the desired false positive probability, being impossible to store extra elements without increasing the false positive probability. This leads typically to a conservative assumption regarding maximum set size, possibly by orders of magnitude, and a consequent space waste. This paper proposes Scalable Bloom Filters, a variant of Bloom filters that can adapt dynamically to the number of elements stored, while assuring a maximum false positive probability.",
keywords = "Data structures, Bloom filters, Distributed systems, Randomized algorithms",
author = "Almeida, {Paulo S{\'e}rgio} and Carlos Baquero and Nuno Pregui{\c c}a and David Hutchison",
year = "2007",
month = mar,
day = "31",
doi = "10.1016/j.ipl.2006.10.007",
language = "English",
volume = "101",
pages = "255--261",
journal = "Information Processing Letters",
issn = "1872-6119",
publisher = "Elsevier",
number = "6",

}

RIS

TY - JOUR

T1 - Scalable Bloom Filters

AU - Almeida, Paulo Sérgio

AU - Baquero, Carlos

AU - Preguiça, Nuno

AU - Hutchison, David

PY - 2007/3/31

Y1 - 2007/3/31

N2 - Bloom filters provide space-efficient storage of sets at the cost of a probability of false positives on membership queries. The size of the filter must be defined a priori based on the number of elements to store and the desired false positive probability, being impossible to store extra elements without increasing the false positive probability. This leads typically to a conservative assumption regarding maximum set size, possibly by orders of magnitude, and a consequent space waste. This paper proposes Scalable Bloom Filters, a variant of Bloom filters that can adapt dynamically to the number of elements stored, while assuring a maximum false positive probability.

AB - Bloom filters provide space-efficient storage of sets at the cost of a probability of false positives on membership queries. The size of the filter must be defined a priori based on the number of elements to store and the desired false positive probability, being impossible to store extra elements without increasing the false positive probability. This leads typically to a conservative assumption regarding maximum set size, possibly by orders of magnitude, and a consequent space waste. This paper proposes Scalable Bloom Filters, a variant of Bloom filters that can adapt dynamically to the number of elements stored, while assuring a maximum false positive probability.

KW - Data structures

KW - Bloom filters

KW - Distributed systems

KW - Randomized algorithms

U2 - 10.1016/j.ipl.2006.10.007

DO - 10.1016/j.ipl.2006.10.007

M3 - Journal article

VL - 101

SP - 255

EP - 261

JO - Information Processing Letters

JF - Information Processing Letters

SN - 1872-6119

IS - 6

ER -