Fast Smallest Lowest Common Ancestor Computation Based on Stable Match
Fast Smallest Lowest Common Ancestor Computation Based on Stable Match
复制标题
基于稳定匹配的快速最小最小共同祖先计算
DOI：
10.1007/s11390-013-1337-1
复制
发表时间：
2013-03
影响因子：
0.7
通讯作者：
汤显
中科院分区：
文献类型：
--
作者：
周军锋;蓝国祥;陈子阳;汤显
本文主要研究基于最小最低共同祖先语义的XML关键字查询的高效处理。对于一个给定的关键字查询问米,我们建议使用稳定匹配作为SLCA计算的基础,在每一个稳定匹配m由m节点属于m不同关键字倒问:m列表满足最低,没有其他共同祖先(LCA)节点问的可以找到位于第一个节点后的m和m的LCA的后裔,基于定位的操作稳定的匹配可以跳过更无用的节点。我们提出了两种基于稳定匹配的SLCA计算算法，即BSLCA和HSLCA。BSLCA从最短到最长每次处理两个关键字倒排表，而HSLCA对所有关键字倒排表进行整体处理，避免了BSLCA调用冗余计算的问题。我们的大量实验结果根据各种评估指标验证了我们的方法的性能优势。
In this paper, we focus on efficient processing of XML keyword queries based on smallest lowest common ancestor (SLCA) semantics. For a given query Q with m keywords, we propose to use stable matches as the basis for SLCA computation, where each stable match M consists of m nodes that belong to the m distinct keyword inverted lists of Q. M satisfies that no other lowest common ancestor (LCA) node of Q can be found to be located after the first node of M and be a descendant of the LCA of M, based on which the operation of locating a stable match can skip more useless nodes. We propose two stable match based algorithms for SLCA computation, i.e., BSLCA and HSLCA. BSLCA processes two keyword inverted lists each time from the shortest to the longest, while HSLCA processes all keyword inverted lists in a holistic way to avoid the problem of redundant computation invoked by BSLCA. Our extensive experimental results verify the performance advantages of our methods according to various evaluation metrics.