文献类型：会议

作　　者：王伟彦 张博 王晓玲 周傲英

作者单位：复旦大学Web数据库与P2P计算实验室 上海 200433 华东师范大学海量计算研究所 上海 200062

会议文献：第二十五届中国数据库学术会议(NDBC2008)论文集

会议名称：第二十五届中国数据库学术会议(NDBC2008)

会议日期：20081024

会议地点：桂林

主办单位：中国计算机学会

出版日期：20081024

语　　种：中文

摘　　要：随着XML的广泛应用,XML上的关键字检索逐渐成为一个研究热点.现有的关键字检索方法主要基于LCA计算和候选点选择两种操作,存在以下问题:首先,现有方法利用Dewey编码来表示结点,LCA的计算过程需要逐段地比较Dewey编码,当XML深度很大时,大量的LCA计算会影响算法的性能.其次,为了确定候选点(即用于进行LCA计算的结点),需要对结点集进行遍历,当结点集很大时,查找过程比较耗时.针对以上问题,首先提出一种基于哈希表的索引结构来记录结点和标签之间的关系。基于这种索引结构,进一步设计了高效的关键字检索算法——Hash-Search算法,避免了LCA计算和确定候选点过程.在理论上提供了算法的正确性证明和复杂度分析,并进行了实验测试,表明Hash-Search算法是一种高效的XML关键字检索算法。

关 键 词：哈希表 关键字检索 XML 结点集遍历  索引结构 Hash-Search  

分 类 号：G254.23[图书情报与档案管理类] TP311.13]