English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the problem of validating XML documents of size $N$ against generalDTDs in the context of streaming algorithms. The starting point of this work isa 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 adeterministic streaming algorithm that solves this problem with memory space$O(\log^2 N)$, a constant number of auxiliary read/write streams, and $O(\logN)$ total number of passes on the XML document and auxiliary streams.  An important intermediate step of this algorithm is the computation of theFirst-Child-Next-Sibling (FCNS) encoding of the initial XML document in astreaming fashion. We study this problem independently, and we also providememory efficient streaming algorithms for decoding an XML document given in itsFCNS encoding.  Furthermore, validating XML documents encoding binary trees in the usualstreaming model without external memory can be done with sublinear memory.There is a one-pass algorithm using $O(\sqrt{N \log N})$ space, and abidirectional two-pass algorithm using $O(\log^2 N)$ space performing thistask.

Validating XML Documents in the Streaming Model with External Memory