收稿时间: 2016-07-22; 修改时间: 2017-06-09; 采用时间: 2019-09-13 作者简介: 覃遵跃 (1974-), 男, 湖南张家界人, 博士, 副教授, 主要研究领域为数据库技术;
汤庸 (1964-), 男, 博士, 教授, 博士生导师, CCF杰出会员, 主要研究领域为协同工作, 数据库;
徐洪智 (1974-), 男, 副教授, 主要研究领域为嵌入式系统, 并行计算;
黄云 (1976-), 男, 博士, 副教授, CCF专业会员, 主要研究领域为数据挖掘, 智能信息计算. 关键字检索具有友好的用户操作体验，该检索方式已在文本信息检索领域得到了广泛而深入的应用.对XML数据采用关键字检索是目前研究的热点.基于查询语义的XML关键字检索方法存在返回大量与用户查询意图无关的查询片段或者丢失符合用户查询意图的片段这两个问题.针对这些问题，在考虑LCA横向和纵向两个维度的基础上，提出了用户查询意图与LCA相关性的两个规则，根据两个规则定义了LCA的边密度和路径密度，建立了综合的LCA节点评分公式，最后设计TopLCA- K 算法对LCA进行排名，并利用中心位置索引CI提高了TopLCA- K 算法的效率.实验结果显示，利用所提出的方法返回的查询节点更加符合用户需求. 关键词 : XML关键字检索 TopLCA- K 算法 QIN Zun-Yue ^1,2 , TANG Yong ^1,3 , XU Hong-Zhi ² , HUANG Yun ²

1. School of Data and Computer Science, SunYat-Sen University, Guangzhou 510275, China;
2. School of Software, JiShou University, Zhangjiajie 427000, China;
3. School of Computer Science, South China Normal University, Guangzhou 510631, China

Foundation item: National High Technology R & D Program of China (863) (2013AA01A212); National Natural Science Foundation of China (61772211, 60970044, 61272067, 61363073); S & T Projects of Guangdong Province (2014B010116002, 2015B010109003, 2013B 090800024, S2012030006242, 2015B010129009) Abstract : Keyword search has a friendly user experience; the method has been widely used in the field of text information retrieval. Keyword search on XML data is a hot research topic presently. The XML keyword search method based on query semantics have two problems:(1) a large number of query fragments which are not related to the user's query intention have been returned; (2) the fragments which are consistent with the user's query intention have been missed. Aiming at these problems, two rules of user query intention and LCA correlation are proposed on the basis of the two (horizontal and vertical) dimensions of LCA. The edge density and path density of LCA are defined according to the two rules, and a comprehensive scoring formula on LCA nodes is established, finally, the TopLCA- K algorithm is designed to rank LCA. To improve the efficiency of the algorithm, center location index is designed. Experimental results show that the nodes returned by this method are more in line with the needs of users. Key words : XML keyword retrieval edge density path density TopLCA- K algorithm

XML是互联网中信息表示和交换的事实标准, 在电子政务、电子商务、金融、出版、科学数据和各种资源数字化等方面扮演着极其重要的角色.利用关键字检索XML数据, 用户不需要学习复杂的查询语言, 并且也无需预先了解XML数据的结构知识, 因此研究XML关键字检索是非常迫切和必要的.

XML关键字检索只需要返回XML树片段, 该树片段包含了匹配的所有关键字 ^[ 1 , 2 ].文献[ 3 - 8 ]详细介绍了返回XML树片段的检索方式, 通常, 这种检索方式的结果包含了每个关键字实例的一棵最小连通树, 该树的根节点是包含了所有关键字实例的最低公共祖先LCA(lowest common ancestor).LCA是针对XML关键字检索的所有可能情况, 有些LCA可能不符合用户的查询意图.为了返回与用户意图密切的LCA, 文献[ 9 - 13 ]采用过滤方法抛弃了与用户意图不相关的LCA, 但这些方法经常过滤掉了用户想要的LCA, 具有低的准确率和召回率 ^{[ 14 ]} .针对过滤语义不足的问题, 文献[ 6 , 15 , 16 ]设计了Top- k 算法, 对查询结果LCA进行排名并优先选择Top- K 个结果.对于XML数据进行关键字检索也可以通过TF*IDF和PageRank进行排名 ^{[ 1 , 9 , 14 , 17 ]} 以提高用户的检索兴趣.

虽然对XML关键字检索研究取得了很多研究成果, 但仍然存在一些问题.首先是检索质量问题, 例如通过过滤语义SLCA ^{[ 11 , 18 , 19 ]} 和ELCA ^{[ 13 , 20 ]} 来产生LCA子集, 然后对子集进行排名, 这种方法存在丢失相关查询结果的问题.第二是查询效率问题, 在检索关键字较多时将返回大量的LCA结果, 处理LCA排名主要基于关键字倒排表的规模 ^{[ 8 , 14 ]} , 因此, 当数据集规模增大时, 算法不能很好地满足应用要求.文献[ 21 ]提出了一种通用的自上而下(top-down)的处理策略来发现LCA/SLCA/ELCA语义的共同祖先重复(CAR)和访问无用节点(VUN)问题, 但不能对LCA节点进行排名.

针对上面存在的两个问题, 本文提出了对LCA直接进行排名的TopLCA- K 方法, 该方法综合考虑了查询关键字数量、边的构成和路径等情况, 然后计算出每个LCA的大小.

本文主要贡献包括:

(1) 提出了LCA与用户查询意图相关的两个规则.用户查询意图与查询关键字实例到LCA边的数量成反比, 以及用户查询意图与LCA子树路径的数量成反比.

(2) 建立了计算LCA分数的公式.根据前面提出的两个规则, 利用边密度和路径密度作为衡量LCA值的方法.

(3) 设计了计算LCA值的算法TopLCA- K .为了避免丢失部分满足用户需要的查询结果, 提出对所有LCA进行打分.为了提高查询效率, 提出了中心位置索引CI.根据LCA分数进行排名, 把最可能满足用户查询意图的LCA首先展示给用户.

(4) 利用实际的不同规模数据集对提出的算法进行了测试, 实验验证了在查询关键字个数不同的情况下, 本文提出的算法具有更高的准确率和召回率, 并且返回的 K 个结果更符合用户需要.

本文第2节介绍研究背景和相关工作.第3节介绍度量LCA大小的概念和方法以及TopLCA- K 算法.第4节显示本文提出的算法的实验结果, 以及与其他方法的比较情况.第5节总结本文的工作, 并给出未来的研究方向.

2 研究背景与相关概念 2.1 研究背景

因为XML半结构化数据不像关系数据库那样具有严格的模式, 因此对这种类型的数据进行关键字检索是一项复杂的任务.很多文献针对XML关键字检索提出了各种类型的查询语义, 可以分为基于树模型和基于图模型的查询语义.在基于树模型的关键字查询语义中, LCA是所有其他语义的基础, 其中, SLCA ^{[ 11 ]} 、ELCA ^{[ 1 , 13 ]} 、MLCA ^{[ 10 ]} 、XSearch ^{[ 9 ]} 、VLCA ^{[ 12 ]} 、TLCA ^{[ 22 ]} 等是基于LCA的代表性语义.基于图模型的查询语义主要借鉴关系数据库的关键字查询思想 ^{[ 23 ]} , 即对于给定的一组查询关键字, 返回CN(connected network).

