Given a set \(S \subseteq \mathcal {U}\) and a function \(f:S\rightarrow \lbrace 0,1\rbrace ^r\) , a static retrieval data structure for f supports queries that return \(f(x)\) for \(x \in S\) and an arbitrary value from \(\lbrace 0,1\rbrace ^r\) for \(x \in \mathcal {U}\setminus S\) . Retrieval data structures can be used to implement a static approximate membership query (AMQ) data structure, i.e., a Bloom filter alternative, with false positive rate \(2^{-r}\) . The information-theoretic space lower bound for both tasks is \(r|S|\) bits, and here we aim to use space \(r|S|(1+\varepsilon)\) bits for a small overhead \(\varepsilon\) , including succinct constructions with \(\varepsilon = o(1)\) . A well-known approach to this task associates each key \(x \in S\) with a row vector \(\smash{\vec{h}}(x) \in \lbrace 0,1\rbrace ^{m}\) and stores a matrix \(Z\in \lbrace 0,1\rbrace ^{m\times r}\) such that \(\smash{\vec{h}}(x)\cdot Z = f(x)\) for every \(x \in S\) . We propose a new variant where \(\smash{\vec{h}}(x)\) contains a short block of random bits at a random position \(s(x)\) , and is otherwise zero. Sorting the row vectors by \(s(x)\) gives a matrix \(A \in \lbrace 0,1\rbrace ^{n \times m}\) with non-zero entries concentrated in a “ribbon” along a generalized diagonal. This makes a variant of Gaussian elimination particularly efficient at computing Z . We thus obtain simple data structures called Standard Ribbon Retrieval and Homogeneous Ribbon Filter . We then refine the construction using bumping (a variant of backyarding) and overloading (using \(m \lt n\) ) to obtain bumped ribbon retrieval (“BuRR”), with overhead \(\mathcal {O}\!(\frac{\log w}{rw^2})\) , query time \(\mathcal {O}\!(1+\frac{rw}{\log n})\) , and expected construction time \(\mathcal {O}\!\left(nw\right)\) , for a tuning parameter \(w=\mathcal {O}\!\left(\log n\right)\) that opens a trade-off between space and running time. Our experiments reveal our implementations to be the first to simultaneously achieve small overheads and fast running times in practice, with BuRR achieving overheads well below 1 % while being faster than most competitors, which have larger space overheads. This efficiency, including favorable constants, stems from a combination of simplicity, word parallelism, and high locality. We offer a unified theoretical perspective on these three ribbon-based data structures, including a nontrivial rigorous analysis of their running times and memory consumption.

Approximate membership filters are increasingly used in many computing and networking applications and new filter designs are being continuously presented to improve one or more performance metrics. Therefore, understanding their security and privacy is an important issue. Previous works have considered attackers that only have access to an individual filter in isolation. For applications that generate many related filters, such as a filter for a deny list that evolves over time, that analysis is insufficient. This paper considers an attacker with access to several versions of a filter that share most of the same input elements. We find that for typical implementations of Bloom, cuckoo, and quotient filters, the attacker gains little or no advantage with access to multiple versions of a filter. However, typical xor filters do reveal more information about their input elements by querying multiple versions of a filter, and we propose techniques to enhance the privacy of xor filters and others.

In the Uncoordinated Unique Identifiers Problem (UUIDP) there are n independent instances of an algorithm A that generates IDs from a universe (1, ..., m) , and there is an adversary that requests IDs from these instances. The goal is to design A such that it minimizes the probability that the same ID is ever generated twice across all instances, that is, minimizes the collision probability. Crucially, no communication between the instances of A is possible. Solutions to the UUIDP are often used as mechanisms for surrogate key generation in distributed databases and key-value stores. In spite of its practical relevance, we know of no prior theoretical work on the UUIDP.

A retrieval data structure for a static function $f:S\rightarrow \{0,1\}^r$ supports queries that return $f(x)$ for any $x \in S$. Retrieval data structures can be used to implement a static approximate membership query data structure (AMQ), i.e., a Bloom filter alternative, with false positive rate $2^{-r}$. The information-theoretic lower bound for both tasks is $r|S|$ bits. While succinct theoretical constructions using $(1+o(1))r|S|$ bits were known, these could not achieve very small overheads in practice because they have an unfavorable space--time tradeoff hidden in the asymptotic costs or because small overheads would only be reached for physically impossible input sizes. With bumped ribbon retrieval (BuRR), we present the first practical succinct retrieval data structure. In an extensive experimental evaluation BuRR achieves space overheads well below 1\,\% while being faster than most previously used retrieval data structures (typically with space overheads at least an order of magnitude larger) and faster than classical Bloom filters (with space overhead $\geq 44\,\%$). This efficiency, including favorable constants, stems from a combination of simplicity, word parallelism, and high locality. We additionally describe homogeneous ribbon filter AMQs, which are even simpler and faster at the price of slightly larger space overhead.