We present a framework to dynamize succinct data structures,
to encourage their use over non-succinct versions in a wide
variety of important application areas. Our framework can
dynamize most state-of-the-art succinct data structures for
dictionaries, ordinal trees, labeled trees, and text
collections. Of particular note is its direct application to
XML indexing structures that answer
queries. Our
framework focuses on achieving information-theoretically
optimal space along with near-optimal update/query bounds.
As the main part of our work, we consider the following
problem central to text indexing: Given a text T over an
alphabet
,
construct a compressed data structure
answering the queries
,
,
and
for a symbol
.
Many data
structures consider these queries for static text T. We
build on these results and give the best known query bounds
for the dynamic version of this problem, supporting
arbitrary insertions and deletions of symbols in T.
Specifically, with an amortized update time of
,
any static succinct data structure D for
T, taking t(n) time for queries, can be converted by our
framework into a dynamic succinct data structure that
supports
,
,
and
queries in
time, for any constant
.
When
,
we achieve
O(1) query times. Our update/query bounds are near-optimal
with respect to the lower bounds.