Hash-Search:基于哈希表的快速XML关键字检索算法
随着XML的广泛应用,XML上的关键字检索逐渐成为一个研究热点.现有的关键字检索方法主要基于LCA计算和候选点选择两种操作,存在以下问题:首先,现有方法利用Dewey编码来表示结点,LCA的计算过程需要逐段地比较Dewey编码,当XML深度很大时,大量的LCA计算会影响算法的性能.其次,为了确定候选点(即用于进行LCA计算的结点),需要对结点集进行遍历,当结点集很大时,查找过程比较耗时.针对以上问题,首先提出一种基于哈希表的索引结构来记录结点和标签之间的关系。基于这种索引结构,进一步设计了高效的关键字检索算法——Hash-Search算法,避免了LCA计算和确定候选点过程.在理论上提供了算法的正确性证明和复杂度分析,并进行了实验测试,表明Hash-Search算法是一种高效的XML关键字检索算法。
哈希表 关键字检索 XML 结点集遍历 索引结构 Hash-Search
王伟彦 张博 王晓玲 周傲英
复旦大学Web数据库与P2P计算实验室 上海 200433 华东师范大学海量计算研究所 上海 200062
国内会议
桂林
中文
174-177,235
2008-10-24（万方平台首次上网日期，不代表论文的发表时间）