摘要
现有的XML关键字查询算法都是基于前缀编码,而这种编码方式会产生公共祖先重复比较CAR(Common Ancestor Repetition)问题.针对这一问题,提出一种基于区间编码的XM L关键字查询算法In Search(Interval Search).该算法首先建立基于区间编码的区间索引In Index(Interval Index),计算节点之间的最小范围值和最小公共祖先,遍历区间索引计算候选SLCA节点集合,过滤候选SLCA节点集合,得到SLCA节点集合.理论和实验结果表明,In Search算法是一种高效的SLCA节点查询算法.
Existing XML keyword search algorithms are based on prefix encodeing,and this will have a CAR （Common Ancestor Repetition ） problem. To solve this problem, this paper proposes an algorithm called InSearch （ Interval Search） based on interval encoding to search SLCA nodes. The algorithm firstly establish InIndex （ Interval Index ） based on the minimum interval between node, then compute minimum range and minimum common ancestor between nodes,traversing interval index to calculate SLCA candidate set of nodes, finally filter candidate SLCA set to get SLCA node collection. Theoretical and experimental results show that, InSearch algo- rithm is an efficient search algorithm to get SLCA nodes.
出处
《小型微型计算机系统》
CSCD
北大核心
2016年第5期933-937,共5页
Journal of Chinese Computer Systems
基金
国家自然科学基金项目(61163015)资助
内蒙古自然科学基金重点项目(2013MS0909)资助
内蒙古自治区高等学校科学研究项目(NJZY156)资助
内蒙古自治区高等学校科学研究项目(NJZY143)资助
