Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Autoscaling Bloom filter: Controlling trade-off between true and false positives
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science. (DCC)ORCID iD: 0000-0002-6032-6155
ETH Zurich, Zurich, Switzerland.
Melbourne, Australia.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.ORCID iD: 0000-0003-0069-640x
2019 (English)In: Neural computing & applications (Print), ISSN 0941-0643, E-ISSN 1433-3058Article in journal (Refereed) Epub ahead of print
Abstract [en]

A Bloom filter is a special case of an artificial neural network with two layers. Traditionally, it is seen as a simple data structure supporting membership queries on a set. The standard Bloom filter does not support the delete operation, and therefore, many applications use a counting Bloom filter to enable deletion. This paper proposes a generalization of the counting Bloom filter approach, called “autoscaling Bloom filters”, which allows adjustment of its capacity with probabilistic bounds on false positives and true positives. Thus, by relaxing the requirement on perfect true positive rate, the proposed autoscaling Bloom filter addresses the major difficulty of Bloom filters with respect to their scalability. In essence, the autoscaling Bloom filter is a binarized counting Bloom filter with an adjustable binarization threshold. We present the mathematical analysis of its performance and provide a procedure for minimizing its false positive rate.

Place, publisher, year, edition, pages
Springer, 2019.
Keywords [en]
Bloom filter, Counting Bloom filter, Autoscaling Bloom filter, True positive rate, False positive rate
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-75476DOI: 10.1007/s00521-019-04397-1OAI: oai:DiVA.org:ltu-75476DiVA, id: diva2:1341842
Funder
Swedish Research Council, 2015-04677Available from: 2019-08-12 Created: 2019-08-12 Last updated: 2019-08-13

Open Access in DiVA

fulltext(1244 kB)5 downloads
File information
File name FULLTEXT01.pdfFile size 1244 kBChecksum SHA-512
9d5dcdc9c7a19779c531536d51ee66d0f2e7157f34c500bae7ce7e9f7a90b637e98f1c144173b4a431868f86170c838f99fec427e57c32ad5d6c771c1c4f3cdc
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Kleyko, DenisOsipov, Evgeny
By organisation
Computer Science
In the same journal
Neural computing & applications (Print)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 5 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 4 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf