Ribbon: Fast Succinct Static Retrieval and Approximate Membership

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.