SLCA ^{[ 11 ]} 过滤掉了后裔LCA; 在ELCA ^{[ 1 , 13 ]} 语义定义中, v 是一个LCA节点, 如果以 v 为根的子树中过滤掉所有其他以LCA节点为根的子树后, v 仍然包含所有关键字, 则 v 是一个ELCA节点; MLCA ^{[ 10 ]} 语义去掉包含了关键字标签相同但路径不同的LCA; VLCA ^{[ 12 ]} 和XSearch ^{[ 9 ]} 在LCA的基础上, 将不同关键字到LCA路径上存在的同名节点的结果排除在外.基于树模型的查询语义除了LCA之外, 还有MCT(minimal cost tree)语义 ^{[ 15 ]} .

基于图模型的查询语义把XML数据建模为一个图, 返回CN(connected network) ^{[ 24 ]} 作为关键字查询结果.每个CN都是文档树 D 的一个无环子图 T , 并且 T 包含查询 Q 中的所有关键字至少1次, 而 T 的任何真子图都不包含 Q 中的所有关键字.基于CN的一种典型查询语义是MCN(meaning connected network) ^{[ 19 ]} , 该查询语义找出给定关键字之间有意义的关系.XKeyword ^{[ 24 ]} 和BLINKs ^{[ 25 ]} 也是基于图的查询语义.

已经提出的针对XML关键字查询语义, 或者基于LCA进行过滤, 例如SLCA、ELCA等, 或者基于CN进行过滤, 例如MCN.虽然这些过滤语义可以返回更加贴近用户意图的查询结果, 但用户查询往往很复杂, 因此这些过滤的查询语义也显示出了低召回率问题 ^{[ 14 ]} .为了弥补过滤查询语义存在低召回率问题, 对符合条件的查询结果进行排名是一种有效的解决办法.对查询结果进行排名, 可以把与用户查询意图更相关的查询结果放在前面.已有排名方法分为两种, 一种是根据XML结构和语义上的相关性进行排名 ^{[ 1 , 6 , 9 , 14 , 15 , 26 , 27 ]} , 另一种是按照某种统计度量办法对LCA节点进行评分排名 ^{[ 1 , 6 , 9 , 14 , 15 , 28 - 30 ]} .例如XRank ^{[ 1 ]} 对PageRank算法进行了改进而适用于XML关键字查询结果排名; XSearch ^{[ 9 ]} 对TF*IDF函数进行改进使之适用于XML文档树结构的关键字查询排名; XReal ^{[ 4 ]} 的排序思想基于TF*IDF, 考虑的排序因素包括关键字频率、关键字出现顺序、关键字在查询结果中的位置以及结果的大小等.Termehchy和Winslett ^{[ 14 ]} 通过采用交互信息来计算结果相干性以进行排名; Nguyen和Cao ^{[ 31 ]} 使用交互信息来比较结果, 然后在查询结果之间定义了一个支配关系来进行排名; SAIL ^{[ 15 ]} 定义了最小代价树, 并且通过使用链接来分析关键字对之间的相关性, 最后返回Top- k 查询结果; XBridge ^{[ 28 ]} 在使用打分函数时考虑了查询结果的结构, 然后对查询结果进行分类; 文献[ 25 ]基于图模型数据, 提出了一种结合结构大小、PageRank以及TF*IDF这3种排序思想的混合排名机制.文献[ 26 ]提出了一个新的对XML数据的关键字查询进行排名和过滤语义的方法XReason语义, 该方法基于模式推理, 模式记录了查询匹配的结构和语义特征.为了利用模式进行推理, 提出了模式之间的同态关系.该方法的优点是从整体的角度考虑查询匹配, 避免了以前语义利用局部XML子树比较查询匹配存在的缺陷.

2.2 相关概念

一般情况下, 把XML文档建模为一棵有序标签树, 树中的节点代表XML元素或者属性, 每个节点有一个id号(节点唯一的编号)、一个标签(元素或者属性), 有的节点是一个值(对应元素文本值或者属性值).

定义 1 ( XML有向树 ). 一个XML文档建模为一棵带标签的有向树 T ( V , E , r ), 其中, V 表示节点的集合, E 表示边的集合, r 是树的根节点.

定义 2 ( 关键字匹配集合KMS ). 对给定的XML有向树 T ( V , E , r )和查询关键字 k , 用 KMS ( k )表示 T 中所有与关键字 k 匹配的节点集合, KMS ( k )={ v | v ∈ V , k = tag ( v )或者 k = value ( v )}.其中, tag ( v )表示节点 v 的标签, value ( v )表示节点 v 的值.

例如 图 1 中, KMS ( A )={4, 10, 15}, KMS ( B )={6, 11, 16}, KMS ( C )={8, 12, 17}.

定义 3 ( 节点集 N 的最低公共祖先LCA ( lowest common ancestor )). 给定XML有向树 T ( V , E , r )和 m 个元素节点集 N ={ v _i | v _i ∈ V , 1≤ i ≤ m }, 节点 v = LCA ( N )当且仅当满足以下条件:

(1) 任意的 v _i ∈ N , v 是 v _i 的祖先节点, v ∈ V , 1≤ i ≤ m .

(2) 不存在节点 u (∈ V ), u 是 v 的后裔, 并且 u 是任意 v _i (∈ N )的祖先节点.

定义 4 ( LCA集合 LCASet ( T , Q )). 针对XML有向树 T ( V , E , r )的关键字查询 Q ={ k ₁ , k ₂ , …, k _m }, LCA集合 LCASet ( T , Q )={ v | v ∈ V 且 v = LCA ( k _{[1, i ]} , k _{[2, i ]} , ..., k _{[ m , i ]} )}, k _{[1, i ]} ∈ KMS ( k ₁ ), k _{[2, i ]} ∈ KMS ( k ₂ ), …, k _{[ m , i ]} ∈ KMS ( k _m ).

例如 图 1 中, 查询 Q ={ A , B , C }, LCASet ( T , Q )={1, 2, 9, 14}, 因为节点1= LCA ({4, 11, 17})(其中的一种情况), 节点2= LCA ({4, 6, 8}), 节点9= LCA ({10, 11, 12}).

3 相关定义 3.1 研究动机

图 2 表示某图书馆的藏书情况, 是一棵XML有序标签树 T , 圆角矩形中的数字表示节点的Dewey编码, 旁边是节点的标签, 叶子节点下的字符串表示值, 例如 tag (1)= booklist , tag (1.2)= book , value (1.3.1.1)= BigData System .

考虑对该树的关键字查询 Q ={BigData, Felix, James}, 检索目标是查询书名包含BigData, 作者名字中包含Felix或者James的图书.这些关键字在树中出现多次, 例如1.1.3.1.1.1、1.2.1.1、1.2.4.1.1.1、1.3.1.1和1.4.1.1这5个节点中出现关键字BigData.按照LCA的定义, 有 LCASet ( T , Q )={1, 1.1, 1.1.3, 1.2, 1.2.4.1, 1.3, 1.4}这7个节点满足查询 Q 的要求, 这些LCA中, 只有1.2、1.3、1.4和1.2.4.1满足用户查询要求; 1和1.1.3是连接节点, 因此不符合查询要求; 1.1标签包含Felix和James, 但与title对应的书是XML, 而不是BigData, 因此1.1虽然是书但也不符合用户查询意图.按照已经提出的过滤语义, 例如根据SLCA语义则不能返回1.2而是返回1.2.4.1, 按照MLCA语义则不能返回1.3, 而根据ELCA语义返回1.1.3节点也有意义, 这些过滤语义并不能准确地表达用户的查询意图.

