New Directions in Succinct Data Structures - Theory/Algorithms talk by Ian Munro, U. Waterloo

Title:  New Directions in Succinct Data Structures

Speaker:  Dr. J. Ian Munro
Cheriton School of Computer Science
University of Waterloo

Host:  David Kirkpatrick

Abstract:
Algorithms and data structures developed for one application domain
and set of constraints are often applied to other situations. Succinct
data structures were developed, to a large extent, for extremely space
efficient string indexing. We now seem to be in an era in which such
methods are being used for applications in which space requirements
are not as severe and indeed for applications outside stringology,
such as geometric problems. We give a couple of examples of this trend
through recent results on reporting range majority and dynamic
orthogonal range counting.
This is joint work with Meng He et al.