基于道路网的连续k近邻查询算法

针对增量式监测算法(IMA)的冗余搜索问题,提出一种基于IMA改进的移动对象连续k近邻(Continuous k Nearest Neighbor, CkNN)查询处理新算法。采用增量式查询处理机制;利用距离相近的查询其查询结果大部分相同这一特性,在以查询点为中心进行网络扩展之前,首先执行一个预处理过程,分析相近的其他查询的扩展树,并重用其中的有效部分,从而避免了对道路网的盲目扩展;且在节点的网络扩展中,通过应用具有相同扩展方向的其他查询的扩展结果,不仅减少了对道路网的重复扩展,还节省了计算代价。实验结果表明,所提算法同传统算法相比较, 缩短了查询响应时间,提高了运行效率,并且适用于不同类型的k近邻查询。     

一种采用扩展Dewey编码非归并的小枝模式查询算法

小枝模式查询是XML查询中重要的操作,已经有许多种算法提出,如TwigStack和TJFast算法等,但是他们都是基于归并思想的,不能避免大量的不必要的路径归并.本文提出的TwigWM(Twig Without Merging)算法使用部分栈与链表的结构来实现非归并查询,由于从扩展Dewey编码中能够直接得到祖先元素结点的编码,所以TwigWM算法采用扩展Dewey编码.实验结果表明,TwigWM算法要优于TJFast、Twig2Stack等算法.     

基于扩展倒排索引的不确定XML关键字查询算法

现有的不确定XML关键字查询算法均需遍历不确定XML文档,并且算法在执行过程中需要频繁的字符串比较,造成时间浪费。针对上述问题,提出基于扩展倒排索引的不确定XML关键字查询算法Pr E。扩展倒排索引有效地存储了不确定XML文档中节点的相关信息,根据扩展倒排索引即可初始化动态哈希表和序号编码链表,并且Pr E算法在执行过程中利用整数的比较代替了字符串的比较。理论分析与实验结果表明,Pr E算法是一种高效的不确定XML关键字查询算法。     

基于自动机的XML流多查询处理

XML流数据处理在研究领域引起广泛关注,该文针对XML流上的多查询处理提出一种算法,把多个查询合并为一个共享前缀的查询树,应用自动机和运行时栈相结合的方法,单遍扫描XML流处理数据流上的多个查询。该算法采用一种分层栈结构保存查询模式匹配候选集,利用XML节点的区间编码来确定节点之间的关系,返回整条匹配路径。     

连续不确定XML的Top-k查询算法研究

为了解决连续不确定XML高效的top-k查询,提出CProTJFast算法.该算法基于P-文档模型,扩展PEDewey(probabilistic extended Dewey)编码支持连续分布类型节点的编码,采用路径概率下限值进行节点过滤,并针对连续概率密度函数制定过滤策略,从而在计算连续节点概率之前过滤掉不参与结果的节点.实验结果表明,采用连续节点过滤策略的CProTJFast算法有效地提高了连续不确定XML的top-k查询效率.     

GIS中文查询系统中间语言的形成研究

由于GIS中文查询语句与空间扩展SQL语句相差很大，直接转化非常困难，所以需要有某种中间语言作为过渡。本文对GIS中文查询系统中间语言的形成进行了研究，提出了以句子栈、实体栈、查询目标栈、查询条件栈和句型字符串为结构的中间语言，制订了空间查询语句的文法规则，设计了GIS中文查询语句到中间语言转换的算法。实验证明，该算法可以完成大部分查询语句到中间语言的转化。     

基于完全加权关联规则的局部反馈查询扩展

针对现有查询扩展存在的缺陷,将完全加权关联规则挖掘技术应用于查询扩展,提出新的查询扩展模型和扩展词权重的计算方法;提出基于完全加权关联规则挖掘的局部反馈查询扩展算法。该算法能自动从初检的前列文档中挖掘与原查询相关的完全加权关联规则,从规则中提取与原查询相关的扩展词,实现查询扩展。实验结果表明,与现有查询扩展算法比较,该查询扩展算法的检索性能得到很好的改善和提高。     

基于局部类别分析和遗传算法的查询优化算法

