Abstract: A new method to efficiently evaluate XPath over XML documents streams is proposed. The FA (finite automata)-based index structure is designed to boost the evaluation, according to the semantic features of XPath. To overcomethe cache miss when accessingthe hash table, a software-prefetching algorithm which can achieve great speedup for the accesses of hash table is proposed. A thorough experimental study shows that proposed system can deal with workloads containing millions of XPath subscriptions efficiently.

Key words: XML, XPath, software prefetch, publish/subscribe

摘要： 提出了在XML数据流上有效评测XPath订阅的技术和方法。根据XPath层次结构的语义特征, 设计了基于非确定有限状态自动机的动态索引结构, 使得具有相同前缀的XPath查询可以共享存储索引的空间和共享查找索引的计算。基于栈的新评测算法设计了高速缓存软件预取技术, 以处理评测过程中频繁出现的cache缺项问题。系统取得了很高的性能, 通过全面的实验表明, 系统可以有效处理超过百万以上XPath查询的负载量。

关键词: XML, XPath, 软件预取, 发布/订阅