Validating XML Documents in the Streaming Model with External Memory

Details Validating XML Documents in the Streaming Model with External Memory Validating XML Documents in the Streaming Model with External Memory

2010-12-15

arxiv.org/abs/1012.3311v3

Computer Science

Data Structures and Algorithms

Change title. Remove a statement on a lower bound (now Conjecture 2 in Annexe B) since the proof was incomplete

Scientific paper

We study the problem of validating XML documents of size $N$ against general DTDs in the context of streaming algorithms. The starting point of this work is a well-known space lower bound. There are XML documents and DTDs for which $p$-pass streaming algorithms require $\Omega(N/p)$ space. We show that when allowing access to external memory, there is a deterministic streaming 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 and auxiliary streams. An important intermediate step of this algorithm is the computation of the First-Child-Next-Sibling (FCNS) encoding of the initial XML document in a streaming fashion. We study this problem independently, and we also provide memory efficient streaming algorithms for decoding an XML document given in its FCNS encoding. Furthermore, validating XML documents encoding binary trees in the usual streaming model without external memory can be done with sublinear memory. There is a one-pass algorithm using $O(\sqrt{N \log N})$ space, and a bidirectional two-pass algorithm using $O(\log^2 N)$ space performing this task.

Affiliated with

Also associated with

No associations

Rating

Validating XML Documents in the Streaming Model with External Memory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Validating XML Documents in the Streaming Model with External Memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Validating XML Documents in the Streaming Model with External Memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-13845