KFilter: XML Stream Filtering Based On Keyword Search

With the fast development of Internet and XML gradually being the standard of data storing and exchanging, there emerge many applications which are closely associated with XML stream, for instance, SDI (Selective Dissemination of Information).Almost all the research on XML stream filtering are based on XPath or XQuery. This mainly brings two problems: First, users should master a complicate query language; Second, in order to write their queries, users have to be familiar with the schema of the incoming stream.To these two problems, paper[20] first proposed the solution that apply keyword search on XML stream filtering. Keyword search is a user-friendly query manner and it has been widely used in the domain of information retrieval. Simplicity is the most significant advantage of keyword search. In this way, users do not need to master a query language and know the structure of the incoming stream. Although [20] proposed an algorithm called Lookup which is based on a stack, it is not efficient. This algorithm is just a solution to single query, the authors does not proposed a solution to multiple queries. In fact, there are always a lot of queries in the XML stream filtering system.In this paper we first introduce the conception of Rightmost Contain Border, and then use it to propose the algorithm called XVirtualStack(XVS), which deals with single query and uses a virtual stack and a position vector to buffer all the keywords appearing in the incoming stream. Based on XVS, we give the system architecture of kFilter and then propose multi-XVS which can process a large number of queries. Finally we do experiments on both XVS and multi-XVS. The results show that our algorithm and system are efficient and reliable.