|
An XML Toolkit for Light-weight XML Stream Processing
|
|
Download
Download:
Additional info about the software, including license agreement is here .
Abstract
The XML toolkit consists of a number of utilities that perform simple operations on
XML files. We have built a sort utility, an aggregation utility, a mapping utility to
transform Unix directory hierarchies to XML, and some smaller utilities.
Utilities can be combined sequentially, in pipes, to perform more complex XML
processing. The toolkit defines a binary XML format that is more compact than
XML (by a factor of two, on average). This format can be optionally used as
communication format in a pipeline, to achieve speedups by a factor of two. The
toolkit defines a novel index called stream index, SIX. All
utilities check if the input data has a pre-computed SIX, and use it if it is
available.
There are two important technical contributions in the toolkit: a highly scalable XML stream processor,
and an XML stream index. Both have important applications beyond the toolkit, to XML packet routing and to selective dissemination of
information. The XML stream processor achieves a sustained throughput of about 5.6MB/s and scales up to large numbers of XPath expressions
(up to 1,000,000 in our experiments). Since the processor transforms all XPath expressions into a single deterministic automaton, we did a
detailed theoretical analysis to prove that the number of states in the automaton remains relatively small. The stream index is the first
attempt to index streaming data, rather than stored data. It has to be small compared to the data stream (ours is 6% or less), and has to
arrive just in time with the data stream. We measured speedups of up to a factor of four in processing XML streams with the index.
Acknowledgments
This project is supported by a generous gift from Microsoft and by Suciu's NSF CAREER Grant
0092955 and Alfred P. Sloan Research Fellowship.
Technology
All tools in the toolkit parse the XML data, process a collection of XPath
expressions, do some simple processing, then output some XML result. To speedup
the XPath processing part we have implemented a novel two technologies that
achieve very high XML throughput: 1) All XPath expressions are converted to one
single Lazy DFA (deteministic finite automaton that is constructed lazily), and 2)
We have developed a new structured called Stream IndeX (SIX) that allows
us to skip portions of the XML document that are not needed for the particular
set of XPath expressions.
We have implemented those Lazy DFA and SIX on our own tokenized (binary) SAX parser and xerces1_4_0 SAX parser. We now release the formar version of XML Toolkit library (See download) and plan to release the latter one in future.
Other Information
Download and references
Presentation Slides
Xmill: The XML Compressor
See http://www.cs.washington.edu/homes/suciu/XMILL.
Technical Documents
XML data for experiments
XML Toolkit Mailing List
XML Toolkit Mailing List is now available. See http://mailman.cs.washington.edu/mailman/listinfo/xmltk.
Members
The sun never sets on the XMLTK project! (Seattle, Paris, Yokosuka Japan,...)
Suggestions for Future Projects
Some suggestions for future projects are here.
|
 |
Department of Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
|
CSE Home