基于XML的发布/订阅系统的评测算法研究

北京大学学报（自然科学版）

基于XML的发布/订阅系统的评测算法研究

李永锋

北京大学地球与空间科学学院地质信息系统实验室,北京100871

收稿日期:2008-06-20 出版日期:2009-09-20 发布日期:2009-09-20

A Novel Evaluating Algorithmover XML Pub/Sub Systems

LI Yongfeng

Geological Spatial Information SystemLaborotory, School of Earth and Space Sciences, Peking University, Beijing 100871

Received:2008-06-20 Online:2009-09-20 Published:2009-09-20

摘要/Abstract

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

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

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

中图分类号:

TP391

李永锋. 基于XML的发布/订阅系统的评测算法研究[J]. 北京大学学报（自然科学版）.

LI Yongfeng. A Novel Evaluating Algorithmover XML Pub/Sub Systems[J]. Acta Scientiarum Naturalium Universitatis Pekinensis.

[1]	仇睿恒,汤帜,胡薇,高良才. XTrim: 一种基于XML Schema和微型数据块优化的XML压缩方法[J]. 北京大学学报（自然科学版）, 2010, 46(5): 771-778.
[2]	姚凌青,潘懋,王占刚,屈红刚. 基于COMPOSITE设计模式与XML实现变差函数模型的一致表达与存储[J]. 北京大学学报（自然科学版）, 2008, 44(5): 787-792.
[3]	包小源,唐世渭,吴泠,杨冬青,宋再生,王腾蛟. ArithRegion——一种压缩XML的索引结构[J]. 北京大学学报（自然科学版）, 2006, 42(1): 103-109.
[4]	李军国,张立昂. 基于XML的网上数学表达式显示技术[J]. 北京大学学报（自然科学版）, 2003, 39(5): 675-680.
[5]	邓志鸿,唐世渭,张铭,杨冬青,陈捷. Ontology研究综述[J]. 北京大学学报（自然科学版）, 2002, 38(5): 730-728.
[6]	陈爱军,李琦,徐光祐. GeoML--基于XML的地理空间信息共享与互操作语言[J]. 北京大学学报（自然科学版）, 2002, 38(4): 550-555.