路网中查询点速度不确定的连续k近邻查询方法

提出一种路网中查询点速度不确定的连续k近邻查询方法.查询点在起始位置向服务器提出查询请求,得到k近邻的候选集.随着查询点的移动,利用有效候选集计算当前的k近邻,而不必再向服务器请求,从而减少了服务器计算代价.当候选集部分失效时,由服务器返回候选集中失效的兴趣点的当前信息,使候选集有效.当候选集完全失效时,由查询点重新向服务器提出查询请求,得到新的候选集.并提出一种计算候选集的优化方法,降低了查询代价.最后,通过实验验证了所提算法的有效性.     

移动对象历史轨迹的连续最近邻查询算法

提出一种直接在原始时空坐标系下对一维移动对象的历史轨迹进行连续最近邻查询的算法,给出相关的定义与定理,通过分析轨迹之间的交点及轨迹线段单调性等特征,利用以前所求得的最近邻结果信息进行连续最近邻的查询判断。实验结果与分析表明,该算法具有较好的性能。     

路网中速度不确定移动对象的k近邻查询

目前在基于道路网的移动对象的各类查询研究中,大多都是在假定移动对象速度固定不变的基础上进行的.而实际上因为外界环境和自身情况等不确定性因素的影响,对象的速度可能会发生变化.基于此,本文提出一种基于路网的速度不确定的移动对象的k近邻查询处理方法.在查询时刻根据查询点位置执行查询操作,得到构成查询点k近邻的候选对象集合,再根据概率计算方法得到结果集及其概率.实验结果表明本文所提方法是有效的.     

面向移动对象连续k近邻查询的双层索引结构

移动对象连续k近邻（CKNN）查询是指给定一个连续移动的对象集合,对于任意一个k近邻查询q,实时计算查询q的k近邻并在查询有效时间内对查询结果进行实时更新.现实生活中,交通出行、社交网络、电子商务等领域许多基于位置的应用服务都涉及移动对象连续k近邻查询这一基础问题.已有研究工作解决连续k近邻查询问题时,大多需要通过多次迭代确定一个包含k近邻的查询范围,而每次迭代需要根据移动对象的位置计算当前查询范围内移动对象的数量,整个迭代过程的计算代价占查询代价的很大部分.为此,提出了一种基于网络索引和混合高斯函数移动对象分布密度的双重索引结构（grid GMM index,GGI）,并设计了移动对象连续k近邻增量查询算法（incremental search for continuous k nearest neighbors,IS-CKNN）.GGI索引结构的底层采用网格索引对海量移动对象进行维护,上层构建混合高斯模型模拟移动对象在二维空间中的分布.对于给定的k近邻查询q,IS-CKNN算法能够基于混合高斯模型直接确定一个包含q的k近邻的查询区域,减少了已有算法求解该区域的多次迭代过程;当移动对象和查询q位置发生变化时,进一步提出一种高效的增量查询策略,能够最大限度地利用已有查询结果减少当前查询的计算量.最后,在滴滴成都网约车数据集以及两个模拟数据集上进行大量实验,充分验证了算法的性能.     

移动对象的连续最近邻查询算法

介绍了一种索引结构———TPR树和静态环境中基本的最近邻查询算法,并提出了影响时间这一概念,将其运用到最近邻查询算法中,可以完成移动对象的连续最近邻查询。     

一种移动对象增量组最近邻居查询方法

基于移动对象增量最近邻居查询(INCNN),提出一种移动对象增量组最近邻居查询方法(INCGNN)。该方法以较小的代价求出每次更新时刻的组最近邻居。针对组最近邻居查询的特点,给出了k+1组最近邻居查询改进算法,椭圆剪枝和延迟更新3种优化查询的策略。实验结果表明,INCGNN明显优于REEGNN,3种优化策略能较好地提高查询性能。     

保护位置隐私和查询内容隐私的路网K近邻查询方法

位置隐私和查询内容隐私是LBS兴趣点(point of interest,简称POI)查询服务中需要保护的两个重要内容,同时,在路网连续查询过程中,位置频繁变化会给LBS服务器带来巨大的查询处理负担,如何在保护用户隐私的同时,高效地获取精确查询结果,是目前研究的难题.以私有信息检索中除用户自身外其他实体均不可信的思想为基本假设,基于Paillier密码系统的同态特性,提出了无需用户提供真实位置及查询内容的K近邻兴趣点查询方法,实现了对用户位置、查询内容隐私的保护及兴趣点的精确检索;同时,以路网顶点为生成元组织兴趣点分布信息,进一步解决了高强度密码方案在路网连续查询中因用户位置变化频繁导致的实用效率低的问题,减少了用户的查询次数,并能确保查询结果的准确性.最后从准确性、安全性及查询效率方面对本方法进行了分析,并通过仿真实验验证了理论分析结果的正确性.     

基于受限移动对象当前及将来时刻检索的时空索引结构研究

