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.
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

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