Succinct data structures: Towards optimal representation of massive data
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.