Compressed Static Functions with Applications
- Day - Time: 13 June 2013, h.14:30
- Place: Area della Ricerca CNR di Pisa - Room: C-29
Speakers
Referent
Abstract
Given a set of integer keys from a bounded universe along with associated data, the dictionary problem asks to build a data structure able to answer efficiently 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.
This seminar will describe a recent result presented at ACM-SIAM SODA 2013 which provides time and space optimal solutions for three well-established relaxations of this basic problem: (Compressed) Static functions, Approximate membership and Relative membership.
NOTE: This seminar belongs to the series of seminars presented by the winners of the prize "Young researchers ISTI 2013". Rossano Venturini placed third in the Young researcher category.