基于最短路径的道路网络k近邻查询处理

针对基于空间道路网络的k近部查询处理,提出了分布式移动对象更新策略以有效减少服务器计算代价,利用基于内存的空间道路网络部接矩阵、最短路径矩阵结构和移动对象哈希表索引分别对道路网络无向图与移动对象进行存储管理。提出了基于最短路径度量的网络扩展搜索(SPNE)算法,以通过裁剪网络搜索空间来减少k近部查询搜索代价。实验表明,SPNE算法的性能优于传统的NE和MKNN等k近邻查询处理算法。     

信息网数据库管理系统的查询优化

查询是信息网数据库管理系统的重要组成部分。反向查询是一种被广泛应用,并且十分耗时的查询策略,因为在反向查询中对象名未知,在匹配路径之前需要通过路径反向查得对象。针对反向查询,提出了优化算法,从最后一条有价值的路径单元开始反向查询,利用路径上提供的所有信息,将搜索空间限制至最小,使得花费在路径匹配上的时间减少,查询效率得以提升。最后,原始算法和优化算法进行了对比实验,结果表明了优化算法的优越性。     

大规模图上标签集约束路径的集合查询

图数据模型被广泛用于社交网络、生物技术、语义网络等开放、异构环境下的数据建模。标签集约束路径查询是基本路径查询问题之一,因其具有路径描述的灵活性而受到目前研究的重视。目前重点研究布尔查询问题:判断给定顶点对间是否有满足标签集约束的路径,返回是或否。 现研究布尔查询问题的正交问题,称为集合查询问题:给定标签约束集,返回满足标签集约束可达的顶点对。集合查询问题面临两个困难:1)简单地将集合查询问题简化为布尔查询问题的迭代会陷入穷举困境;2)压缩传递闭包的生成树结构虽然能够有效地回答布尔查询问题,但是,这种压缩结构不能有效支持集合查询,因为集合查询需要搜索满足约束连通的所有顶点对。为此,继续采用生成树来压缩标签路径传递闭包,用倒排索引表来加快集合查询所导致的搜索,并进一步给出两个优化算法。在大规模的数据集上的测试表明,本方法在时间和空间效率方面都具有优势。     

空间关键词搜索研究综述

由于越来越多的数据具有位置和文本双重属性,空间关键词查询(spatial keyword query,简称SKQ)应运而生.一个SKQ以一个地理位置和若干关键词作为参数,返回满足空间与文本约束的结果,这些结果往往根据指定公式排列.对现有的空间关键词搜索技术进行了梳理,首先对问题进行了描述,对挑战进行了分析;然后分析了基本空间关键词搜索技术.将文献中提出的各种空间关键词查询进行了划分,对现有的查询处理技术进行分类,对每种类型的技术,从索引技术和查询算法两个方面进行了总结,并从多个角度对它们进行了比较.其后介绍了扩展空间关键词搜索技术,还介绍了与该问题相关的其他研究工作.最后指出了研究中存在的不足以及以后的研究方向.     

半结构化数据查询的处理和优化

半结构化数据的特点是数据的结构不规则或不完整,其模型都基于带根有向图,因此,查询处理过程本质上是对图的搜索过程.另外,通配路径使查询处理更加复杂化.文章详细介绍了异构数据源集成系统Versatile中采取的半结构数据OIM(model for object integration)对象的查询和优化策略,包括查询计划的生成、路径扩展和路径索引、层次索引和基于数据源知识这3种查询优化方法.文章介绍的方法同样适用于其他的半结构化数据模型.     

道路网中的移动对象连续范围查询

研究了采用网络距离的道路网上移动对象连续多范围查询处理技术。设计了道路网、移动对象和查询数据在内存中存储的数据模型。基于该数据模型提出了两种道路网上的移动对象连续多范围查询处理算法。其中,增量式范围查询算法(incremental range query algorithm,IRQA)通过使用扩张树和影响列表结构减少查询的重新计算;组范围查询算法(group range query algorithm,GRQA)利用同一路径上多查询的结果具有相关性这一特点减少查询的重新计算。实验结果表明GRQA算法在查询分布比较集中时性能较优,IRQA算法在查询均匀分布时性能较优,此外,两种算法均优于重新计算所有查询结果的原始算法。     

移动空间安全区域关键字查询算法

