PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Belazzougui D., Venturini R. Compressed static functions with applications. In: SODA 2013 - 24th Annual ACM-SIAM Symposium on Discrete Algorithms (New orleans, Louisiana, USA, 5 gennaio 2013). Proceedings, pp. 229 - 240. SIAM-ACM, 2013.
 
 
Abstract
(English)
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.
URL: http://knowledgecenter.siam.org/soda/
Subject Compressed Data Structures
E.1 DATA STRUCTURES


Icona documento 1) Download Document PDF
Icona documento 2) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional