基于智能分组策略的XML关键字查询算法

XML关键字查询作为一种信息检索方式,一直是相关领域的热点研究问题。在经典查询语义SLCA的基础上,设计并实现了一种基于智能分组策略的XML关键字查询的优化算法。提出的算法通过合理的分组策略可以保证在运算过程中及时 去除组内祖先节点和重复节点,减少了大量冗余计算,提高了算法的效率。最后设计多组实验在不同的XML数据上进行测试,实验结果表明了该算法的有效性和高效性。     

XML关键字查询处理研究

关键字查询作为一种有效的信息检索手段,一直以来都是XML数据管理领域研究的热点问题,每年均有大量最新研究成果出现在各种顶级会议和期刊上.针对众多国内外研究者在XML关键字查询领域所作出的创新性工作,该文以XML关键字查询处理系统为框架来组织现有工作,重点分析和比较了查询生成、语义定义、排序机制、查询算法及结果展示等5个关键技术点所涉及的代表性工作的特点,并结合最新的应用需求从有效性和高效性的角度归纳出XML关键字查询技术后续研究面临的问题和挑战.     

基于扩展查询表达式的XML关键字查询

目前可扩展标示语言(XML)关键字查询大多是基于最小公共祖先(LCA)语义子树产生查询结果,而未能加入除LCA语义子树之外与用户查询意图相关的结果。为解决该问题,提出一种基于扩展查询表达式的XML关键字查询方法。将用户查询日志作为查询扩展统计模型,对其进行统计分析,并结合最佳检索概念判断是否需要扩展查询表达式。使用XML TF-IDF方法计算候选属性的权重,根据初检结果的上下文信息,利用聚类方法获得与查询意图最相关的扩展查询关键字,从而扩展查询表达式。实验结果表明,与XSeek和基于语义词典的查询扩展方法相比,该方法的平均F度量值分别提高了7%和17%,具有较高的查询质量。     

基于关键字之间结构关系的XML查询结果排序方法

非空结果的XML关键字查询中,多个查询关键字之间必然存在联系,这种联系可以通过SLCA(最紧致片段)的结构关系获得.基于SLCA的结构关系,提出了一种推测多个关键字内在联系的XML关键字查询结果排序方法:通过LISA Ⅱ 算法获得SLCA;根据SLCA的结构信息推测出各个关键字之间的内在结构关系,得到所有关键字组成的关系树;然后根据关系树中各关键字对查询结点的严格程度得到对应SLCA的重要程度,据此得到有序的SLCA并输出.该方法利用了XML文档的结构信息对查询结果进行排序.实验结果和分析表明,提出的方法具有较高的准确率,能够较好地满足当前用户的需求和偏好.     

TDCOL:列式存储的XML关键字查询处理策略

针对已有方法在XML数据上基于SLCA(smallest lowest common ancestor)语义处理查询时存在的冗余计算问题,提出了一种基于列存储的倒排索引CList,用于避免已有方法的倒排表中相同数据重复存储的问题。基于CList,提出了一种自顶向下的查询处理算法TDCOL(top-down SLCA computation based oncol-umn storage)来提升系统的处理性能。对于给定查询Q={k1,k2,...,km}的每个公共祖先结点,TDCOL在保证仅处理一次的情况下即可得到所有满足条件的结果,因而将时间复杂度降为O(m′|LID1|′lb|Skmaxch(v)|),其中|LID1|是Q的最短倒排表中包含的不同ID值的数目,Skmaxch(v)是所有被处理结点的包含关键字的孩子结点集中的最大集合。最后通过比较各种指标,从不同角度对TDCOL算法的性能优势进行了验证。     

一种基于关键字的XML文档查询算法

对XML文档查询的常用方法有两种：一种是使用查询语言;另一种是使用关键字,而使用关键字查询XML文档比使用查询语言更为简单方便。给出了一种使用关键字查询XML文档的索引查找算法。该算法只需要扫描一次关键字对应的编码列,就可以找到需要的编码,提高了查询效率。实验表明该算法是可行的和有效的。     

利用实体语义信息的关键字查询结果多样化

