logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-11152022-225519


Tipo di tesi
Tesi di laurea magistrale
Autore
COSTA, MARCO
URN
etd-11152022-225519
Titolo
Engineering data structures for the approximate range emptiness problem
Dipartimento
INFORMATICA
Corso di studi
INFORMATICA
Relatori
relatore Prof. Ferragina, Paolo
relatore Dott. Vinciguerra, Giorgio
Parole chiave
  • algorithm engineering
  • compressed data structures
  • range filters
Data inizio appello
02/12/2022
Consultabilità
Non consultabile
Data di rilascio
02/12/2025
Riassunto
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.
File