基于结构语义的XML关键字搜索

XML关键字搜索是一个用户友好的信息发现方法,非常适用于XML文档不存在schema的情况,但问题是用户在关键字搜索中很难准确地表达搜索语义.现有的主要XML关键字搜索的研究是基于SLCA(最小最低公共祖先)方法,但该方法可能会丢失一部分有意义的结果.提出一种新的基于语义距离的模型,更全面地考虑XML文档结构的语义特性;在该模型的基础上,设计了多种算法将彼此语义相近的关键字结点聚集在一起形成XML关键字搜索结果,并用大量实验对几种算法进行了比较.     

关系数据库关键字搜索系统Discover的实验与分析

早在2002年,关系数据库中的关键字搜索问题就已经有了很多代表性的研究成果,其中的Discover系统由于其算法经典,在后来的文章中被广泛引用.但是Discover中实验数据并不充分,如关键字个数设定过少、没有给出关键字个数对结果集大小的影响、只在AND语义下进行实验等.由于存在上述问题,使得对关键字搜索问题的研究得不到一些真正有意义的数据.文中实现了Discover中的关键字搜索算法,并对实验进行了进一步的完善,并对实验结果进行了分析和阐述,为关键字搜索提供了更有价值的实验数据和分析结果.     

面向领域的语义搜索引擎的应用研究

针对基于关键字的搜索引擎缺乏语义的问题,提出了一种面向专业领域的语义搜索引擎模型.以领域本体形式化描述为基础,构建本体语义框架,进而给出语义搜索模型.在模型中,以概念、概念-实例以及关键字等3种扩展特征项作为基础,对查询扩展算法和文档语义标注算法进行了研究,并且构建了语义索引,通过引入向量空间模型判定扩展检索词与语义文档的相似度.实验结果表明,该模型较传统模型较大提高了检索的查准率和查全率.     

一种基于语义的服务搜索与匹配方法

Web服务是构建基于面向服务架构(SOA)的应用系统所需的主流分布式计算技术.作者此前提出了一种语义增强服务库,支持基于语义的服务注册、搜索和组装.讨论该服务库中所使用的一种基于语义的服务搜索与匹配方法.该算法不仅考虑了功能性属性而且引入了非功能性属性来进行服务匹配.算法利用所建立的本体对服务进行语义标注,并通过对OWL-S进行扩展,增加了非功能性属性支持.论文给出了服务的定义,详细介绍了服务搜索与匹配的步骤,并以一个服务的搜索为例对算法的使用进行了说明.最后把本文提出的算法与基于关键字匹配的服务搜索算法进行了比较分析,结果表明本文所提出的算法搜索更加准确.论文最后简介了基于该算法的语义库的基本架构及功能.     

基于结构摘要的XML关键字检索

基于最低最小公共祖先(SLCA)的XML关键字搜索语义,提出一种使用XML结构摘要(summary)对关键字进行索引的方法XKSS.XKSS索引方法通过避免重复存储大量XML树上的含义相同的节点,大幅度降低了索引的空间耗费,并提高了查询性能.基于XKSS建立的索引,提出一个算法SSB-SLCA来计算SLCA节点.实验表明,基于XKSS的关键字搜索方法能够更高效地寻找关键字的SLCA.     

一种P2P环境下基于用户行为的语义检索方案

受资源类型多样化、搜索复杂度的制约,现有的P2P文件共享系统中的搜索机制是基于文件名的关键字匹配,这种方法不能发现关键字与资源内容之间的深层关系,因此不能实现语义检索.针对这个问题,提出一种新的搜索方案,该方案建立在已有的搜索机制之上,利用用户的搜索行为和下载行为的规律自动发现关键字和资源间的深层关系,在底层的P2P网络上构建一个元数据空间以辅助搜索.该方案具有实现代价小、时间复杂度低、可进化和支持语义搜索的优点.在Maze系统上的实验表明,该方案具有较高的查询命中率和查询准确率.     

空间关键字个性化语义近似查询方法

