Event type:
Guest lecture
Event time:
13.04.2017 - 15:15 - 16:00
Lecturer :
Rajeev Raman
Place:
B119
Description:
Driven by the increasing need to analyze and search for complex patterns
in very large data sets, the area of compressed and succinct data
structures has grown rapidly in the last 10-15 years. Such data
structures have very low memory requirements, allowing them to fit into
the main memory of a computer, which in turn avoids expensive
computation on hard disks.
in very large data sets, the area of compressed and succinct data
structures has grown rapidly in the last 10-15 years. Such data
structures have very low memory requirements, allowing them to fit into
the main memory of a computer, which in turn avoids expensive
computation on hard disks.
This talk will focus on a sub-topic that has become popular recently:
encoding "the data structure" itself. Some data structuring problems
involve supporting queries on data, but the queries that need to be
supported do not allow the original data to be deduced from the queries.
This presents opportunities to obtain space savings even when the data
is incompressible, by pre-processing the data, extracting only the
information needed to answer the queries, and then deleting the
data. The minimum information needed to answer the queries is called the
effective entropy of the problem: precisely determining the effective
entropy can involve interesting combinatorics.