Light-weight acceleration for streaming XML document filtering using path tries
Shuichi Mitarai, Akira Ishino, Masayuki Takeda · 2007
This paper proposes a scalable XML filtering basing on preprocessing of XML data. XML data is preprocessed and transformed into a pair of a path trie and a binary XML data. The path trie is the trie representing the set of strings of tag names along with root-to-leaf paths, and the binary XML data is obtained from the original XML data by replacing every start tag and the corresponding end tag with special byte codes, respectively. Each occurrence of the special byte code for a start tag is followed by ID of the corresponding node of the path trie. Path pattern matching is performed against the path trie. Since the path trie is much smaller than the XML data, a drastic speedup is possible. Query pattern processing is done by combining the keyword occurrences found in scanning of the binary XML data with the information added to path trie node implied by node IDs embeded in the binary XML data. Experimental results show that, the processing time and memory requirement of our method are, respectively, 1/6–1/4 and 1/6 compared with XMLTK, a state-of-the-art streaming XML processor.