InSearch:一种高效的XML关键字查询算法  

InSearch: An Efficient Algorithm for XML Keyword Search

作　　者：张晓琳[1] 郝琨[1] 郭丹丹[1] 张换香[1] 刘立新[1] 

机构地区：[1]内蒙古科技大学信息工程学院,内蒙古包头014010

出　　处：《小型微型计算机系统》2016年第5期933-937,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61163015)资助;内蒙古自然科学基金重点项目(2013MS0909)资助;内蒙古自治区高等学校科学研究项目(NJZY156)资助;内蒙古自治区高等学校科学研究项目(NJZY143)资助

摘　　要：现有的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.

关 键 词：XML 关键字查询 区间编码 InSearch 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]