Appears in collection : 2016 - T1 - WS4 - Inference problems theme

Today, XML (eXtensible Markup Language) is ubiquitous. For example, it is the standard file format for data exchange on the Internet, and (often massive) XML databases are widely employed. Streaming XML, i. e. , the processing of XML streams, gained popularity in recent years. In many applications, streaming processing is simply the only option (e. g. when monitoring data in sensor networks), but also in application where more involved approaches are possible, streaming algorithms often outperform usual non-streaming approaches. In this presentation, we discuss some of the challenges that arise when processing streaming XML. We discuss streaming algorithms for fundamental XML-related problems such as well-formedness and validity of XML documents. Presented techniques include hashing, randomization and communication complexity.