Theory and practice of bloom filters for distributed systems
S Tarkoma, CE Rothenberg… - … Surveys & Tutorials, 2011 - ieeexplore.ieee.org
Many network solutions and overlay networks utilize probabilistic techniques to reduce
information processing and networking costs. This survey article presents a number of …
information processing and networking costs. This survey article presents a number of …
Xor filters: Faster and smaller than bloom and cuckoo filters
The Bloom filter provides fast approximate set membership while using little memory.
Engineers often use these filters to avoid slow operations such as disk or network accesses …
Engineers often use these filters to avoid slow operations such as disk or network accesses …
Backyard cuckoo hashing: Constant worst-case operations with a succinct representation
The performance of a dynamic dictionary is measured mainly by its update time, lookup time,
and space consumption. In terms of update time and lookup time there are known …
and space consumption. In terms of update time and lookup time there are known …
Ribbon filter: practically smaller than Bloom and Xor
PC Dillinger, S Walzer - arXiv preprint arXiv:2103.02515, 2021 - arxiv.org
Filter data structures over-approximate a set of hashable keys, ie set membership queries
may incorrectly come out positive. A filter with false positive rate $ f\in (0, 1] $ is known to …
may incorrectly come out positive. A filter with false positive rate $ f\in (0, 1] $ is known to …
Bloom filters, adaptivity, and the dictionary problem
MA Bender, M Farach-Colton… - 2018 IEEE 59th …, 2018 - ieeexplore.ieee.org
An approximate membership query data structure (AMQ)-such as a Bloom, quotient, or
cuckoo filter-maintains a compact, probabilistic representation of a set S of keys from a …
cuckoo filter-maintains a compact, probabilistic representation of a set S of keys from a …
Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses
A minimal perfect hash function maps a set S of n keys into the set {0, 1,…, n− 1} bijectively.
Classical results state that minimal perfect hashing is possible in constant time using a …
Classical results state that minimal perfect hashing is possible in constant time using a …
Using cascading Bloom filters to improve the memory usage for de Brujin graphs
K Salikhov, G Sacomoto, G Kucherov - Algorithms for Molecular Biology, 2014 - Springer
Abstract Background De Brujin graphs are widely used in bioinformatics for processing next-
generation sequencing data. Due to a very large size of NGS datasets, it is essential to …
generation sequencing data. Due to a very large size of NGS datasets, it is essential to …
{Don't} be Dense: Efficient Keyword {PIR} for Sparse Databases
In this paper, we introduce SparsePIR, a single-server keyword private information retrieval
(PIR) construction that enables querying over sparse databases. At its core, SparsePIR is …
(PIR) construction that enables querying over sparse databases. At its core, SparsePIR is …
Chainedfilter: Combining membership filters by chain rule
Membership (membership query/membership testing) is a fundamental problem across
databases, networks and security. However, previous research has primarily focused on …
databases, networks and security. However, previous research has primarily focused on …
The bloom paradox: When not to use a bloom filter
O Rottenstreich, I Keslassy - IEEE/ACM Transactions on …, 2014 - ieeexplore.ieee.org
In this paper, we uncover the Bloom paradox in Bloom Filters: Sometimes, the Bloom Filter is
harmful and should not be queried. We first analyze conditions under which the Bloom …
harmful and should not be queried. We first analyze conditions under which the Bloom …