bei Google ScholarTitelangaben
Werner, Martin ; Schönfeld, Mirco:
The Gaussian Bloom Filter.
In: Renz, Matthias ; Shahabi, Cyrus ; Zhou, Xiaofang ; Cheema, Muhammad Aamir
(Hrsg.):
Database Systems for Advanced Applications : 20th International Conference DASFAA 2015 ; Proceedings. Part I. -
Cham
: Springer International Publishing
,
2015
. - S. 191-206
. - (Lecture Notes in Computer Science
; 9049
)
ISBN 978-3-319-18120-2
DOI: https://doi.org/10.1007/978-3-319-18120-2_12
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.
Weitere Angaben
| Publikationsform: | Aufsatz in einem Buch |
|---|---|
| Begutachteter Beitrag: | Ja |
| Keywords: | Bloom Filter; Database design; Data structures |
| Institutionen der Universität: | Fakultäten > Sprach- und Literaturwissenschaftliche Fakultät Fakultäten > Sprach- und Literaturwissenschaftliche Fakultät > Juniorprofessur Datenmodellierung und interdisziplinäre Wissensgenerierung Fakultäten > Sprach- und Literaturwissenschaftliche Fakultät > Juniorprofessur Datenmodellierung und interdisziplinäre Wissensgenerierung > Juniorprofessur Datenmodellierung und interdisziplinäre Wissensgenerierung - Juniorprof. Dr. Mirco Schönfeld Fakultäten |
| Titel an der UBT entstanden: | Nein |
| Themengebiete aus DDC: | 000 Informatik,Informationswissenschaft, allgemeine Werke > 004 Informatik |
| Eingestellt am: | 18 Nov 2021 11:35 |
| Letzte Änderung: | 18 Nov 2021 11:35 |
| URI: | https://eref.uni-bayreuth.de/id/eprint/67893 |