Succinct data structures: Towards optimal representation of massive data

Srinivasa Rao Satti
교수
서울대학교 컴퓨터공학부.
일시: 
2013년 5월 23일 목요일 PM 12:00 - 2013년 5월 23일 목요일 PM 1:00
장소: 
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.