Dynamic Rank/Select Dictionaries with Applications to XML Indexing

A. Gupta, W.-K. Hon, R. Shah, and J. S. Vitter. ``Dynamic Rank/Select Dictionaries with Applications to XML Indexing,'' submitted.

Full text (Adobe pdf format)

We consider a central problem in text indexing: Given a text T over an alphabet $\Sigma$, construct a compressed data structure answering the queries $\mathit{access}(i)$, $\mathit{ranks}(i)$, and $\mathit{selects}(i)$ for a symbol  $s \in \Sigma$. Many data structures consider these queries for static text T. We consider the dynamic version of the problem, where we are allowed to insert and delete symbols at arbitrary positions of T. This problem is a key challenge in compressed text indexing and has direct application to dynamic XML indexing structures that answer subpath queries [XBW].

We build on the results of [RRR, GMR] 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((1/\epsilon)n^\epsilon)$, we suggest how to support $\mathit{ranks}(i)$, $\mathit{selects}(i)$, and $\mathit{access}(i)$ queries in $O((1/\epsilon)\log\log n)$ time, for any $\epsilon < 1$. The best previous query times for this problem were $O(\log n \log \vert\Sigma\vert)$, given by [Makinen Navarro]. Our bounds are competitive with state-of-the-art static structures [GMR]. Some applicable lower bounds for the partial sums problem [PD] show that our update/query tradeoff is also nearly optimal. In addition, our space bound is competitive with the corresponding static structures. For the special case of bitvectors (i.e., $\vert\Sigma\vert = 2$), we also show the best tradeoffs for query/update time, improving upon the results of [Makinen Navarro, Hon, RRR].

Our focus on fast query/slower update is well-suited for a query-intensive XML indexing environment. Using the XBW transform [XBW], we also present a dynamic data structure that succinctly maintains an ordered labeled tree T and supports a powerful set of queries on T.