上述查询语义失败的原因是因为那些过滤语义没有充分考虑现实应用的复杂性, 直接删除了某些LCA, 导致了低召回率和准确率.

针对已经出现的问题, 下面提出了按照查询关键字数量、关键字实例路径、LCA类型以及关键字实例离散度等综合因素对LCA进行度量的新方法, 然后按照LCA测量值的大小返回Top- K 个结果.

3.2 LCA与用户意图相关性规则

规则 1 . 用户查询意图与查询关键字实例到LCA节点边的数量成反比.

在LCA子树中, 查询关键字实例离LCA节点越近, 表示LCA越接近用户的查询意图, 查询关键字实例到LCA节点边的数量表示了它们之间的距离.

如 图 1 所示, 关键字查询 Q ={ A , B , C }, x 1和 x 2节点都是查询 Q 的LCA, 显然, 查询关键字的实例距离 x 2比 x 1更近, 因此, x 2比 x 1更符合用户的查询意图.

该规则确定了查询关键字实例与LCA之间的纵向关系.但在实际情况中, 除了纵向关系之外还存在横向关系, 即查询关键字实例在整个LCA子树中的占比情况.如 图 1 所示, x 2和 x 4都是查询 Q 的LCA, 根据规则1, 它们的度量值是相同的, 但 x 2仅仅包含了3个查询关键字实例, 而 x 4包含了 y 1和 y 2两个冗余节点, 因此, x 2比 x 4更符合用户查询需求.针对这个问题, 提出了规则2.

规则 2 . 用户查询意图与LCA子树路径的数量成反比.

规则2反映了LCA中查询关键字实例的离散度, LCA包含的子树相对于查询关键字越多, 表示查询关键字之间的离散度越大, 说明该LCA与用户查询的相关度越小.

3.3 基于关键字密度的LCA评分方法

根据规则1和规则2, 给出了计算LCA排名的有关定义, 并利用这些定义建立了计算LCA分数的公式.

定义 5 ( 最小最优LCA路径数 MOPSize ( Q )). 对于XML有向树 T ( V , E , r )的关键字查询 Q ={ k ₁ , k ₂ , …, k _m }, 与查询 Q 对应的LCA集合 LCASet ( T , Q ), 则最小最优LCA的路径数是关键字的数量, 即 MOPSize ( Q )=| Q |.

对于关键字查询 Q , LCA包含了所有查询关键字实例, 最小最优情况是LCA节点到叶子节点的每条路径上包含一个查询关键字实例.这种情况在横向轴上没有冗余信息, 也不缺少信息.如果LCA节点到叶子节点的路径数多于关键字数量, 则说明LCA有多余信息, 这种多余信息可能会对用户产生干扰.例如 图 2 中, 节点1.4是关键字查询 Q ={BigData, Felix, James}的LCA, MOPSize ( T , Q )=3, 因为3个叶子节点到LCA的路径刚好包含了3个查询关键字; 虽然节点1.3也是查询 Q 的LCA, 但它的子树有5条叶子到LCA的路径, 说明包含了冗余信息.