随着时代的飞速发展,人们对智能生活的追求不断提高,空间查询也被人们愈来愈重视。移动空间关键字查询,作为一种主要的连续空间查询类型,受到了广泛的研究。在最新的顶尖会议文刊中,提出了一种新的查询类型,称为移动集合空间关键字查询(MCSKQ)。这种类型的查询不断报告一组对象,这些对象在查询移动时共同覆盖查询关键字。同时,返回的对象也必须靠近查询对象并且彼此靠近。计算精确的结果集是一个NP-hard的问题。为了降低查询处理的成本,本文提出了基于安全区域技术的算法,在查询对象移动时,保持精确的结果集。在其基础上,本文基于MCKSQ的思想提出新的优化策略,以降低查询处理成本的方法。     

XML数据的路径表达式查询优化技术

路径表达式作为XML数据查询语言的核心部分,关于它的计算方法的研究成果已有很多,然而针对路径表达式本身进行优化的研究却相对较少.提出了两种针对路径表达式的优化策略:路径缩短策略和补路径策略,从而提高了XML路径查询效率.路径缩短策略根据XML文档模式信息,将路径表达式查询长度缩短,从而简化查询本身以降低需要的查询代价;而补路径策略则试图使用代价更小的等价路径表达式来替换原始查询.经过对实验数据的分析,这两种优化策略对于绝大多数路径表达式查询可以应用,并可大幅度地改进路径表达式的查询性能.     

一种针对反向空间偏好top-k查询的高效处理方法

随着地理位置定位技术的蓬勃发展,基于在线位置服务技术的应用也越来越多.提出一种查询类型——反向空间偏好top-k查询.类似于传统的反向空间top-k查询,对于给定的空间查询对象,该查询返回使该对象满足top-k属性得分的那些用户.但不同的是,该对象的属性不是自身具有的特性,而是通过计算该对象与其他偏好对象之间的空间关系（如距离）而确定.这种查询在市场分析等许多重要领域具有需求,例如,根据查询结果,分析出某个地区中某个设施受欢迎的程度.但是,由于大量空间对象的存在导致对象之间空间关系的计算代价非常高,如何实时地计算出对象的空间属性得分,给查询处理带来很大的挑战.针对该问题提出优化的查询处理算法包括：数据集剪枝、数据集批量处理、基于权重的用户分组等策略.通过理论分析和充分的实验验证,证明了所提出方法的有效性.与普通方法相比,这些方法能够大幅度提高查询处理的执行时间和I/O效率.     

空间数据库中全局最近邻查询处理方法

空间数据库中基于层次化索引结构的全局最近邻(all-nearest-neighbor,All-NN)计算采用单节点展开策略的嵌套循环技术来降低计算开销.在同一数据集合的全局最近邻计算中,基于索引结构带来的对象空间位置临近性特点,抛弃传统理论距离裁剪规则和嵌套循环技术来减少计算和索引节点访问开销.提出了采用局部计算和完备计算两阶段的计算模型来获得全局最近邻结果.首先以叶节点为单位,采用扫描线算法获得节点内部所有对象的局部最近邻结果,然后根据计算结果得到启发式裁剪距离.在第2阶段采用层次化过滤的范围查询算法来获取外部的(可能的)最近邻对象.实验与分析表明该方法可以很好地支持不同种类、大小、分布的数据集合All-NN查询处理,具有良好的实用价值.     

用户偏好约束的空间关键词范围查询处理方法

随着基于地理位置的个性化服务的广泛应用,用户偏好约束的空间关键词范围查询成为了研究热点。现有面向空间关键词范围查询的索引没有考虑用户偏好属性,导致剪枝性能和查询效率较低。为了解决该问题,提出了一种支持用户偏好属性、空间位置、关键词协同剪枝的混合索引BRPQ;并在此基础上,提出了高效的用户偏好约束的空间关键词范围查询处理算法。实验结果表明,相比现有索引,BRPQ索引的构建时间平均减少了13%,查询效率平均提升了20%。     

以目标节点为导向的XML路径查询处理

XML查询语言将复杂路径表达式作为核心内容.为了加速路径表达式处理,基于路径分解和结构连接操作的处理策略需要更深入的研究.以目标节点为导向的XML路径查询处理框架被提了出来.该方法利用了扩展基本操作来减少连接操作的数目.在路径分解和查询计划选择的过程中,利用查询树中的目标节点来避免中间结果的传递.除了分解规则和策略以外,提出了一组扩展的基本操作和实现算法.初步的实验结果显示,该方法具有良好的性能.它为路径查询处理提供了更多的选择.     

距离-关键字相似度约束的双色反k近邻查询方法

针对空间关键字双色反k近邻查询返回结果质量较低的问题,提出了基于距离-关键字相似度约束的双色反k近邻查询方法。首先,通过设置一个阈值将查询结果中质量较低的用户给过滤掉,从而避免了查询结果中出现空间距离相对较远的用户,保证了查询结果质量;然后,为支持该查询,提出了一种关键字多分辨率网格矩形树（KMG-Tree）索引来管理数据;最后,提出了基于Six-region算法的Six-region-optimize算法来提高查询处理效率。Six-region-optimize算法的查询效率相较baseline和Six-region算法分别平均提高了约85.71%和23.45%。基于真实时空数据进行实验测试和分析,实验结果验证了Six-region-optimize算法的有效性和高效性。     

