Given a set of integer keys from a bounded universe along with associated data, the dictionary problem asks to answer two queries: membership and retrieval. Membership has to tell whether a given element is in the dictionary or not; Retrieval has to return the data associated with the searched key. In this paper we provide time and space optimal solutions for three well-established relaxations of this basic problem: (Compressed) Static functions, Approximate membership and Relative membership.
Compressed static functions with applications
Venturini R
2013
Abstract
Given a set of integer keys from a bounded universe along with associated data, the dictionary problem asks to answer two queries: membership and retrieval. Membership has to tell whether a given element is in the dictionary or not; Retrieval has to return the data associated with the searched key. In this paper we provide time and space optimal solutions for three well-established relaxations of this basic problem: (Compressed) Static functions, Approximate membership and Relative membership.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
prod_277560-doc_78202.pdf
solo utenti autorizzati
Descrizione: Compressed Static Functions with Applications
Tipologia:
Versione Editoriale (PDF)
Dimensione
152.14 kB
Formato
Adobe PDF
|
152.14 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
