Efficient XPath Query Algorithms Over XML Streams

Wim the rapid XML data increasing.especially with the large XML dataemerging,XML query research is becoming the hotspot in both industry andacademia.The traditional XML query technology needs to parse XML document inmain memory and index the XML structure locally,and construct query tree andquery plan per query statement to produce the final results.This approach COSTS a lot of storage space and need to pre—parse the XML document in advance,which is notsuitable for XML stream query.In this paper,the XML stream query processin algorithms are studied and implemented along with the technologies of XML filter,XPath evaluation and stream index.The main contribution in this paper follows:·XML stream model and stream expression for XML tree model are proposed;·The current XML query standards are introduced and compared;·Two kinds ofstream index SI and SSI are proposed;·Three XPath evaluaion algorithms are proposed and implemented,including NFA based XPath evaluation,SI—NFA based XPath evaluation and Multi—NFA based multi-XPath evaluation;·A novel change detection algorithm for XML data streams(SDifr)and an incremental query algorithm based on SDiff are proposed;·Extensive experiments are given to show all algorithms have linear time and space complexity,and are capable of processing a large scale of XML stream data.