The Streaming Complexity of Validating XML Documents
Christian Konrad, Frédéric Magniez · arXiv (Cornell University) · 2010
We study the complexity of validating XML documents against any given DTD in the context of streaming algorithms with external memory. We design a deterministic algorithm that solves this problem with memory space $O(\log^2 N)$, a constant number of auxiliary read/write streams, and $O(\log N)$ total number of passes on the XML document of size $N$ and auxiliary streams. An important intermediate step is the memory-efficient computation of the FCNS encoding of the initial XML document. Then, validity can already be decided in one-pass with memory space $O(\sqrt{N\log N})$, and no auxiliary streams. A second but reverse pass makes the memory space collapse to $O(\log^2 N)$. This suggests a systematic use of the FCNS encoding for large XML documents, since, without this encoding, there are DTDs against which validating XML documents requires memory space $\Omega(N/p)$ for any $p$-pass streaming algorithm without auxiliary streams, even if randomization is allowed. Last, for the special case of validating XML documents encoding binary trees, we give a deterministic one-pass algorithm with memory space $O(\sqrt{N})$, and prove its optimality, up to a multiplicative constant, even if randomization is allowed.