Compressed Static Functions with Applications

Day - Time: 13 May 2013, h.11:00
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 is the second one of the series of six seminars presented by the winners of the prize "Young researchers ISTI 2013". Rossano Venturini placed third in the Young researcher category.