Compressed Static Functions with Applications

Day - Time: 13 June 2013, h.14:30
Place: Area della Ricerca CNR di Pisa - Room: C-29

Andrea Esuli


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.