在给定的空间及时间范围内,如何构建高效的时空索引结构,以实现对移动对象快速有效的检索,是实现定位服务、智能交通、数字化战争等诸多应用中所迫切需要解决的问题.本文依据移动对象的运动特点,提出了一种面向当前及将来时刻快速更新及有效检索的索引结构—PQR树.PQR树是综合PMRQuad树和R*树的结构,首先依据道路分布用PMRQuad树将移动对象的索引空间实行粗略的层分割,将所有快速移动对象与道路相关联.然后用R*树索引分布在各个子空间块内的类静止对象.实验结果表明PQR树具有良好的更新和查询性能.     

Oporto: A Realistic Scenario Generator for Moving Objects

The spatio-temporal database research community has just started to investigate benchmarking issues. On one hand we would rather have a benchmark that is representative of real world applications, in order to verify the expressiveness of proposed models. On the other hand, we would like a benchmark that offers a sizeable workload of data and query sets, which could obviously stress the strengths and weaknesses of a broad range of data access methods. This paper offers a framework for a spatio-temporal data sets generator, a first step towards a full benchmark for the large real world application field of smoothly moving objects with few or no restrictions in motion. The driving application is the modeling of fishing ships where the ships go in the direction of the most attractive shoals of fish while trying to avoid storm areas. Shoals are themselves attracted by plankton areas. Ships are moving points; plankton or storm areas are regions with fixed center but moving shape; and shoals are moving regions. The specification is written in such a way that the users can easily adjust generation model parameters.     

基于模糊-粗糙集的移动对象k近邻预测

已往移动对象k近邻预测的研究中,有各种不确定性的分析以及对象本身预测位置不确定性的处理,而预测位置模糊不确定性导致其k近邻查询边界的粗糙不确定性的相关处理仍是空白.本文应用模糊一粗糙集的理论,先分析了已有方法得出的预测位置的模糊性,再用传统方法求得基于预测位置的扩展k m近邻集,最后借助模糊一粗糙隶属函数来最终确定所求k近邻集合中的各个点.实验数据表明,本方法明显提高了k近邻集合相对移动对象实际位置的精确度.     

不确定移动对象的模糊时空范围查询

指出不确定性和模糊性在时空语义上的区别;提出不确定移动对象的模糊时空范围查询问题,即查询条件中时间、空间范围的外延是模糊的,无清晰的边界,而目标对象的位置不确定;用模糊集表示模糊查询条件,概率密度函数表示移动对象在各自不确定区域内的可能位置分布;给出了不确定对象关于模糊查询条件匹配度的计算方法;设计了基于α截集的无效对象排除和有效对象确认规则及查询算法.算法规则适用于任意概率密度分布.现有的确定或不确定范围查询可以看成是模糊时空范围查询的特例.通过实验验证了算法的效率,在各种参数设置下,约有30%~90%的查询结果可在不计算匹配度的情况下获得.     

球面上的K最近邻查询算法

针对球面上数据对象点集的特征和K最近邻查询的需求,提出2种处理球面上K最近邻查询的算法:基于查询轴的K最近邻查询算法(PAM方法)和基于查询圆面的K最近邻查询算法(PCM方法).对2种算法进行实验比较,结果表明,PAM方法和PCM方法都适合处理球面上的最近邻查询问题,PAM方法在存储量和查询复杂度方面相对于PCM方法具...     

不确定移动对象概率Skyline集的查询更新

Skyline查询的研究已从传统的静态Skyline操作延伸到动态的、不确定数据集上的Skyline查询和计算上。研究了移动环境下,查询点位置固定、目标点处于运动状态并且位置不确定情况下的连续概率Skyline计算问题。这个过程中,移动对象与查询对象之间的距离随时间不断变化。移动对象由于其运动状态导致位置无法精确定位,因此移动对象之间的支配关系只能采用概率形式表示,且随时间不断变化。给出了移动对象间的支配概率的定义,以及移动对象Skyline概率的定义,并定义了触发事件来记录对象支配概率发生变化的时刻,实现概率Skyline计算的连续跟踪和动态更新。提出了基于事件触发的连续概率Skyline查询算法(event triggered continuous probabilistic Skyline query for uncertain moving object,U-ECPS),对移动环境下的Skyline集进行连续查询和更新。大量的实验结果验证了U-ECPS算法的有效性。     

面向多核多线程的移动对象连续K近邻查询

针对移动对象的多用户连续K近邻查询处理问题,结合多核多线程技术的发展,提出了一种基于多线程的两阶段多用户连续K近邻查询处理框架.将查询处理分为查询预处理阶段和查询执行阶段,分别执行数据更新任务和查询处理任务,每个阶段都设计了优化cache访问命中率,并利用多线程技术提高多用户连续查询处理并行性的方法及数据结构.提出了一...     

时空数据库中多个最近邻对象的查询算法

