Query optimization method based on automaton for content-based filtering
Tong Wang, Daxin Liu, Xuanzuo Lin · 2006
There are many Web-based applications such as XML content-based Filtering system etc. over the Internet. XML messages stream in and filter engine decide which users have potential interest based on their known requirements. However, when we process thousands of XPaths against fast XML streams, the limited main memory requirements become the bottleneck for the filter engine. We noticed that the uncertain factors in XPath expressions might lead to exponential complexity in search space. Thus, this paper proposes a novel method for XML filtering to solve the computational problem. We define a novel binary operation "product" of automata to diminish the uncertain factors thus reducing the search space. Then, we give the construction algorithms for DTD automaton and automaton product respectively. Finally, we analyze the complexity of the optimizing process and also validate the method in our experimental system.