Sketch-Based Summarization of Ordered XML Streams

In this paper, we tackle the problem of approximately answering a continuous aggregate query over an XML stream using limited memory. This problem is key in the development of tools for the on-line monitoring and analysis of streaming XML data, such as complex event streams, RSS feeds, or workflow traces. We introduce a novel technique that supports XML queries with any combination of the common XPath axes, namely, ancestor, descendant, parent, child, following, preceding, following-sibling, and preceding-sibling. At the heart of our approach lies an efficient transform that reduces a continuous XML query to an equi-join query over relational streams. We detail the transform and discuss its integration with randomized sketches as a basic mechanism to estimate the result of the XML query. We further enhance this mechanism with structural sieving, a technique that takes advantage of the XML data and query characteristics in order to improve the accuracy of the sketch-based approximation. We present an extensive experimental study on real-life and synthetic data sets that validates the effectiveness of our approach and demonstrates its advantages over existing techniques.