Succinct data structures: Towards optimal representation of massive data

Srinivasa Rao Satti
서울대학교 컴퓨터공학부.
Thursday, May 23rd 2013, 12:00pm - Thursday, May 23rd 2013, 1:00pm
Rm 309, Bldg 302.


This talk introduces the concept of succinct data structures through a few examples. A succinct data structure represents the given data in close to (information-theoretic) optimal space while supporting the required queries on the data efficiently. The concept was introduced by Jacobson in the late 80's, and there has been a significant progress in the last two decades. Succinct data structures are not only applicable in places where one needs to store massive amounts of data in a space-efficient and indexable manner, but also have potential applications in representing data on limited-memory devices such as mobile phones, PDAs etc.