XMLPrelteringasaString分析.PDFVIP

XML Prefiltering as a String Matching Problem Christoph Koch, Stefanie Scherzinger, Michael Schmidt Saarland University Database Group Saarbr¨ucken, Germany {koch,scherzinger}@infosys.uni-sb.de, mschmidt@informatik.uni-freiburg.de Abstract— We propose a new technique for the efficient search the input with a fixed-size window in a single pass. Within the and navigation in XML documents and streams. This technique window held in main memory, we can locally jump back and takes string matching algorithms designed for efficient keyword forth, all the while trying to quickly process the input by skip- search in flat strings into the second dimension, to navigate in tree structured data. We consider the important XML data man- ping characters. As we confirm in our experiments, this results agement task of prefiltering XML documents (also called XML in significant speedups for searching flat strings and XML data projection) as an application for our approach. Different from alike. In particular, both the runtime costs and the number of existing prefiltering schemes, we usually process only fractions of character comparisons of our technique are comparable with the input and get by with very economical consumption of both Boyer-Moore style string matching algorithms. main memory and processing time. Our experiments reveal that, already on low-complexity problems such as XPath filtering, in- While the runtime algorithm is simple, lean, and efficient, memory query engines can experience speed-ups by two orders the static analysis computing the runtime data structures is of magnitude.