现有的空间关键字查询处理模式大都仅支持位置相近和文本相似匹配,但不能将语义相近但形式上不匹配的对象提供给用户;并且,当前的空间-文本索引结构也不能对空间对象中的数值属性进行处理。针对上述问题,本文提出了一种支持语义近似查询的空间关键字查询方法。首先,利用词嵌入技术对用户原始查询进行扩展,生成一系列与原始查询关键字语义相关的查询关键字;然后,提出了一种能够同时支持文本和语义匹配,并利用Skyline方法对数值属性进行处理的混合索引结构AIR-Tree;最后,利用AIR-Tree进行查询匹配,返回top-k个与查询条件最为相关的有序空间对象。实验分析和结果表明,与现有同类方法相比,本文方法具有较高的执行效率和较好的用户满意度;基于AIR-Tree索引的查询效率较IRS-Tree索引提高了3.6%,在查询结果准确率上较IR-Tree和IRS-Tree索引分别提高了10.14%和16.15%。     

一种基于HBase的高效空间关键字查询策略

随着移动定位技术的发展以及智能手机的普及,互联网中空间文本对象的数量正在急速增长,如何在规模庞大且动态增长的空间文本对象中进行高效的空间关键字查询成为了许多空间关键字查询应用所关心的问题.现有的方法通常利用基于R树和倒排索引的混合索引结构来处理空间关键字查询,然而,面对数量巨大而且不断增长的空间文本对象,这些方法往往难以为空间关键字查询的高效性和扩展性提供支持.对此,提出一种基于HBase的空间文本数据索引结构SK-HBase.SK-HBase以HBase作为数据存储,通过有效的数据分配策略对空间文本对象的空间信息和文本信息同时进行索引.在SK-HBase的基础上,本文提出了两种空间关键字查询算法,以保证不同空间范围下的空间关键字查询的高效性和可扩展性.实验证明,我们的方法能够在海量数据下进行高效的空间关键字查询并具有良好的可扩展性.     

一种基于DHT的多关键字搜索新机制

本文在基于结构化P2P路由算法Kademlia的基础上提出了一种新的支持多关键字搜索的DHT(Distributed Hash Table)机制:kNN-Kad(K Neareast Neighbor Kademlia),它使Kademlia网络可以高效的进行主题搜索和多关键字的搜索.kNNKad机制包括资源发布算法和多关键字查找算法,通过仿真,分析了搜索时间复杂度、通信量以及维护代价,其结果表明该机制相对于现有算法具有更高的综合性能.     

关系数据库中支持语义的Top-K关键字搜索

为了增强关系数据库中的关键字搜索查询结果,考虑了多表之间以及元组之间的语义关系,提出了一种语义评分函数.该语义评分函数不仅涵盖了当前的评分思想,并且加入新指标来衡量查询结果与查询关键字之间的相关性.基于该评分函数,提出两种以数据块为处理单位的Top-K搜索算法,分别为BA(blocking algorithm)算法和EBA(early-stopping blocking algorithm)算法.EBA在BA基础上引入了过滤域值,以便尽早终止算法的迭代次数.最后实验结果显示语义评分函数保证了搜索结果的高查准率和查全率,所提出的BA算法和EBA算法改善了现有方法的查询性能.     

ELCA evaluation for keyword search on probabilistic XML data

As probabilistic data management is becoming one of the main research focuses and keyword search is turning into a more popular query means, it is natural to think how to support keyword queries on probabilistic XML data. With regards to keyword query on deterministic XML documents, ELCA (Exclusive Lowest Common Ancestor) semantics allows more relevant fragments rooted at the ELCAs to appear as results and is more popular compared with other keyword query result semantics (such as SLCAs). In this paper, we investigate how to evaluate ELCA results for keyword queries on probabilistic XML documents. After defining probabilistic ELCA semantics in terms of possible world semantics, we propose an approach to compute ELCA probabilities without generating possible worlds. Then we develop an efficient stack-based algorithm that can find all probabilistic ELCA results and their ELCA probabilities for a given keyword query on a probabilistic XML document. Finally, we experimentally evaluate the proposed ELCA algorithm and compare it with its SLCA counterpart in aspects of result probability, time and space efficiency, and scalability.     