查询扩展是信息检索中优化查询的一种有效方法。针对信息检索中用户查询关键词与文档标引词不匹配的问题,提出一种基于局部类别分析和遗传算法的查询优化算法。该算法分两个阶段实现:第1阶段对用户提交的查询Qold进行扩展,采用基于局部类别分析的查询扩展方法选择查询扩展词构成新查询Qnew;第2阶段对新查询Qnew进行权重分配,采用遗传算法对扩展后的查询进行权重调整得到最优查询向量,再次对测试集中的文档进行二次检索。实验结果表明,该算法比单独使用局部上下文分析算法、局部类别分析算法均有更优的检索性能。     

完全加权关联规则挖掘及其在查询扩展中的应用*

为了将完全加权关联规则挖掘技术应用于查询扩展,提出面向查询扩展的基于多种剪枝策略的完全加权词间关联规则挖掘算法,该算法能够极大地提高挖掘效率;提出了一种新的查询扩展模型和扩展词权重计算方法,使扩展词权值更加合理,在此基础上提出一种新的基于局部反馈的查询扩展算法,该算法利用完全加权关联规则挖掘算法自动从局部反馈的前列初检文档中挖掘与原查询相关的完全加权关联规则,构建规则库,从中提取与原查询相关的扩展词,实现查询扩展。实验结果表明,查询扩展算法的检索性能确实得到了很好的改善和提高,与现有查询扩展算法比较,在相同的查全率水平级下其平均查准率有了明显的提高。     

基于相关性和语义相似度融合的查询扩展方法

针对局部共现查询扩展算法查准率不高、性能差的缺点,提出了一种基于相关性和语义相似度的查询扩展算法RSIQE（relativity and similarity inosculate query expansion）。该方法首先用局部共现查询扩展算法扩展出n个相关扩展词,继而利用知网资源计算查询的相似度和扩展词的相关性,在此基础上融合扩展的相关度来得到N个扩展词的排序,通过对扩展词序列赋权来重新计算新查询中各词的权重,由新查询词赋权迭代得到检索结果。实验表明,该扩展方法比传统局部共现查询扩展算法不仅具有更优的检索性能,而且检索精度进一步提高。     

Matching twigs in fuzzy XML

A considerable amount of twig pattern matching algorithms have been proposed to holistically process a twig query. Those algorithms mainly focus on twig pattern query with the AND-logic. However, there is often a need to process a twig query with the OR-predicates. Furthermore, the existing algorithms fall short in their ability to support twig query with OR-logic in fuzzy XML. To overcome this limitation, in this paper, we first introduce a novel encoding scheme to represent node information in fuzzy XML. Based on the encoding scheme, we then propose an effective algorithm for matching a twig pattern query with the AND/OR-logic in fuzzy XML. Our approach adopts a compact stack technique to process the complicated twig query consisting of both AND-logic and OR-logic. More importantly, our method eliminates re-scanning unnecessary portions of XML documents and redundant intermediate results. Finally, the experimental results demonstrate the performance advantages of our approach.     

概率XML文件树结点概率的查询算法

概率XML文件是概率数据的网络数据交换和表示标准,元素取值及其概率的查询与计算是概率XML文件的重要研究内容.概率XML文件树是一种有效的概率XML文件的数据模型,定义了概率XML文件树的基本路径和扩展路径,提出了根据可能世界原理将概率XML文件树分解为普通子XML树的集合的算法,根据路径分析原理将概率XML文件树分解为子概率XML树的集合的算法和相应的查询与计算结点及结点集合概率的算法,并通过实验进行了比较分析.实验结果表明:这两种方法是有效的;与前一种方法比较,后一种方法适合较大的概率XML文件树、结点及结点集合的概率的查询,计算过程较简单.     

一种XML文档索引及查询处理方式

本文首先论述了传统XML路径模式索引方式，在此基础上提出面向元素的XML文档索引方式和相关算法，以及使用扩展的后序遍历序号进行元素节点标识的方案，并给出了该索引方式和元素节点标识方案下规则路径表达式查询和树型模式查询处理的方法，最后说明该方式在效率上优于传统索引方式下规则路径表达式查询和树型模式查询处理。     

Nonrecursive incremental evaluation of Datalog queries