定义 6 ( 关键字与LCA的联系度 CSize ( T , Q , u , v )). 对于XML有向树 T ( V , E , r )的关键字查询 Q ={ k ₁ , k ₂ , …, k _m }, u ( LCASet ( T , Q ), v ∈ KMS ( k _i )(1≤ i ≤ m ), 存在一条从 u 到 v 的路径 p ( u , t ₁ , t ₂ , …, t _n , v ), CSize ( T , Q , u , v )=路径 p 的长度.

定义6表明了LCA与查询 Q 的关键字实例之间纵向紧密度, CSize 越小, 表明关键字与LCA越密切.如 图 2 所示, 1.1.3和1.3都是关键字查询 Q ={BigData, Felix, James}的LCA, CSize ( T , Q , 1.1.3, Felix)=4, 表明在1.1.3中, 关键字Felix与该LCA的距离是4, 而 CSize ( T , Q , 1.3, Felix)=3, 表明在1.3中, 关键字Felix与该LCA的距离是3, 说明后者比前者更接近用户需求.

为了对规则1进行计算, 提出了LCA边密度的概念, 它表示LCA子树中查询关键字实例到LCA边的数目与查询关键字之间的关系.

定义 7 ( 边密度 LCAEDen ( T , Q , v )). 对于XML有向树 T ( V , E , r )的关键字查询 Q ={ k ₁ , k ₂ , …, k _m }, 某个LCA关键字的边密度为

$LCAEDen{\text{(}}T, Q, v{\text{)}} = {\text{Min}}\left\{ {\sum\nolimits_{i = 1}^m {CSize(T, Q, v, {k_i})} /MOPSize(T, Q)} \right\}$

v ∈ LCASet ( T , Q ), k _i ∈ Q 且是 v 的后裔, 1≤ i ≤ m .

边密度 LCAEDen ( T , Q , v )表示查询关键字实例与LCA的纵向联系紧密度.该值越小, 说明查询关键字实例与LCA联系得越密切, 当然, 查询结果就越好.如 图 2 所示, 节点1.4是 Q ={BigData, Felix, James}的LCA, 它的边密度 LCAEDen ( T , Q , 1.4)=8/3;节点1.1.3也是 Q 的LCA, 它的边密度是 LCAEDen ( T , Q , 1.1.3)=11/3, 因此1.4比1.1.3更符合用户查询意图.但是1.3和1.4都是 Q 的LCA, 它们的边密度 LCAEDen ( T , Q , 1.4)= LCAEDen ( T , Q , 1.3)=8/3, 但是显然, 1.3比1.4包含了更多的冗余信息, 因此1.3没有1.4好.

针对边密度相同而LCA存在冗余信息的情况, 根据规则2, 提出了路径密度这一概念.它表示LCA子树中查询关键字实例在整个LCA路径中的关系, 即查询关键字的横向关系.

定义 8 ( LCA的实际路径数量 RPSize ( T , Q , u )). 对于XML有向树 T ( V , E , r )的关键字查询 Q ={ k ₁ , k ₂ , …, k _m }, u ∈ LCASet ( T , Q ), RPSize ( T , Q , u )=等于 u 的叶子节点数量.

定义8表明了对于关键字查询 Q , 从LCA到叶子节点的路径数量.如 图 2 所示, 节点1.4是关键字查询 Q = {BigData, Felix, James}的一个LCA, RPSize ( T , Q , 1.4)=3, 说明该LCA无冗余信息, 而 RPSize ( T , Q , 1.3)=5, 说明节点1.3存在冗余信息.

定义 9 ( 路径密度 LCAPDen ( T , Q , v )). 对于XML有向树 T ( V , E , r )的关键字查询 Q ={ k ₁ , k ₂ , …, k _m }, 某个LCA节点的路径密度 LCAPDen ( T , Q , v )= RPSize ( T , Q , v )/ MOPSize ( Q ), 其中, v ∈ LCASet ( T , Q ).

路径密度 LCAPDen ( T , Q , v )表示了在整个LCA子树中, 查询关键字实例路径存在的稀疏度.该值越大, 表示越稀疏, 说明该LCA中的冗余信息越多, 可能更不符合用户的查询意图.如 图 2 所示, 节点1.4是 Q ={BigData, Felix, James}的LCA, 它的路径密度 LCAPDen ( T , Q , 1.4)=3/3;节点1.3也是 Q 的LCA, 它的路径密度 LCAPDen ( T , Q , 1.3)= 5/3, 因此1.4比1.3更符合用户查询意图.

定义7和定义9分别从纵向和横向的角度来考虑LCA与用户查询意图的相关度.但存在另一种情况, 如果两个不同LCA的边密度和路径密度都相同, 我们如何区别它们?XML文档节点分为连接节点、实体节点、属性节点和值节点 ^{[ 32 ]} .不同节点的含义不同, 连接节点表示不同实体之间或者实体与属性之间的连接关系, 相当于关系数据系统中的连接表, 实体节点表示现实世界的对象, 相当于关系数据库系统中的实体关系, 属性节点相当于关系数据库系统表中的属性, 值相当于属性的记录值.在实际查询中, 用户往往对实体比较感兴趣, 因此在LCA排名中, 实体节点比连接节点、属性节点和值节点更重要.

LCA节点与用户查询意图的契合度是综合性的因素, 定义7和定义9考虑了LCA节点与查询关键字的纵向和横向关系, 定义10建立了综合考虑各种情况下的LCA评分公式.

定义 10 ( LCAValue ( T , Q , v )). 对于XML有向树 T ( V , E , r )的关键字查询 Q ={ k ₁ , k ₂ , …, k _m }, v ∈ LCASet ( T , Q ), LCA的分值为

其中, | LCA |表示LCA的孩子节点个数, t 表示与根节点类型相同的节点个数.

在如 图 2 所示的XML文档中, 对于查询 Q ={BigData, Felix, James}, 计算每个LCA所得分数见 表 1 .

1.1.3(1.1.3.1.1.11.1.3.2.2.1.1, 1.1.3.1.2.1.1) 1.2(存在多种组合, 其中一种:1.2.1.1, 1.2.2.1.1, 1.2.3.2.1) 1.2.4.1(1.2.4.1.1.11.2.4.1.2.1.1, 1.2.4.1.2.2.1) 1.3(1.3.1.1, 1.3.2.1.1, 1.3.3.2.1) 1.4(1.4.1, .4.2.1.1, 1.4.2.2.1) 1(存在多种组合, 其中一种情况:1.3.1.1, 1.2.2.1.1, 1.1.2.1.1) 1(存在多种组合, 另一种情况:.1.3.1.1.1, 1.2.2.1.1, 1.3.3.1.1)

表 1 中, 查询 Q 有3个查询关键字, 因此节点1.1.3的 MOPSize 为3, 以1.1.3为根的实际路径数(叶子节点数)为6, 关键字BigData、Felix和James与LCA节点1.1.3的联系度分别为 CSize ( T , Q , 1.1.3, BigData(1.1.3.1.1.1))=3、 CSize ( T , Q , 1.1.3, Felix(1.1.3.2.2.1.1))=4、 CSize ( T , Q , 1.1.3, James(1.1.3.1.2.1.1))=4, γ =0.94, 利用公式(2)计算出 LCAValue ( T , Q , 1.1.3)=6.61;同理, 节点1.2也是LCA节点, 关键字与1.2的联系度之和为8, 叶子节点数是8, 利用公式(2)计算出 LCAValue ( T , Q , 1.2)=6.10;同理, LCAValue ( T , Q , 1.4)=4.42;对于节点1, 存在多种组合情况, 表 1 列出其中的两种, 第1种对应的节点为1.3.1.1(Bigdata), 1.2.2.1.1(James), 1.1.2.1.1(Felix), 它们的 LCAValue ( T , Q , 1)= 14.96, 而另一种组合的节点为1.1.3.1.1.1(Bigdata), 1.2.2.1.1(James), 1.3.3.1.1(Felix), 它们的 LCAValue ( T , Q , 1)= 13.62.

表 1 最后一行显示, 最符合用户查询意图的节点1.4和1.2.4.1的 LCAValue 值最小, 节点1.3次之, 值较大的节点1表明该节点最不符合用户查询意图.因此, 可以按照 LCAValue 值从小到大排名, 把最符合用户查询意图的LCA节点优先返回给用户.

4 主要算法 4.1 计算LCA分值的算法TopLCA- K

为XML文档树中的每个节点赋予一个体现结构关系的Dewey编码, 通过该编码仅计算公共前缀即可求出任意两个节点的LCA.如 图 2 所示, 节点1.1.2.1.1和节点1.1.3.2.2.2.1, 它们的公共前缀是1.1, 因此, 节点1.1是这两个节点的LCA.

为了提高计算 LCAValue 的效率, 对于XML文档树 T ( V , E , r )的关键字查询 Q ={ k ₁ , k ₂ , …, k _m }, 为每个查询关键字建立倒排索引, 并根据它们的Dewey编码从小到大排序, 按照匹配集合中实例节点个数从小到大的顺序对每个查询关键字进行排序. 表 2 对查询 Q ={BigData, Felix, James}建立了倒排索引表, BigData关键字实例有5个节点, Felix关键字实例有7个节点, James关键字实例有6个节点, 按照关键字实例个数从小到大排序, 并且每个查询关键字的Dewey编码也根据从小到大的顺序排序.此外, 还需要为每个非叶子节点建立该子树包含叶子节点数的索引表, 见 表 3 , 为1, 1.1, 1.1.1, 1.1.2和1.1.3建立非叶子节点索引表.

基于倒排表算法计算 LCAValue 值的基本思想是利用贪心算法计算所有查询关键字对应节点的各种组合, 利用公式(2)计算该组合的LCA值并进行排名, 输出TopLCA- K 的查询结果给用户.假设有 t 个查询关键字, 则该算法时间复杂度为 O ( n ^t ), 当查询关键字多并且XML文档规模很大时, 该算法效率很低.

4.2 改进的TopLCA- K 算法

为了提高TopLCA- K 算法效率以适应大规模XML文档的环境, 对TopLCA- K 算法进行改进.

定义 11 ( 节点集 V ’的中间路径 MidP ( T , V ’ , u )). XML有向树 T ( V , E , r ), 节点集 V ʹ⊆ V , 节点 u 到根节点 r 构成的路径 p ( u , p ₁ , p ₂ , …, p _n , r )把节点集 V ʹ分为左右两部分子集 V ʹ _l 和 V ʹ _r , V ʹ _l ∩ V ʹ _r =Ø, V ʹ _l ∪ V ʹ _r = V ʹ, MidP ( T , V ʹ , u ) = p ( u , p ₁ , p ₂ , …, p _n , r ).

定义 12 ( 节点集 V ’中离节点 u 最近节点 Nearest ( T , V ʹ, u )). XML有向树 T ( V , E , r ), 节点集 V ʹ∈ V , 节点 u ∈ V 但 u ∉ V ʹ. V ʹ中离 u 最近的节点为 Nearest ( T , V ʹ, u ), 计算 Nearest ( T , V ʹ, u )的过程如下.

(1) 中间路径 MidP ( T , V ʹ, u )把 V ʹ分为 V ʹ _l 和 V ʹ _r , V ʹ _l ∩ V ʹ _r =Ø, V ʹ _l ∪ V ʹ _r = V ʹ;

(2) V ʹ _l 中最大Dewey编码节点为 v _l _ _max , V ʹ _r 中最小Dewey编码节点为 v _r _ _min ;

(3) LCA ( u , v _l _ _max )= x , LCA ( u , v _r _ _min )= y ;

(4) 如果 x 是 y 的祖先, 则 v _r _ _min 为基于 u 的 V ʹ的中心节点, 即 Nearest ( T , V ʹ, u )= v _r _ _min ; 如果 y 是 x 的祖先, 则 v _l _ _max 为基于 u 的 V ʹ的中心节点, 即 Nearest ( T , V ʹ, u )= v _l _ _max ;

(5) 如果 x 和 y 是同一个节点, 则 v _l _ _max 为基于 u 的 V ’的中心节点, 即 Nearest ( T , V ʹ, u )= v _l _ _max .

图 1 中, 设 V ={3, 4, 5, 7, 10, 11, 13, 15, 16}, 中间路径 p (12, 9, 1)把 V 分为 V _l ={3, 4, 5, 7, 10, 11}, V _l 中最大编码为11, V _r ={13, 15, 16}, V _r 中最小编码为13, LCA (11, 12, )=9, LCA (12, 13)=1, 根据定义12(4), 则有 Nearest ( T , V , 12)=11.

定义 13 ( 中心节点 CenterNode ( T , V , u )). XML有向树 T ( V , E , r ), 为 T 的每个节点根据深度优先赋予一个Dewey编码, 节点集 V ʹ={ v ₁ , v ₂ , …, v _m }( v _i ∈ V ), V ʹ的 m 个节点按照Dewey编码从小到大排序后, 节点 u ∈ V 但 u ∉ V ʹ, 则 CenterNode ( T , V ʹ, u )= Nearest ( T , V ʹ, u ).

性质 1 . XML有向树 T ( V , E , r )的 m 个节点 u ₁ , u ₂ , …, u _m , x = LCA ( u ₁ , u ₂ , …, u _m ); T 中的 m +1个节点 u ₁ , u ₂ , …, u _m , u ʹ, LCA ( u ₁ , u ₂ , …, u _m , u ʹ)= y , 如果 u ʹ是 x 的后裔, 则 y 是 x 本身, 否则 y 是 x 的祖先.

性质 2 . XML有向树 T ( V , E , r )的节点 x 和 y , 如果 y 是 x 的祖先, 则 y 子树的叶子节点数大于等于 x 子树的叶子节点数, 即 leafNum ( T , y )≥ leafNum ( T , x ).

性质 3 . XML有向树 T ( V , E , r ), 节点集 V ʹ的 m 个节点按照Dewey编码从小到大排序, V ʹ={ v ₁ , v ₂ , …, v _m } ( v _i ∈ V , 1≤ i ≤ m ), u ∈ V 但 u ∉ V ʹ. CenterNode ( T , V ʹ, u )= v _j ( v _j ∈ V ʹ), 则 leafNum ( T , LCA ( u , v _j ))≤ leafNum ( T , LCA ( u , v _j ʹ))( v _j≠ v _j ʹ, v _j ʹ∈ V ʹ).

证明:因为 v _j = CenterNode ( T , V ʹ, u ), 根据定义12和定义13, 则 v _j ʹ≠ v _j , LCA ( u , v _j ʹ)= LCA ( u , v _j )或者 LCA ( u , v _j ʹ)是 LCA ( u , v _j )的祖先.根据性质2, leafNum ( T , LCA ( u , v _j ʹ))≥ leafNum ( T , LCA ( u , v _j )).

图 2 中, 按照Dewey编码从小到大排序后, V ʹ={1.1.2.1.1, 1.1.2.2.1, 1.1.3.1.1.1, 1.1.3.1.2.1.1, 1.1.3.2.1.1, 1.1.3.2.2.1, 1.1.3.2.2.1.1, 1.1.3.2.2.2.1}, 对于节点Bob(1.1.3.1.1.2.1), V ʹ的中心点 CenterNode ( T , V ʹ, 1.1.3.1.1.2.1)= 1.1.3.1.2.1.1, 根据性质3, leafNum ( T , LCA (1.1.3.1.1.2.1, 1.1.3.1.2.1.1))≤ leafNum ( T , LCA (1.1.3.1.1.2.1, v ))( v∈V ʹ且 v≠ 1.1.3.1.2.1.1).例如, leafNum ( T , LCA (1.1.3.1.1.2.1, 1.1.3.1.2.1.1))(=2)≤ leafNum ( T , LCA (1.1.3.1.1.2.1, 1.1.3.2.2.1.1)) (=6).同理, leafNum ( T , LCA (1.1.3.1.1.2.1, 1.1.3.1.2.1.1))(=2)≤ leafNum ( T , LCA (1.1.3.1.1.2.1, 1.1.3.1.1.1))(=3).

在TopLCA- K 算法中, 如何确定 K 是一个重要问题.如对于 图 2 中的 Q ={BigData, Felix, James}, KMS (BigData) ={1.1.3.1.1.1, 1.2.1.1, 1.2.4.1.1.1, 1.3.1.1, 1.4.1.1}共有5个节点; KMS (Felix)={1.1.2.1.1, 1.1.3.1.1.1.1, 1.2.3.2.1, 1.2.4.1.2.1.1, 1.3.2.1.1, 1.3.3.1.1, 1.4.2.1.1}共有7个节点; KMS (James)={1.1.2.2.1, 1.1.3.2.2.1.1, 1.2.2.1.1, 1.2.4.1.2.2.1, 1.3.3.2.1, 1.4.2.2.1}, 共有6个节点.按照LCA的概念共有5×7×6=210种组合情况, 但是满足用户查询意图的LCA比这个数值要小得多.实际上, 真正满足用户意图的LCA的个数由min{| KMS (BigData)|, | KMS (Felix)|, | KMS (James)|}的值确定, 即具有最少关键字实例的个数就是用户需要寻找的LCA个数.

规则 3 . 对于XML有向树 T ( V , E , r )的关键字查询 Q ={ k ₁ , k ₂ , …, k _m }, 满足用户查询意图的LCA个数, 即 LCANum ( T , Q )≤min{| KMS ( k ₁ )|, | KMS ( k ₂ )|, …, | KMS ( k _m )|}, k _i ∈ Q , 1≤ i ≤ m .

证明:设 k _i 的| KMS ( k _i )|具有最小值 t , 则当 k _j ∈{ k ₁ , k ₂ , …, k _{i -1} , k _{i +1} , …, k _m }时, | KMS ( k _j )|≥ t .对于 KMS ( k _i )中的任意查询实例节点 u ∈ KMS ( k _i ), LCAValue ( T , Q , v )的最小值为 α , v 为包含了 u 的一个LCA, 该LCA是满足用户查询意图的LCA.由于| KMS ( k _i )|的值为 t , 因此这样的LCA不多于 t 个, 即 LCANum ( T , Q )≤min{| KMS ( k ₁ )|, | KMS ( k ₂ )|, …, | KMS ( k _m )|}.

备注:如果多个 LVAValue ( T , Q , v )的值相同, 则看作是同一个LCA.

利用规则3能够解决过滤语义, 如SLCA、MLCA和ELCA等查不全的问题.例如, 针对 图 2 中的查询 Q ={BigData, Felix, James}, 按照SLCA语义, 不能返回1.2节点, 但是根据规则3, 能够把节点1.2作为满足查询意图的一个节点返回给用户.

规则3确定了TopLCA- K 算法中 K 的值, 利用定义13确定搜索倒排表的起始位置, 利用性质3能够对搜索的倒排表进行剪枝, 从而提高算法效率.

改进后的TopLCA- K 算法的思想是:首先建立每个查询关键字的倒排表, 对查询关键字实例的个数从小到大排序, 并把每个倒排表中的Dewey编码按照从小到大的顺序排序, 逐层建立中心位置索引, 根据中心位置索引逐层寻找LCA并进行评分, 一直完成最少个数的查询关键字实例的搜索.

建立中心位置索引CI(center index)的方法是:对于XML有向树 T ( V , E , r )的关键字查询 Q ={ k ₁ , k ₂ , …, k _m }, 查询关键字 k ₁ 的实例 KMS ( k ₁ )={ a _{[1, 1]} , a _[1,2] , …, a _{[1, t 1]} }, 查询关键字 k ₂ 的实例 KMS ( k ₂ )={ a _{[2, 1]} , a _{[2, 2]} , …, a _{[1, t 2]} }, 查询关键字 k _m 的实例 KMS ( k _m )={ a _{[ m , 1]} , a _{[ m , 2]} , …, a _{[ m , tm ]} }.每个查询关键字实例按照Dewey编码从小到大排序, 即 a _{[ j , 1]} ≤ a _{[ j , 2 ]} ≤…≤ a _{[ j , tj ]} (1≤ j ≤ m ), 且 t ₁ ≤ t ₂ ≤…≤ t _m .构建如下的中心位置索引如 图 3 所示.第1层存储了 k ₁ 实例, 第2层存储了 CenterNode ( T , KMS ( k ₂ ), a _{[1, j ]} )节点, 第3层到第 m 层存储了 CenterNode ( T , KMS ( k _i ), CenterNode ( T , KMS ( k _{i- 1} ), a _{[ i– 1, j ]} ))节点.

推论 1 . XML有向树 T ( V , E , r )的关键字查询 Q ={ k ₁ , k ₂ , …, k _m }, 对应的中心位置索引CI, 第 i 层的中心位置 a _{[ i , ci ]} , LCA ( a _{[1, c 1]} , a _{[2, c 2]} , …, a _{[ m , cm ]} )= C , a _{[1, c 1]} , a _{[2, c 2]} , …, a _{[ m , cm ]} 是CI树中一条从叶子节点到第1层的路径; LCA ( a _{[1, x 1]} , a _{[2, x 2]} , …, a _{[ i , ci + k ]} )= R ( c _i + k ≤ t _i , t _i 是第 i 层的关键字实例个数), LCA ( a _{[1, x 1]} , a _{[2, x 2]} , …, a _{[ i , ci – j ]} )= L ( c _i – j ≥0), 则如下公式成立:

(1) 如果 leafNum ( R )+ $\sum\nolimits_{j = 1}^{{c_i} + k} {CSize(T, Q, R, a[j, {x_j}]} ) \geqslant leafNum(C) + \sum\nolimits_{t = 1}^i {CSize(T, Q, a[t, {x_t}])} , $ 则 LCAValue ( T , Q , LCA ( R , a _{[ i , xi + k + 1]} ))≥ LCAValue ( T , Q , LCA ( C ));

(2) 如果 $leafNum(L) + \sum\nolimits_{j = 1}^{{c_i} - j} {CSize(T, Q, L, a[j, {x_j}]) \geqslant leafNum(C) + \sum\nolimits_{j = 1}^i {CSize(T, Q, L, a[j, {x_j}])} } , $ 则 LCAValue ( T , Q , LCA ( L , ${a_{[i, xi - j - 1]}}$ ))≥ LCAValue ( T , Q , LCA ( C )).

根据推论1, 可以快速寻找出最小LCA的值. 图 4 显示了 图 2 、 Q ={BigData, Felix, James}的CI.通过树的第1个分支计算出LCA为1.1.3, 该节点有6个叶子, 关键字与LCA的联系度为11, LCAValue ( T , Q , 1.1.3)= (6+11)/3=17/3;在第3层以1.1.3.1.2.1.1为出发点, 从两边搜索其他Felix节点的组合情况, 左边的Felix节点1.1.2.1.1, 则前面两个节点与1.1.2.1.1的LCA为1.1, 现在考虑只有BigData和James两个节点的情况下 LCAValue ( T , Q , 1.1)=(9+9)/3=18/3, 则 LCAValue ( T , Q , 1.1)≥18/3 > LCAValue ( T , Q , 1.1.3)(=17/3), 根据推论1, 可以不用考虑1.1.2.1.1左边的节点; 再观察右边的情况, 右边的Felix为1.2.3.2.1, 则前面两个节点与1.2.3.2.1的LCA为1, 这种情形下叶子节点有25个, LCAValue ( T , Q , 1)=(25+4)/3 > LCAValue ( T , Q , 1.1.3)(=17/3), 根据推论1, 可以不用考虑1.2.3.2.1右边的节点.因此, 利用中心位置索引可以对搜索空间进行快速剪枝, 提高了搜索效率.

针对有序XML文档树 T 的关键字查询 Q , 按照深度优先遍历 T 并为每个节点赋予Dewey编码, 然后建立每个查询关键字 k _i 对应的实例节点倒排表, 并按照Dewey编码从小到大地对该倒排表进行排序; 建立每个子树的叶子节点数列表; 建立中心位置CI.寻找最佳 K 个LCA方法, 见算法1和算法2.

//Location的数据结构

class Location{

int level; //表示IL中某个节点的层次

int colmum; //表示IL中某层次的某个列

String dewey; //表示level层colmun列的dewey编码

算法 1. getMinLcaValue(T, Q)//取得最小的LCA值.

输入:XML文档树T和查询关键字Q;

输出:K个值最小的LCA.

BEGIN

IL←getCI(T, Q); //产生倒排表, 见 表 3

ciT←getCI(IL); //根据倒排表产生中心位置索引表, 如 图 4 所示

FOR(i=0;i < ciT的列数; i++)

leftLca=getLcaValue(ciT, IL, i, left); //得到第i列左边值最小的LCA

rightLca=getLcaValue(ciT, IL, i, left); //得到第i列右边值最小的LCA

IF(leftLca > rightLca)

return rightLca;

ELSE IF(leftLca < rightLca)

RETURN leftLca;

RETURN leftLca∪rightLca;

ENDIF

ENDFOR

算法 2 . getLcaValue(ciT, IL, col, direction); //根据倒排表IL和CI计算第col个的LCA值.

输入:中心位置索引树ciT, 关键字倒排表IL, ciT的列col, 搜索ciT的方向direction;

输出:LCA节点和值.

BEGIN

curMinLca←getCIValue (ciT, col); //取得CI路径上的LCA值

WHILE(!isEmpty(stkLocation)) //保存Location信息的栈stkLocation不为空

IF(如果stkLocation栈顶的level到达最高层)

FOR(根据direction方向遍历最高层的所有元素)

curLCA←getStkValue(stkLocation); //计算栈中LCA的值

IF(curLca < curMinLca) //当前LCA值< 当前最小LCA值

curMinLca=curLca;

ENDIF

IF(curLca满足推论1) //满足推论1, 不用计算之后的LCA

break;

ENDIF

ENDFOR

pop(stkLocation);

ELSE IF(如果stkLocation栈顶没有到达最高层)

curLocation←getTop(stkLoccation); //获得栈顶的层数及位置信息;

WHILE(curLocation位置信息不是该层的边界)

pop(stkLocation);

curLocation←getTop(stkLoccation); //获得栈顶的层数及位置信息;

ENDWHILE

stkLocation栈顶位置信息location+1;

根据level和location修改stkLocation栈顶的Dewey信息;

stkLoc的栈顶位置信息+1, stkElem对应的值入栈

WHILE(stkLocation栈顶的层次数 < 最大层次数时)

下一层的层次数入栈, 位置信息0入栈stkLoc;

对应的集合的0号元素入栈stkElem

ENDWHILE

ENDIF

ENDWHILE

5 实验分析

我们设计了一套全面的实验来评估本文提出的TopLCA- K 算法的性能, 采用真实数据集SIGMODRECORD、Mondial和DBLP作为测试数据, 比较了与XReal、XReason和SLCA等算法在查全率、查准率和时间性能等方面的效果.所有实验在CPU为Intel双核3.6GHz, RAM为4GB, 操作系统为Windows 7的机器上运行, 实现语言为Java SE, 通过使用dom4j-1.6.1.jar来解析XML文档.

5.1 数据集与查询测试

我们选取了来自于现实情况的SIGMODRECORD、Mondial和DBLP作为测试数据集. 表 4 显示了这些数据集的统计信息, 它们具有不同特征, SIGMODRECORD节点数和不同标签数最小, Mondial数据集的节点数处于中间水平, 使用这两个测试数据集的主要目的是测试算法的查全率和查准率.DBLP ^① 的规模很大, 节点数超过1亿, 我们选择的测试数据仅仅是其中的一部分, 但也保持了一定的规模, 该数据集主要测试在数据规模较大情况下各算法的时间性能.本实验没有考虑数据集中ID/IDREF的关联情况.

针对每个测试数据集, 我们选取了具有不同查询意图的测试查询, 并且每个查询测试的查询意图是明确的.为每个数据集设计了7个测试查询, S1~S7、M1~M7和D1~D7分别表示针对SIGMODRECORD、Mondial和DBLP数据集的测试查询.具体见 表 5 .

5.2 查询质量

把本文提出的TopLCA- K 算法与已有XReason、Xreal和SLCA等方法在查准率和查全率进行对比来比较它们的查询质量.

图 5 显示了本文提出的TopLCA- K 与其他方法在查询准确率方面的比较情况.

图 5 显示, 在查准率方面, 一般情况下, TopLCA- K 要高于其他3种方法, 因为该算法考虑了LCA中横向关键字密度和纵向关键字密度两方面的情况, 因此排在前面的更符合用户查询意图.但在某些查询情况下, 准确率也不能达到100%, 主要是因为查询关键字存在一些歧义, 例如关于DBLP数据集的D4查询, 查询意图是查询688页, 2011年出版的标题中含有Security的论文、书籍或者会议出版的文章, 但是由于688不仅仅出现在page中, 而且在节点ee中也出现了该关键字.同理, 2011不仅仅出现在year节点中, 而且在incollection的url中也出现了2011.

图 6 显示了召回率的比较情况.

很明显, TopLCA- K 的召回率为100%, 不存在漏检问题, 其他方法都不能达到100%, XReal采用扩展网页排名方法进行排名, 在关键字歧义情况下, 很容易漏检; SLCA由于去掉了父LCA, 显然会丢失一些符合要求的结果; 而TopLCA- K 返回了所有的LCA, 包括有歧义的LCA, 然后从深度和广度计算LCA的值, 把排名小的优先返回, 当K值合理时, 将返回所有可能满足查询意图的LCA.

5.3 查询性能

图 7 显示了3个数据集上算法运行时间情况, 为了准确记录查询时间, 每个关键字查询执行5次, 取它们的平均值作为查询时间, 根据规则3设置了TopLCA- K 中 K 的值.从 图 7 可以发现, TopLCA- K 的算法时间性能明显优于XReason和XReal, 与SLCA比较接近.因为TopLCA- K 算法利用CI能够对查询空间树进行有效剪枝, 例如在D6中, 共有8 849个节点包含关键字2014, 其中year节点值有4 051个, 其他节点, 如ee包含的2014有520个.这种情况对XReason产生有效结构模式形成了很大干扰, 这种情况也对采用TF*IDF排名的XReal方法形成了很多干扰信息.

6 结束语

本文首先介绍了LCA过滤语义和结果排名方法, 指出了在XML关键字查询中LCA过滤语义存在漏报问题, 提出了用户查询意图与查询关键字在纵向和横向方面的两个规则, 建立了利用边密度和路径密度对LCA节点进行评分的公式, 采取中位节点索引CI来提高TopLCA- K 算法效率.实验结果表明, 本文提出的对LCA进行评分排名的方法在查准率和召回率方面效果较好, 并且查询时间性能也较好, 但需要进一步优化提高.下一步的研究重点考虑当在LCA之间存在包含、重复和交叉关系情况时, 如何对LCA进行排序以及结果展示的问题, 同时进一步优化算法.在未来的工作中, 将研究如何减少编码长度以及基于新编码方案的XML关键字查询处理.

Guo L, Shao F, Botev C, Shanmugasundaram J. XRANK: Ranked keyword search over XML documents. In: Proc. of the SIGMOD Conf. 2003. 16-27. https://www.researchgate.net/publication/2907277_XRANK_ranked_keyword_search_over_XML_documents?_sg=J2GM5inWioCCbtMt8W2arKNO4-luutFURdEfjEsohhVfL_QFaDXBAKlH86iYxeouBVYQYNUeaNs1m8kAcZ27Ug Schmidt A, Kersten M, Windhouwer M. Querying XML documents made easy: Nearest concept queries. In: Proc. of the Int'l Conf. on Data Engineering. IEEE, 2001. 321-329. https://www.researchgate.net/publication/3892969_Querying_XML_documents_made_easy_Nearest_concept_queries Zhang CJ, Wang XL, Zhou AY. XML filtering based-on probabilistic SLCA. Chinese Journal of Computers, 2014(9): 1959-1971(in Chinese with English abstract). http://d.old.wanfangdata.com.cn/Periodical/jsjxb201409006 Bao Z, Ling TW, Chen B, et al. Effective XML keyword search with relevance oriented ranking. In: Proc. of the IEEE Int'l Conf. on Data Engineering. IEEE, 2009. 517-528. https://www.researchgate.net/publication/220965634_Effective_XML_Keyword_Search_with_Relevance_Oriented_Ranking Bao Z, Lu J, Ling TW, et al . Towards an effective XML keyword search. IEEE Trans. on Knowledge & Data Engineering, 2010, 22(8): 1077-1092. http://d.old.wanfangdata.com.cn/Periodical/jsjkxjsxb-e201201016 Chen LJ, Papakonstantinou Y. Supporting top-K keyword search in XML databases. In: Proc. of the IEEE Int'l Conf. on Data Engineering. IEEE, 2010. 689-700. https://www.researchgate.net/publication/220967677_Supporting_Top-K_Keyword_Search_in_XML_Databases Liu Z, Chen Y. Processing keyword search on XML:A survey. World Wide Web-Internet & Web Information Systems, 2011, 14(5-6): 671-707. http://cn.bing.com/academic/profile?id=4e1dfc222fd77963196a2371b589c7b8&encoded=0&v=paper_preview&mkt=zh-cn Liu X, Wan C, Chen L. Returning clustered results for keyword search on XML documents. IEEE Trans. on Knowledge & Data Engineering, 2011, 23(12): 1811-1825. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=4f7f9ff80e8a0e44402d10c5d44b9567 Cohen S, Mamou J, Kanza Y, Sagiv Y. XSEarch:A semantic search engine for XML. VLDB Journal, 2003, 45-56. http://d.old.wanfangdata.com.cn/NSTLHY/NSTL_HYCC0210759439/ Li Y, Yu C, Jagadish HV. Schema-free XQuery. VLDB Journal, 2004, 72-83. http://d.old.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ0219568412/ Xu Y, Papakonstantinou Y. Efficient keyword search for smallest LCAs in XML databases. In: Proc. of the ACM SIGMOD Int'l Conf. on Management of Data. Baltimore: DBLP, 2005. 527-538. https://www.researchgate.net/publication/221214405_Efficient_Keyword_Search_for_Smallest_LCAs_in_XML_Databases Li G, Feng J, Wang J, et al. Effective keyword search for valuable lcas over XML documents. In: Proc. of the 16th ACM Conf. on Information and Knowledge Management. ACM, 2007. 31-40. https://www.researchgate.net/publication/221615543_Effective_keyword_search_for_valuable_LCAs_over_XML_document_in_CIKM Chen ZY, Wang X, Tang X. Efficiently computing RKN for keyword queries on XML data. Journal on Communications, 2014, 35(7): 46-55(in Chinese with English abstract). [ doi:10.3969/j.issn.1000-436x.2014.07.006 ] Termehchy A, Winslett M. Using structural information in XML keyword search effectively. ACM Trans. on Database Systems, 2011, 36(1): 1-39. http://cn.bing.com/academic/profile?id=d2d2dd1e4fbbdee8a391236e58e690cd&encoded=0&v=paper_preview&mkt=zh-cn Li G, Li C, Feng J, et al . SAIL:Structure-aware indexing for effective and progressive top-k, keyword search over XML documents. Information Sciences, 2009, 179(21): 3745-3762. [ doi:10.1016/j.ins.2009.06.025 ] Li J, Liu C, Zhou R, et al. Top-k keyword search over probabilistic XML data. In: Proc. of the IEEE Int'l Conf. on Data Engineering. IEEE, 2011. 673-684. https://www.researchgate.net/publication/224237550_Top-k_Keyword_Search_over_Probabilistic_XML_Data Amer-Yahia S, Lalmas M. XML search:Languages, INEX and scoring. ACM SIGMOD Record, 2006, 35(4): 16-23. [ doi:10.1145/1228268 ] Hristidis V, Papakonstantinou Y, Balmin A. Keyword proximity search on XML graphs. In: Proc. of the Int'l Conf. on Data Engineering. IEEE, 2003. 367-378. https://www.researchgate.net/publication/4053392_Keyword_proximity_search_on_XML_graphs Zhou J, Bao Z, Ling TW, et al . MCN:A new semantics towards effective XML keyword search. Lecture Notes in Computer Science, 2009, 5463: 511-526. [ doi:10.1007/978-3-642-00887-0 ] Zhou R, Liu C, Li J. Fast ELCA computation for keyword queries on XML data. In: Proc. of the Int'l Conf. on Extending Database Technology. ACM, 2010. 549-560. Zhou J, Wang W, Chen Z, et al . Top-down XML keyword query processing. IEEE Trans. on Knowledge & Data Engineering, 2016, 28(5): 1340-1353. http://d.old.wanfangdata.com.cn/NSTLHY/NSTL_HYCC0213257696/ Dimitriou A, Theodoratos D, Sellis T. Top- k -size keyword search on tree structured data. Information Systems, 2014(47): 178-193. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=23aa86b10d3d43f202c1ac7fb5c4de2e Hristidis V, Papakonstantinou Y. DISCOVER:Keyword search in relational databases. VLDB Journal, 2002, 26(2): 670-681. http://d.old.wanfangdata.com.cn/Periodical/zhgkzz98201512001 Li QS, Wang QY, Wang S. Query understanding for XML keyword search. Ruan Jian Xue Bao/Journal of Software, 2012, 23(8): 2002-2017(in Chinese with English abstract). http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?flag=1&file_no=4122&journal_id=jos [ doi:10.3724/SP.J.1001.2012.04122 ] He H, Wang H, Yang J, et al. BLINKS: Ranked keyword searches on graphs. In: Proc. of the ACM SIGMOD Int'l Conf. on Management of Data. Beijing: ACM, 2007. 305-316. https://www.researchgate.net/publication/221214090_BLINKS_ranked_keyword_searches_on_graphs Aksoy C, Dimitriou A, Theodoratos D, et al. XReason: A semantic approach that reasons with patterns to answer XML keyword queries. In: Database Systems for Advanced Applications. Berlin, Heidelberg: Springer-Verlag, 2013. 299-314. https://link.springer.com/chapter/10.1007%2F978-3-642-37487-6_24 Aksoy C, Dimitriou A, Theodoratos D. Reasoning with patterns to effectively answer XML keyword queries. VLDB Journal, 2015, 24(3): 441-465. [ doi:10.1007/s00778-015-0384-3 ] Li J, Liu C, Zhou R, et al. Suggestion of promising result types for XML keyword search. In: Proc. of the Int'l Conf. on Extending Database Technology. ACM, 2010. 561-572. https://www.researchgate.net/publication/221103747_Suggestion_of_promising_result_types_for_XML_keyword_search Zhou J, Bao Z, Wang W, et al . Efficient query processing for XML keyword queries based on the IDList index. VLDB Journal, 2014, 23(1): 25-50. [ doi:10.1007/s00778-013-0313-2 ] Liu X, Wan C, Liu D. Keyword query with structure:towards semantic scoring of XML search results. Information Technology & Management, 2016, 17(2): 151-163. http://cn.bing.com/academic/profile?id=9b9161058f799579c182736da0ee14e1&encoded=0&v=paper_preview&mkt=zh-cn Nguyen K, Cao J. Top-k, answers for XML keyword queries. World Wide Web-Internet & Web Information Systems, 2012, 15(5-6): 485-515. http://cn.bing.com/academic/profile?id=9f796dc01b71dd1ba9bcad2b29dc3fea&encoded=0&v=paper_preview&mkt=zh-cn Liu Z, Chen Y. Identifying meaningful return information for XML keyword search. In: Proc. of the ACM SIGMOD Int'l Conf. on Management of Data. ACM, 2007. 329-340. https://www.researchgate.net/publication/221214917_Identifying_meaningful_return_information_for_XML_keyword_search 张晨静, 王晓玲, 周傲英. 基于概率SLCA的XML过滤. 计算机学报, 2014(9): 1959-1971. http://d.old.wanfangdata.com.cn/Periodical/jsjxb201409006 陈子阳, 王璿, 汤显. 面向XML关键字查询的高效RKN求解策略. 通信学报, 2014, 35(7): 46-55. [ doi:10.3969/j.issn.1000-436x.2014.07.006 ] 李求实, 王秋月, 王珊. XML关键词检索的查询理解. 软件学报, 2012, 23(8): 2002-2017. http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?flag=1&file_no=4122&journal_id=jos [ doi:10.3724/SP.J.1001.2012.04122 ]