近年来,可扩展标记语言（extensible markup language,XML）数据的关键字查询受到广泛关注和研究,查询结果的多样化作为提高用户查找效率的有效途径,也成为一个研究热点。已有的方法采用不同的粒度对查询结果进行多样化,但效果并不理想。为解决这个问题,提出了一种新的方法——从查询结果所描述的中心实体出发对其进行多样化。首先分析实体包含的语义信息,根据实体的特征定义实体语义相似性计算公式,然后通过衡量这些实体之间的语义相似性,对其进行语义划分,并给出查询结果所属中心实体的定位规则。基于以上工作,就可以将查询结果依据其所属中心实体的分组情况进行分类。这样得到的查询结果分组可以让用户根据每组的语义标签进行查询导航,有利于提高查找效率。实验结果证明了该方法的有效性。     

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

现有的XML关键字查询方法包括两步:确定满足特定语义的节点;构建满足特定条件的子树。这种处理方式需要多次扫描关键字倒排表,效率低下。针对这一问题,提出快速分组方法来减少扫描倒排表次数,进而基于快速分组方法提出FastMatch算法。该算法仅需扫描一次关键字倒排表就能构建满足特定条件的子树,从而提高了查询效率。最后通过实验验证了该方法的高效性。     

基于有效最低公共祖先的XML关键字查询算法

针对XML文档关键字搜索问题,从元素标签内容等价和元素结构相似性等价两个方面考虑无效的查询结果。介绍了有效最低公共祖先(FLCA)的概念,在此基础上提出紧致的有效最低公共祖先(CFLCA)的概念。根据定义的查询结果集,提出基于等价模式值索引的查询算法(BEPVA)。最后与CVLCA和SLCA进行了比较,结果表明提出的方法在查询质量和查询效率上有较大的提高。     

XML数据流上的关键字查询

XML数据流上的XPath & XQuery查询处理是目前研究者关注的热点问题,但由于XPath & XQuery查询语言相对复杂,在不知道模式信息的前提下,用户很难通过已有的查询接口得到自己感兴趣的数据片断,因此如何在数据流模型上根据XML数据的特点为用户提供最友好的查询接口就成为一个亟待解决的问题.针对这个问题,创新地提出了在XML数据流上做关键字查询的问题,给出了最小相关连通子树(SRCT)的概念用于处理返回的结果,并设计了一种新的基于栈的Lookup算法,可以有效解决在XML数据流上进行关键字查询的问题,最后通过实验从不同角度对Lookup算法的各项性能指标进行了验证.     

一种基于自然语言生成的XML关键字查询技术

为了解决基于LCA（Lower Common Ancestor）的XML关键字查询丢失语义的问题,提出了一种基于“自然语言生成技术（Natural Language Generation,NLG）”的XML关键字查询技术,将NLG的内容规划应用到XML文档,产生针对用户查询的消息语句集,通过对消息语句集的筛选既可以实现基于语义的XML关键字查询,又可以极大地提高查询效率。     

基于压缩策略的安全XML关键字查询

当含有敏感信息的XML文档在网络上传输或交换时,需要用户执行受限查询,如何提高查询效率,同时又保证敏感信息的安全一直是安全领域的研究热点。以带访问权限的实例信息树为主体,优先抽取主干信息策略,再反向作用于实例信息树存储特殊节点的压缩方法,为安全且高效的XML关键字查询奠定了基础,而且采用扩展的Dewey编码方式,为安全查询提供了方便。实验结果表明,这种基于压缩策略的安全查询方式减轻了存储负担,提高了查询效率。     

基于最小相关实体子树的XML关键字查询算法

针对目前XML关键字查询结果中包含了许多无意义的节点的问题,提出了一种语义相关的查询算法。由于XML文档具有半结构化和自描述的特点,通过充分利用节点间的语义相关性,提出了最小最低实体子树（SLEST）的概念,在这个概念中,关键字之间仅存在物理连接关系;为了捕获关键字之间的IDREF引用关系,提出基于最小相关实体子树（SIEST）的算法,并利用最小最低实体子树和最小相关实体子树代替最小最低公共祖先（SLCA）作为查询结果。实验结果表明,提出的算法能有效提高XML关键字查询结果的查准率。     

Efficient keyword search over virtual XML views