We consider the problem of repeatedly evaluating the same (computationally expensive) query to a database that is being updated between successive query requests. In this situation, it should be possible to use the difference between successive database states and the answer to the query in one state to reduce the cost of evaluating the query in the next state. We use nonrecursive Datalog (which are unions of conjunctive queries) to compute the differences, and call this process incremental query evaluation using conjunctive queries. After formalizing the notion of incremental query evaluation using conjunctive queries, we give an algorithm that constructs, for each regular chain query (including transitive closure as a special case), a nonrecursive Datalog program to compute the difference between the answer after an update and the answer before the update. We then extend this result to weakly regular queries, which are regular chain programs augmented with conjunctive queries having the so-called Cartesian-closed increment property, and to the case of unbounded-set insertions where the sets are binary Cartesian products. Finally, we show that the class of conjunctive queries with the Cartesian-closed increment property is decidable.Parts of the results in this paper appeared as extended abstracts in theProceedings of the 1992 International Conference on Database Theory (LNCS 646, Springer-Verlag), and in theProceedings of the 1993 International Workshop on Database Programming Languages (Workshops in Computing, Springer-Verlag).Guozhu Dong gratefully acknowledges support of the Australian Research Council through research grants, and the Centre for Intelligen Decision Systems.Work by Jianwen Su was supported in part by NSF Grants IRI-9109520 and IRI-9117094.     

MiniCon: A scalable algorithm for answering queries using views

The problem of answering queries using views is to find efficient methods of answering a query using a set of previously materialized views over the database, rather than accessing the database relations. The problem has received significant attention because of its relevance to a wide variety of data management problems, such as data integration, query optimization, and the maintenance of physical data independence. To date, the performance of proposed algorithms has received very little attention, and in particular, their scale up in the presence of a large number of views is unknown. We first analyze two previous algorithms, the bucket algorithm and the inverse-rules, and show their deficiencies. We then describe the MiniCon, a novel algorithm for finding the maximally-contained rewriting of a conjunctive query using a set of conjunctive views. We present the first experimental study of algorithms for answering queries using views. The study shows that the MiniCon scales up well and significantly outperforms the previous algorithms. We describe an extension of the MiniCon to handle comparison predicates, and show its performance experimentally. Finally, we describe how the MiniCon can be extended to the context of query optimization. Received: 15 October 2000 / Accepted: 15 April 2001 Published online: 28 June 2001     

基于扩展路径表达式的XML查询

XML查询问题是当前计算机界研究的热点问题之一，国内外学者提出了众多的模型与算法．其中，日本学者Makoto Murata等提出采用扩展路径表达式来表达查询，并利用hedge自动机和字符串自动机进行XML的查询计算．这种方法与采用路径表达式控制的XML查询相比，克服了后者不能充分利用XML文档有序性的缺点．另外，扩展路径表达式具有较强的表达能力，可以表达任何MSO(一元二阶逻辑)查询．因此，扩展路径表达式已作为XML查询问题研究的主要理论框架之一，但是扩展路径表达式的编写比较困难，表达式也比较复杂，导致算法时间复杂度的提高．在扩展路径表达式中引入通配符，使得扩展路径表达式更加简单灵活；同时在查询的计算过程中提出并应用带截止集的自动机提高计算的时间效率．     

扩展子图同构问题的优化算法

针对扩展子图的匹配问题,根据Ullmann剪枝和QuickSI的不同特性,提出优化处理距离信息的加边算法。根据Query中各个顶点到不同label顶点的最短距离进行剪枝,采用动态加边算法减少加边的运算时间,能够处理规模不大的稀疏图。在AIDS数据库上的实验结果表明,在不同距离值的条件下,QuickSI算法的平均运行速度比Ullmann算法快一个数量级以上。     

面向PSTP查询的高效处理算法

在使用"不完全结构的约束查询(PSTP查询)"从XML文档中获取信息时,用户可以根据自身对XML文档结构的熟悉程度,在查询表达式中灵活地嵌入结构约束条件,从而满足完全不了解、完全了解及了解部分结构信息的各种用户的查询需求。提出一种基于扩展Dewey编码的查询处理算法,可以在仅扫描一遍元素的情况下,处理任意形式的PSTP查询。不同数据集上的实验结果表明,EDPS算法在处理twig查询、不包含"*"结点的PSTP查询及包含"*"结点的PSTP查询时,综合性能明显优于已有方法。