Sketch-Based Summarization of Ordered XML Streams

XML streams, such as RSS feeds or complex event streams, are becoming increasingly pervasive as they provide the foundation for a wide range of emerging applications. An important problem in this context is the realization of continuous queries that can support on-line monitoring and analysis of the streaming XML data. The evaluation of exact results, however, can be prohibitively expensive for the resource-restricted environment of a streaming application. This leads naturally to the use of approximation techniques that can provide an on-demand estimate for the result of a continuous XML query. This paper introduces a new technique for approximately answering a complex aggregate query over an XML stream using limited memory.