Emerging applications such as personalized portals, enterprise search, and web integration systems often require keyword search over semi-structured views. However, traditional information retrieval techniques are likely to be expensive in this context because they rely on the assumption that the set of documents being searched is materialized. In this paper, we present a system architecture and algorithm that can efficiently evaluate keyword search queries over virtual (unmaterialized) XML views. An interesting aspect of our approach is that it exploits indices present on the base data and thereby avoids materializing large parts of the view that are not relevant to the query results. Another feature of the algorithm is that by solely using indices, we can still score the results of queries over the virtual view, and the resulting scores are the same as if the view was materialized. Our performance evaluation using the INEX data set in the Quark (Bhaskar et al. in Quark: an efficient XQuery full-text implementation. In: SIGMOD, 2006) open-source XML database system indicates that the proposed approach is scalable and efficient.     

结合查询相关性的关键词查询排序方法

针对关系数据库关键词查询系统中的结果排序问题,提出了一种新的排序方法.该方法结合了查询相关性和结构权重,将单个元组看作是一个虚拟文档,通过对元组引入信息检索(information retrieval,JR)式评分方式,采用标准化词频和标准化逆文档频率说明元组与查询条件之间的相关性程度,对整个结果采用结构权重来反应结果的语义强度.相比于以往只考虑结构权重的排序方法,该方法能更有效的将与查询高度相关的结果排在前面.实验结果表明,结合查询相关性的排序方法可以有效的对结果进行排序.     

不确定性区域上的多维关键词搜索

随着在线地图应用的普及,基于地图的空间对象检索成为一个重要的工具而被广泛使用,技术也比较成熟。人们在地图上经常进行确定性目标点查询,例如用户提交关键词“咖啡店”,地图应用会在地图上标记所有的咖啡店,用户还可以通过进一步操作获取咖啡店的详细信息。但实际生活中存在另一种需求,例如用户想找到一个区域,在这个区域内要有“咖啡店”、“学校”和“旅店”这三类对象,称这样的查询为不确定性区域检索查询。目前对地图应用的研究无法解决不确定性区域检索的问题。而利用矩形剪枝和top-k推荐能够通过用户提交的关键字,给用户返回若干候选区域。     

SAIL: Structure-aware indexing for effective and progressive top-k keyword search over XML documents

Keyword search in XML documents has recently gained a lot of research attention. Given a keyword query, existing approaches first compute the lowest common ancestors (LCAs) or their variants of XML elements that contain the input keywords, and then identify the subtrees rooted at the LCAs as the answer. In this the paper we study how to use the rich structural relationships embedded in XML documents to facilitate the processing of keyword queries. We develop a novel method, called SAIL, to index such structural relationships for efficient XML keyword search. We propose the concept of minimal-cost trees to answer keyword queries and devise structure-aware indices to maintain the structural relationships for efficiently identifying the minimal-cost trees. For effectively and progressively identifying the top-k answers, we develop techniques using link-based relevance ranking and keyword-pair-based ranking. To reduce the index size, we incorporate a numbering scheme, namely schema-aware dewey code, into our structure-aware indices. Experimental results on real data sets show that our method outperforms state-of-the-art approaches significantly, in both answer quality and search efficiency.     

LAF: a new XML encoding and indexing strategy for keyword‐based XML search

As a large number of corpuses are represented, stored and published in XML format, how to find useful information from XML databases has become an increasingly important issue. Keyword search enables web users to easily access XML data without the need to learn a structured query language or to study complex data schemas. Most existing indexing strategies for XML keyword search are based upon Dewey encoding. In this paper, we proposed a new encoding method called Level Order and Father (LAF) for XML documents. With LAF encoding, we devised a new index structure, called two‐layer LAF inverted index, which can greatly decrease the space complexity compared with Dewey encoding‐based inverted index. Furthermore, with two‐layer LAF inverted index, we proposed a new keyword query algorithm called Algorithm based on Binary Search (ABS) that can quickly find all Smallest Lowest Common Ancestor. We experimentally evaluate two‐layer LAF inverted index and ABS algorithm on four real XML data sets selected from Wikipedia. The experimental results prove the advantages of our index method and querying algorithm. The space consumed by two‐layer LAF index is less than half of that consumed by Dewey inverted index. Moreover, ABS is about one to two orders of magnitude faster than the classic Stack algorithm. Concurrency and Computation: Practice and Experience, 2012.© 2012 Wiley Periodicals, Inc.