模糊XML关键字近似查询方法研究

在精确XML文档上的关键字查询方法的研究大多是基于LCA语义或者其变种语义(SLCA,ELCA等)开展的,将包含所有关键字的最紧致XML子树片段作为查询结果返回。但是这些基于LCA语义产生的查询结果中通常包含了大量的冗余信息,现实世界中存在着大量的不确定和模糊信息,因而如何从模糊XML文档中搜索到高质量的关键字查询结果是一个需要研究的问题。针对模糊XML文档上的关键字近似查询方法进行研究,通过引入最小连接树(MCT)的概念,提出在模糊XML文档上关键字查询的所有GDMCTs问题,并给出解决这一问题的基于栈的算法All fuzzy GDMCTs,该算法可以得到满足用户指定的子树大小阈值和可能性阈值条件的所有GDMCTs结果。实验表明,该算法在模糊XML文档上能够得到较高质量的关键字查询结果。     

不确定数据库上的top-k关键字查询

关系数据库上的关键字检索和不确定数据处理过去一直是两个独立的研究方向。研究了运用关键字方法检索不确定数据的问题,定义了不确定关键字查询的基本模型和语义,提出了一种在属性级粒度的不确定数据库上进行top-k关键字检索的算法。该算法根据用户指定的k值,计算并返回分数最高的前k个结果,其查询结果的评价函数综合考虑了结果与关键字的相关度和结果在可能世界语义下的概率大小。对算法进行了优化,显著降低了计算复杂度。最后通过实验,证明了算法的高效性和实用性。     

Object-stack: An object-oriented approach for top-k keyword querying over fuzzy XML

Keyword search is the most popular technique of searching information from XML (eXtensible markup language) document. It enables users to easily access XML data without learning the structure query language or studying the complex data schemas. Existing traditional keyword query methods are mainly based on LCA (lowest common ancestor) semantics, in which the returned results match all keywords at the granularity of elements. In many practical applications, information is often uncertain and vague. As a result, how to identify useful information from fuzzy data is becoming an important research topic. In this paper, we focus on the issue of keyword querying on fuzzy XML data at the granularity of objects. By introducing the concept of “object tree”, we propose the query semantics for keyword query at object-level. We find the minimum whole matching result object trees which contain all keywords and the partial matching result object trees which contain partial keywords, and return the root nodes of these result object trees as query results. For effectively and accurately identifying the top-K answers with the highest scores, we propose a score mechanism with the consideration of tf*idf document relevance, users’ preference and possibilities of results. We propose a stack-based algorithm named object-stack to obtain the top-K answers with the highest scores. Experimental results show that the object-stack algorithm outperforms the traditional XML keyword query algorithms significantly, and it can get high quality of query results with high search efficiency on the fuzzy XML document.     

XML关键词搜索结果的多样化

可扩展标记语言(extensible markup language,XML)数据的关键词搜索面临着搜索结果数量庞大,同质化严重和不易区分等问题,针对这些问题,提出了一种新的基于多样化的方法.首先从查询结果抽取原型以标识查询结果语义,然后根据结果原型的特点,定义了原型的兴趣度和原型之间的距离,在此基础上,实现了原型的多样化.进一步提出了一种XML关键词搜索结果组织方法,即按照原型聚集查询结果.这种组织方式能够解决上述问题.最后通过实验证明了所提方法的有效性.     

A join algorithm for combining AND parallel solutions in AND/OR parallel systems

