A Framework for Dynamizing Succinct Data Structures

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

subpath

queries [2]. 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

char

(

i

),

rank

s

(

i

), and

select

s

(

i

) for a symbol

s

 ∈ 

Σ

. Many data structures consider these queries for static text

T

[5,3,16,4]. 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

O

(

n

ε

), 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

rank

s

(

i

),

select

s

(

i

), and

char

(

i

) queries in

O

(

t

(

n

) + loglog

n

) time, for any constant

ε

> 0. When |

Σ

| = polylog(n), we achieve

O

(1) query times. Our update/query bounds are near-optimal with respect to the lower bounds from [13].