Bloom Filter-based Path Expression Query Processing

In the past several years, XML has been the de facto standard for data representation and exchange on the web. It is widely applied in the emerging application systems, such as Web services and personalized content delivery. In these applications, plenty of path expressions are processed against XML documents that arrive rapidly in stream form. Efficient query processing on XML stream has been a very important research challenge.In this dissertation, we focus on the research related to query processing on XML stream. Some novel methods are proposed for the processing of simple path expressions and branched path expressions respectively. The performance of these methods are evaluated according to experiments. In particular, we implement a XML stream processing prototype system. The novelty and contributions of this dissertation can be summarized as following: We propose a novel method for XML stream filtering, which uses Bloom Filters representing simple path expressions. This method supports the efficient processing of wildcard character and descendant axis of simple path expressions. To improve the filtering performance, we introduce a new data structure, Prefix Filters, to decrease the number of candidate paths. Experiments show that our Bloom filter-based method takes less time to build routing table than existing automaton-base method. And our Bloom filter-based method has a good performance with acceptable false positive when filtering XML documents of relatively small depth with millions of path queries.We propose a novel method for branched path expressions processing on XML stream, which decomposes all branched path expressions into simple path expressions and evaluates the branched queries based on the output of simple path expressions filtering. This method supports the evaluation of value predicates and processes branched path expressions in a stream fashion. Experimental results clearly confirm that this stream-based method has better performance than existing store-based approach. We present the design and implementation of XSTR, a prototype system for XML stream processing. A detailed architectural description of the system is provided, and a variety of issues in implementation are discussed. XSTR system could work as middleware component in XML stream applications.In conclusion, we study the problem of path expression query processing on XML stream, and present new methods different with existing approaches. The performance of proposed methods is evaluated by experiments. The works in this dissertation contribute to the query processing of XML stream and the development of practical technologies.