When two or more literals in the body of a Prolog clause are solved in (AND) parallel, their solutions need to bejoined to compute solutions for the clause. This is often a difficult problem in parallel Prolog systems that exploit OR and independent AND parallelism in Prolog programs. In several AND/OR parallel systems proposed recently, this problem is side-stepped at the cost of unexploited OR parallelism in the program, in part due to the complexity of the backtracking algorithm beneath AND parallel branches. In some cases, the data dependency graphs used by these systems cannot represent all the exploitable indenpendent AND parallelism known at compile time.In this paper, we describe the compile time analysis for an optimizedjoin algorithm for supporting independent AND parallelism in logic programs efficiently without leaving any OR parallelism unexploited. We then discuss how this analysis can be used to yield very efficient runtime behavior. We also discuss problems associated with a tree representation of the search space when arbitrarily complex data dependency graphs are permitted. We describe how these problems can be resolved by mapping the search space onto the data dependency graphs themselves. The algorithm has been implemented in a compiler for parallel Prolog based on the Reduce-OR process model. The algorithm is suitable for the implementation of AND/OR systems on both shared and nonshared memory machines. Performance on benchmark programs exhibiting AND and OR parallelism on one shared memory machine and one message passing machine is presented.This work was supported in part by NSF Grants CCR-87-00988 and CCR-89-02496.A shorter version of this paper appears in theProceedings of NACLP 1990.     

Retrieving keyworded subgraphs with graph ranking score

Keyword queries have long been popular to search engines and to the information retrieval community and have recently gained momentum for its usage in the expert systems community. The conventional semantics for processing a user query is to find a set of top-k web pages such that each page contains all user keywords. Recently, this semantics has been extended to find a set of cohesively interconnected pages, each of which contains one of the query keywords scattered across these pages. The keyword query having the extended semantics (i.e., more than a list of keywords hyperlinked with each other) is referred to the graph query. In case of the graph query, all the query keywords may not be present on a single Web page. Thus, a set of Web pages with the corresponding hyperlinks need to be presented as the search result. The existing search systems reveal serious performance problem due to their failure to integrate information from multiple connected resources so that an efficient algorithm for keyword query over graph-structured data is proposed. It integrates information from multiple connected nodes of the graph and generates result trees with the occurrence of all the query keywords. We also investigate a ranking measure called graph ranking score (GRS) to evaluate the relevant graph results so that the score can generate a scalar value for keywords as well as for the topology.     

一种基于与或图的语义Web服务自动组合方法研究

单个Web服务提供的功能有限,服务组合成为Web服务应用的一个重要研究方向。提出了一种基于与或图的语义服务自动组合方法。该方法为Web服务引入语义,能将服务搜索空间受限于服务组合与或图中,并能从服务组合与或图中选出最佳组合图,从而达到优化服务组合的目的。仿真实验证明,该方法提高了Web服务组合的成功率和效率。     

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

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

XBridge-Mobile: efficient XML keyword search on mobile web data

Mobile computing over intelligent mobile is affecting human’s habits of obtaining information over Internet, especially keyword search. Most of previous keyword search works are mainly focused on traditional web data sources, in which the performance can be improved by adding more computing power and/or building more offline-computed index. However, it is very challenging to apply the traditional keyword search methods to mobile web-based keyword search because mobile computing has many different features, e.g., frequent disconnections, variety of bandwidths, limited power of mobile devices, limited data size to be downloaded, etc.. To address this challenge, in this paper we design an adaptive mobile-based XML keyword search approach, called XBridge-Mobile, that can derive the semantics of a keyword query and generate a set of effective structured patterns by analyzing the given keyword query and the schemas of XML data sources. Each structured pattern represents one of user’s possible search intentions. The patterns will be firstly sent to the mobile client from web server. And then, the mobile client can select some interested patterns to load the results. By doing this, we can reduce the communication cost a lot between web server and mobile client because only the derived patterns and a few results need to be transferred, not all the keyword search results, by which we can save lots of expenses when the downloaded data is priced. In addition, we can economically maintain the frequent structured pattern queries in the mobile device, which can further reduce the expense of downloading data. At last, we analyze and propose a ranking function to measure the quality of keyword search results, design a set of algorithms to optimize mobile keyword search based on the maintained structured patterns, and present the experimental study of XBridge-Mobile with real XML datasets.