在时空数据库中，最近邻查询用于对某个查询对象，在被查询对象中找出离它最近的一个或多个对象。该文在TPR树这一时空索引的基础上，提出了一种高效的最近邻查询算法，能够支持移动对象的多个最近邻对象的查询，并在性能上也有所提高。     

移动点对象HR索引及反向最近邻查询

在此提出了一种基于速度分布的HR树索引结构,首先在速度域中对移动对象集进行规则划分,根据速度标量大小将移动对象划分到不同的速度树中,每棵速度树中移动对象具有相近的速度;对每棵速度树中的移动对象,则利用时间间隔进行划分。HR树索引增加了两个分别建于叶节点和根节点之上的Hash辅助索引结构,并基于HR树提出了反向最近邻查询算法,具有很好的动态更新性能和并发性。实验结果与分析表明,基于HR树索引的反向最近邻查询算法具有良好的更新及查询性能,优于通用的TPR树索引。     

移动点对象HR索引及反向最近邻查询

在此提出了一种基于速度分布的HR树索引结构,首先在速度域中对移动对象集进行规则划分,根据速度标量大小将移动对象划分到不同的速度树中,每棵速度树中移动对象具有相近的速度;对每棵速度树中的移动对象,则利用时间间隔进行划分。HR树索引增加了两个分别建于叶节点和根节点之上的Hash辅助索引结构,并基于HR树提出了反向最近邻查询算法,具有很好的动态更新性能和并发性。实验结果与分析表明,基于HR树索引的反向最近邻查询算法具有良好的更新及查询性能,优于通用的TPR树索引。     

A Road Network Embedding Technique for K-Nearest Neighbor Search in Moving Object Databases

A very important class of queries in GIS applications is the class of K-nearest neighbor queries. Most of the current studies on the K-nearest neighbor queries utilize spatial index structures and hence are based on the Euclidean distances between the points. In real-world road networks, however, the shortest distance between two points depends on the actual path connecting the points and cannot be computed accurately using one of the Minkowski metrics. Thus, the Euclidean distance may not properly approximate the real distance. In this paper, we apply an embedding technique to transform a road network to a high dimensional space in order to utilize computationally simple Minkowski metrics for distance measurement. Subsequently, we extend our approach to dynamically transform new points into the embedding space. Finally, we propose an efficient technique that can find the actual shortest path between two points in the original road network using only the embedding space. Our empirical experiments indicate that the Chessboard distance metric (L) in the embedding space preserves the ordering of the distances between a point and its neighbors more precisely as compared to the Euclidean distance in the original road network.     

一种车辆移动对象相似轨迹查询算法

车辆移动对象的相似轨迹查询问题是当前移动对象数据管理研究中的一个热点,可以应用在车辆缉查防控、出行规律分析及城市道路规划等诸多领域.当前,随着车辆移动对象监测手段的不断丰富,车辆移动对象数据逐渐表现出流式不间断产生、数据量急剧增大的特征.现有的移动对象相似轨迹查询方法在面对具有上述特征的车辆移动对象数据时在查询正确性和查询效率方面暴露出诸多问题.论文针对这种大规模车辆移动对象数据流下的相似轨迹查询问题,提出一种基于双阈值支持度的车辆移动对象相似轨迹查询算法,该算法通过对车辆移动对象数据的预处理来减少查询中涉及的移动对象数据量,以提高移动对象相似轨迹查询的效率,同时保证查询正确性.实验表明,该文提出的算法,在保障正确查询相似轨迹的前提下,效率比传统相似轨迹查询算法提高很多.     

Indexing the Trajectories of Moving Objects in Networks*

The management of moving objects has been intensively studied in recent years. A wide and increasing range of database applications has to deal with spatial objects whose position changes continuously over time, called moving objects. The main interest of these applications is to efficiently store and query the positions of these continuously moving objects. To achieve this goal, index structures are required. The main proposals of index structures for moving objects deal with unconstrained 2-dimensional movement. Constrained movement is a special and a very important case of object movement. For example, cars move in roads and trains in railroads. In this paper we propose a new index structure for moving objects on networks, the MON-Tree. We describe two network models that can be indexed by the MON-Tree. The first model is edge oriented, i.e., the network consists of nodes and edges and there is a polyline associated to each edge. The second one is more suitable for transportation networks and is route oriented, i.e., the network consists of routes and junctions. In this model, a polyline also serves as a representation of the routes. We propose the index in terms of the basic algorithms for insertion and querying. We test our proposal in an extensive experimental evaluation with generated data sets using as underlying networks the roads of Germany. In our tests, the MON-Tree shows good scalabiliy and outperforms the competing index structures in updating (index creation) as well as in querying.*This work was partially supported by a grant Gu 293/8–l from the Deutsche Forschungsgemeinschaft (DFG), project Datenbanken für bewegte Objekte (Databases for Moving Objects).