Schema validation via streaming circuits

XML schema validation can be performed in constant memory in the streaming model if and only if the schema admits only trees of bounded depth—an acceptable assumption from the practical view-point. In this talk I will present a refinement of the streaming model that take into account that data can be streamed block-by-block, rather then letter-by-letter. Therefore, it provides opportunities to speed up the computation by parallelizing the processing of each block. For this purpose I will introduce a new fine-grained parallel model of computation: the *streaming circuits*. This model process words of arbitrary length in blocks of fixed size, passing constant amount of information between blocks. It allows us to transfer fundamental results about the circuit complexity of regular languages to the setting of streaming schema validation, which leads to effective constructions of streaming circuits of depth logarithmic in the block size, or even constant under certain assumptions on the input schema.

Authors

• Charles Paperman

Keywords

No keywords are indexed for this paper.