The gaussian bloom filter

Martin Werner, Mirco Schönfeld

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

Modern databases tailored to highly distributed, fault tolerant management of information for big data applications exploit a classical data structure for reducing disk and network I/O as well as for managing data distribution: The Bloom filter. This data structure allows to encode small sets of elements, typically the keys in a key-value store, into a small, constant-size data structure. In order to reduce memory consumption, this data structure suffers from false positives which lead to additional I/O operations and are therefore only harmful with respect to performance. With this paper, we propose an extension to the classical Bloom filter construction which facilitates the use of floating point coprocessors and GPUs or additional main memory in order to reduce false positives. The proposed data structure is compatible with the classical construction in the sense that the classical Bloom filter can be extracted in time linear to the size of the data structure and that the Bloom filter is a special case of our construction. We show that the approach provides a relevant gain with respect to the false positive rate. Implementations for Apache Cassandra, C++, and NVIDIA CUDA are given and support the feasibility and results of the approach.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications - 20th International Conference, DASFAA 2015, Proceedings Hanoi, Vietnam, April 20-23, 2015 Proceedings, Part I
EditorsCyrus Shahabi, Muhammad Aamir Cheema, Matthias Renz, Xiaofang Zhou
PublisherSpringer Verlag
Pages191-206
Number of pages16
ISBN (Print)9783319181196
DOIs
StatePublished - 2015
Externally publishedYes
Event20th International Conference on Database Systems for Advanced Applications, DASFAA 2015 - Hanoi, Viet Nam
Duration: 20 Apr 201523 Apr 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9049
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Conference on Database Systems for Advanced Applications, DASFAA 2015
Country/TerritoryViet Nam
CityHanoi
Period20/04/1523/04/15

Keywords

  • Bloom filter
  • Data structures
  • Database design

Fingerprint

Dive into the research topics of 'The gaussian bloom filter'. Together they form a unique fingerprint.

Cite this