Approximate Validity of XML Streaming Data
Huang Xiao Cheng, Li Jun, Michel de Rougemont · 2008
We present a SAX implementation of the statistical embedding associated with XML data, introduced in [1], [2], which allows to efficiently decide eps-validity to any DTD or Schema, for the Edit Distance with Moves. It associates a generalized k-gram to unranked labelled trees (with k = 1/epsiv) from which any regular property can be approximately decided. We show how to exactly compute the k-gram with a SAX implementation using a memory of size d, the depth of the tree, and an approximate k-gram with queues of size M = 2kand a global memory of size 2kin the worst-case. Experiments on large XML files from the XML benchmark project confirm the error analysis for various values of M.