ETD

• algorithm engineering
• compressed data structures
• range filters

This thesis deals with the design of data structures for the approximate range emptiness problem, which are a generalisation of Bloom filters from point to range queries and an essential tool in the design of key-value stores. We design a data structure that improves the space bound of known solutions and matches the lower bound for this problem (up to a lower-order additive term), while being simple and offering efficient query time. An experimental comparison of this data structure with state-of-the-art solutions shows improved space-time and space-error trade-offs.