Tipo di tesi
Tesi di laurea magistrale
Titolo
Engineering data structures for the approximate range emptiness problem
Corso di studi
INFORMATICA
Parole chiave
- algorithm engineering
- compressed data structures
- range filters
Data inizio appello
02/12/2022
Riassunto (Italiano)
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.
