【作者】 包小源； 宋再生； 唐世渭； 杨冬青； 王腾蛟；

【Author】 BAO Xiao-Yuan,SONG Zai-Sheng,TANG Shi-Wei,YANG Dong-Qing,and WANG Teng-Jiao (Deptartment of Computer Science & Technology,Peking University,Beijing 100871)

【机构】 北京大学计算机科学与技术系；

【摘要】 针对形如//element₁/element₂/…/element_m的查询,提出了一种基于后缀树（suffix tree）的XML索引结构SuffIndex.SuffIndex的构造通过只对OEM数据树遍历一次以及在SuffIndex中引入后缀链（Sufflink）的方法,从而达到较低的构造代价.SuffIndex中所有结点利用Hash表保存到其所有子结点的指针,最终使查询//element₁/element₂/…/element_m的处理代价为O（m）.更多还原

【Abstract】 SuffIndex—an XML index structure based on suffix tree is proposed.Suff Index can efficiently be used for evaluation of XPath queries which have the form of//element₁/element₂/…/element_m.The construction of Suff Index is carried out by traveling source OEM data tree only once and introducing Sufflinks into Suff Index so that the cost of construction is low.At the same time,each node in SuffIndex has a hash table to store pointers to all its children and in each index node there is an extent set in which all items are the result of path query of form//element₁/element₂/…/element_m.All these make the cost of querying//element₁/element₂/…/element_m into O（m）.更多还原