xmltk: An XML Toolkit for Lightweight XML Stream Processing

Overview

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.

From a technical point of view, it is essential for XML Toolkit commands to parse XML data and process a collection of XPath expressions. As a common library for these command, we have implemented a novel two technologies to realize a high-throuput XML data processing: 1) Lazy DFA (deteministic finite automaton that is constructed lazily) based XPath processor, and 2) SIX (streaming index for XML data) for XML parser.

We have implemented those Lazy DFA and SIX on our own tokenized (binary) SAX parser and xerces1_4_0 SAX parser.

History

Xmltk began life as a research project at the University of Washington, where it was supported by a generous gift from Microsoft and by Dan Suciu's NSF CAREER Grant 0092955 and Alfred P. Sloan Research Fellowship.

The project is now an open-source project

Getting Involved

See the project group page
See the tutorial (V1.02 September 5, 2002)
See how to download. This describes the details of how to download and navigates you the XMLTK download page on the xmltk.sourforge.net.
View the project mailing list
Browse the CVS repository

Presentation Slides

Slides presented at PlanX'2002.
Slides for an invited talk at SPIRE'2002.

Technical Documents

A paper in CIKM'2003 describing space optimization techniues and branching XPath expressions processing techniques using Lazy DFA: PDF format.
A paper in ICDT'2003 describing Lazy DFA based XPath expressions processing algorithm: Research Index.
A paper in PlanX'2002 describing the toolkit commands, tokenized SAX parser, and streaming index (SIX): PDF format.
An invited paper in SPIRE'2002: in PS format.
Binary format specification (a bit out of date)

Related work

Xmill, the XML compression tool of ill-repute, has been incorporated into this toolkit. The original web page for Xmill can be found here.
XML real data links and repository for your experiments

comments: tjgreen@users.sourceforge.net