节点文献

SuffIndex——一种基于后缀树的XML索引结构

SuffIndex—An XML Index Structure Based on Suffix Tree

  • 推荐 CAJ下载
  • PDF下载
  • 不支持迅雷等下载工具,请取消加速工具后下载。

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

【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)

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

【摘要】 针对形如//element1/element2/…/elementm的查询,提出了一种基于后缀树(suffix tree)的XML索引结构SuffIndex.SuffIndex的构造通过只对OEM数据树遍历一次以及在SuffIndex中引入后缀链(Sufflink)的方法,从而达到较低的构造代价.SuffIndex中所有结点利用Hash表保存到其所有子结点的指针,最终使查询//element1/element2/…/elementm的处理代价为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//element1/element2/…/elementm.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//element1/element2/…/elementm.All these make the cost of querying//element1/element2/…/elementm into O(m).

【关键词】 后缀树XML索引
【Key words】 suffix treeXMLindex
【基金】 国家“九七三”重点基础研究发展规划基金项目(G1999032705);国家“八六三”高技术研究发展计划基金项目数据库重大专项课题(2002AA4Z3440)
  • 【会议录名称】 第二十一届中国数据库学术会议论文集(研究报告篇)
  • 【会议名称】第二十一届中国数据库学术会议
  • 【会议时间】2004-10-14
  • 【会议地点】中国福建厦门
  • 【分类号】TP311.13
  • 【主办单位】中国计算机学会数据库专业委员会
节点文献中: 

本文链接的文献网络图示:

本文的引文网络