一种新的移动查询路径选择方法

在移动查询路径选择中,约束关系和网络特性对路径选择都有较大的影响,根据这一特点提出了一种新的移动查询的路径选择方法。该方法先把一个查询分解成几个子查询并根据约束条件组合成几条备选路径,然后估算这几条备选路经的元组大小,最后通过查询路径选择算法在这几条备选的查询路径中找到较优的路径。该方法充分考虑了约束关系和网络特性这两个因素,实验表明该方法可以在几条备选路径中求得较优路径。     

Adaptive processing of historical spatial range queries in peer-to-peer sensor networks

We investigate the problem of processing historical queries on a sensor network. Since data is considered to have been already collected at the sensor nodes, the main issue is exploring the spatial component of the query in order to minimize its cost represented by the energy consumption. We assume queries can be issued at any network node, i.e., there is no central base station and all nodes have only local knowledge of the network. On the one hand, a globally optimum query processing plan is desirable but its construction is not possible due to the lack of global knowledge of the network. On the other hand, while a simple network flooding is feasible, it is not a practical choice from a cost perspective. To address this problem we propose a two-phase query processing strategy, where in the first phase a path from the query originator to the query region is found and in the second phase the query is processed within the query region itself. This strategy is supported by analytical models that are used to dynamically select the best processing strategy depending on the query specifics. Our extensive analytical and experimental results show that our analytical models are accurate and that the two-phase strategy is better suited for small to medium sized queries, being up to 10 times more cost effective than a typical network flooding. In addition, the dynamic selection of a query processing technique proved itself capable of always delivering at least as good performance as the most energy efficient strategy for all query sizes. Research supported in part by NSERC Canada.     

Using differential technlques to efficiently support transaction time

We present an architecture for query processing in the relational model extended with transaction time. The architecture integrates standard query optimization and computation techniques with new differential computation techniques. Differential computation computes a query incrementally or decrementally from the cahced and indexed results of previous computations. The use of differential computation techniques is essential in order to provide efficient processing of queries that access very large temporal relations. Alternative query plans are integrated into a state transition network, where the state space includes backlogs of base relations, cached results from previous computations, a cache index, and intermediate results; the transitions include standard relational algebra operators, operators for constructing differential files, operators for differential computation, and combined operators. A rule set is presented to prune away parts of state transition networks that are not promising, and dynamic programming techniques are used to identify the optimal plans from the remaining state transition networks. An extended logical access path serves as a structuring index on the cached results and contains, in addition, vital statistics for the query optimization process (including statistics about base relations, backlogs, and queries-previously computed and cached, previously computed, or just previously estimated).     

传感器网络中节点个数约束查询处理算法

对传感器网络中一类新查询--节点个数约束查询,提出能量有效的查询处理算法.算法主要由查询下发和结果回收两部分构成.查询下发算法首先根据节点个数约束查询的特点提出相关节点选择以及基于Steiner树的查询下发算法.然后对该下发算法以及一种基于洪泛的能量有效查询下发算法的能量消耗进行分析,并对比两种算法的能量消耗从中选择适当的下发算法.结果回收算法提出直接和间接两种结果回收方式,并给出两种方式在进行结果回收时能够节省能量的条件.仿真实验表明,提出的能量有效节点个数约束查询处理算法能够在满足用户查询精度的同时,使其能量消耗低于其他查询处理算法.     

In-Route Nearest Neighbor Queries

Nearest neighbor query is one of the most important operations in spatial databases and their application domains, such as location-based services and advanced traveler information systems. This paper addresses the problem of finding the in-route nearest neighbor (IRNN) for a query object tuple which consists of a given route with a destination and a current location on it. The IRNN is a facility instance via which the detour from the original route on the way to the destination is smallest. This paper addresses four alternative solution methods. Comparisons among them are presented using an experimental framework. Extensive experiments using real road map datasets are conducted to examine the behaviors of the solutions in terms of five parameters affecting the performance. The overall experiments show that our strategy to reduce the expensive path computations to minimize the response time is reasonable. The spatial distance join-based method always shows better performance with fewer path computations compared to the recursive methods. The computation costs for all methods except the precomputed zone-based method increase with increases in the road map size and the query route length but decrease with increases in the facility density. The precomputed zone-based method shows the most efficiency when there are no updates on the road map.