Cardinality estimation and dynamic length adaptation for Bloom filters

Odysseas Papapetrou, Wolf Siberski, Wolfgang Nejdl

Research output: Contribution to journalArticleAcademicpeer-review

30 Citations (Scopus)

Abstract

Bloom filters are extensively used in distributed applications, especially in distributed databases and distributed information systems, to reduce network requirements and to increase performance. In this work, we propose two novel Bloom filter features that are important for distributed databases and information systems. First, we present a new approach to encode a Bloom filter such that its length can be adapted to the cardinality of the set it represents, with negligible overhead with respect to computation and false positive probability. The proposed encoding allows for significant network savings in distributed databases, as it enables the participating nodes to optimize the length of each Bloom filter before sending it over the network, for example, when executing Bloom joins. Second, we show how to estimate the number of distinct elements in a Bloom filter, for situations where the represented set is not materialized. These situations frequently arise in distributed databases, where estimating the cardinality of the represented sets is necessary for constructing an efficient query plan. The estimation is highly accurate and comes with tight probabilistic bounds. For both features we provide a thorough probabilistic analysis and extensive experimental evaluation which confirm the effectiveness of our approaches.

Original languageEnglish
Pages (from-to)119-156
Number of pages38
JournalDistributed and Parallel Databases
Volume28
Issue number2-3
DOIs
Publication statusPublished - 1 Dec 2010
Externally publishedYes

Fingerprint

Information systems
Distributed database systems
Filter
Distributed databases
Node
Join
Query
Evaluation
Savings

Keywords

  • Bloom filters
  • Distributed databases
  • Distributed information systems

Cite this

Papapetrou, Odysseas ; Siberski, Wolf ; Nejdl, Wolfgang. / Cardinality estimation and dynamic length adaptation for Bloom filters. In: Distributed and Parallel Databases. 2010 ; Vol. 28, No. 2-3. pp. 119-156.
@article{3c2a16bd81c34bfd9cfdc533f19e129d,
title = "Cardinality estimation and dynamic length adaptation for Bloom filters",
abstract = "Bloom filters are extensively used in distributed applications, especially in distributed databases and distributed information systems, to reduce network requirements and to increase performance. In this work, we propose two novel Bloom filter features that are important for distributed databases and information systems. First, we present a new approach to encode a Bloom filter such that its length can be adapted to the cardinality of the set it represents, with negligible overhead with respect to computation and false positive probability. The proposed encoding allows for significant network savings in distributed databases, as it enables the participating nodes to optimize the length of each Bloom filter before sending it over the network, for example, when executing Bloom joins. Second, we show how to estimate the number of distinct elements in a Bloom filter, for situations where the represented set is not materialized. These situations frequently arise in distributed databases, where estimating the cardinality of the represented sets is necessary for constructing an efficient query plan. The estimation is highly accurate and comes with tight probabilistic bounds. For both features we provide a thorough probabilistic analysis and extensive experimental evaluation which confirm the effectiveness of our approaches.",
keywords = "Bloom filters, Distributed databases, Distributed information systems",
author = "Odysseas Papapetrou and Wolf Siberski and Wolfgang Nejdl",
year = "2010",
month = "12",
day = "1",
doi = "10.1007/s10619-010-7067-2",
language = "English",
volume = "28",
pages = "119--156",
journal = "Distributed and Parallel Databases",
issn = "0926-8782",
publisher = "Springer",
number = "2-3",

}

Cardinality estimation and dynamic length adaptation for Bloom filters. / Papapetrou, Odysseas; Siberski, Wolf; Nejdl, Wolfgang.

In: Distributed and Parallel Databases, Vol. 28, No. 2-3, 01.12.2010, p. 119-156.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Cardinality estimation and dynamic length adaptation for Bloom filters

AU - Papapetrou, Odysseas

AU - Siberski, Wolf

AU - Nejdl, Wolfgang

PY - 2010/12/1

Y1 - 2010/12/1

N2 - Bloom filters are extensively used in distributed applications, especially in distributed databases and distributed information systems, to reduce network requirements and to increase performance. In this work, we propose two novel Bloom filter features that are important for distributed databases and information systems. First, we present a new approach to encode a Bloom filter such that its length can be adapted to the cardinality of the set it represents, with negligible overhead with respect to computation and false positive probability. The proposed encoding allows for significant network savings in distributed databases, as it enables the participating nodes to optimize the length of each Bloom filter before sending it over the network, for example, when executing Bloom joins. Second, we show how to estimate the number of distinct elements in a Bloom filter, for situations where the represented set is not materialized. These situations frequently arise in distributed databases, where estimating the cardinality of the represented sets is necessary for constructing an efficient query plan. The estimation is highly accurate and comes with tight probabilistic bounds. For both features we provide a thorough probabilistic analysis and extensive experimental evaluation which confirm the effectiveness of our approaches.

AB - Bloom filters are extensively used in distributed applications, especially in distributed databases and distributed information systems, to reduce network requirements and to increase performance. In this work, we propose two novel Bloom filter features that are important for distributed databases and information systems. First, we present a new approach to encode a Bloom filter such that its length can be adapted to the cardinality of the set it represents, with negligible overhead with respect to computation and false positive probability. The proposed encoding allows for significant network savings in distributed databases, as it enables the participating nodes to optimize the length of each Bloom filter before sending it over the network, for example, when executing Bloom joins. Second, we show how to estimate the number of distinct elements in a Bloom filter, for situations where the represented set is not materialized. These situations frequently arise in distributed databases, where estimating the cardinality of the represented sets is necessary for constructing an efficient query plan. The estimation is highly accurate and comes with tight probabilistic bounds. For both features we provide a thorough probabilistic analysis and extensive experimental evaluation which confirm the effectiveness of our approaches.

KW - Bloom filters

KW - Distributed databases

KW - Distributed information systems

UR - http://www.scopus.com/inward/record.url?scp=77957859235&partnerID=8YFLogxK

U2 - 10.1007/s10619-010-7067-2

DO - 10.1007/s10619-010-7067-2

M3 - Article

AN - SCOPUS:77957859235

VL - 28

SP - 119

EP - 156

JO - Distributed and Parallel Databases

JF - Distributed and Parallel Databases

SN - 0926-8782

IS - 2-3

ER -