Ribbon: Fast Succinct Static Retrieval and Approximate Membership

Given a set 𝑆 ⊆ U and a function 𝑓 : 𝑆 → {0, 1}$^𝑟$ , a static retrieval data structure for 𝑓 supports queries that return 𝑓 (𝑥) for 𝑥 ∈ 𝑆 and an arbitrary value from {0, 1}𝑟 for 𝑥 ∈ U \ 𝑆. 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$^{−𝑟}$ . The information-theoretic space lower bound for both tasks is 𝑟 |𝑆 | bits, and here we aim to use space 𝑟 |𝑆 |(1 + 𝜀) bits for a small overhead 𝜀, including succinct constructions with 𝜀 = 𝑜 (1).