一种高效的移动对象连续多范围查询处理框架

针对连续多范围查询处理,结合多核多线程技术和大容量内存技术,通过将移动对象和查询放在内存中处理,提出了一种基于多线程的连续多范围查询处理框架.该框架基于多核处理器平台采用多线程技术周期性地处理查询和移动对象的更新,并周期性地计算多范围查询的结果.提出了基于移动对象数据均匀划分的多线程连续多范围查询处理算法,该算法以为查询建立的格网索引为基础.给出了该索引的构建思想和更新算法.考虑到基于内存的算法受Cache访问性能影响,提出了基于空间填充曲线的移动对象存储优化方法.实验证明,基于多核平台的多线程处理能够高效地处理连续多范围查询,同时通过移动对象存储优化能够提高算法运行中Cache访问命中率,进而提高算法性能.     

分布式环境下大规模移动对象范围查询算法

移动对象的连续范围查询是许多基于位置的服务的核心问题。针对该问题,提出一种面向大规模移动对象并发范围查询的分布式搜索方法。首先,设计了一种由全局网格索引（GGI）和局部弹性四叉树构成的移动对象分布式动态索引（DDI）结构。其次,提出了一种基于DDI结构的分布式查询算法（DSA）,该算法首先引入了一种在移动对象和查询点的位置连续变化的情况下的查询结果增量更新策略;然后,在增量更新过程中引入一种面向多并发查询的共享计算优化策略,该策略能够根据已有计算结果对移动对象范围查询结果进行增量搜索。最后,基于德国路网模拟了3个具有不同空间分布的移动对象数据集,将DSA与NS(Naive Search)、GI(Grid Index)和分布式混合索引（DHI）进行对比。实验结果表明,与性能最好的对比算法DHI相比,DSA的初始查询时间减少了22.7%,增量查询时间减少了15.2%,性能优于对比算法。     

基于不确定数据的查询处理综述

不确定数据在一些重要应用领域中是固有存在的,如传感器网络和移动物体追踪。在不确定数据上使用传统的查询方法会使查询结果出现偏差,不能满足用户的需求。因此,基于不确定数据的查询处理受到了越来越多的关注。与在确定数据上查询不同,不确定数据上的研究工作将概率引入到数据模型中来衡量不确定对象成为结果集中元素的可能性。由于问题定义和数据模型的不同,不确定数据上的查询类型也多种多样。从问题定义、数据模型、剪枝策略和算法等角度,对基于不确定数据的范围查询、top-k查询以及skyline查询进行了介绍。     

基于范围查询的移动对象快照KNN查询算法

提出一种基于范围查询的移动对象快照K最近邻(KNN)查询算法——SKNN。预估包含结果集的子空间,使用该子空间作为范围,计算查询点的KNN兴趣点,以降低I/O成本。引入移动数据库中的缓存技术,缩短查询的平均响应时间。实验结果表明,当移动对象的规模较大时,SKNN算法的性能较优。     

基于位置范围的道路网skyline查询

随着无线通信和定位技术的发展,道路网skyline查询在基于位置的服务等方面越来越重要。考虑到现今道路网中位置隐私保护和定位设备的精度问题,用户在道路网上的位置通常用一个范围来表示。但是,已有的道路网skyline研究都是基于单一查询点。针对这一问题,研究了一种新的查询——基于位置范围的道路网skyline查询(RNS),提出了一种基于边界点替换的有效查询处理算法。另外,针对已有的道路网skyline查询中复杂的道路网距离计算对查询效率的影响问题,通过计算兴趣点在道路网上的有效skyline路段,将其与道路网信息融合,建立了道路网skyline模型。基于该模型设计了一种能有效支持RNS查询的道路网skyline索引SSR-tree,提出了基于索引的RNS查询处理算法。通过大量实验验证了所提方法的有效性,并比较了基于索引的算法在查询效率和精度上的提高。     

移动对象数据库预测范围聚集查询技术研究

针对预测范围聚集查询处理技术，提出了一种面向移动对象的聚集TPR树索引。聚集TPR树索引在TPR树中间节点中加入移动对象聚集信息以减少预测范围聚集查询所需要的节点访问代价。并增加了一个建于移动对象标识上的哈希辅助索引结构以支持自底向上的删除搜索算法，具有很好的动态更新性能和并发性。提出了一种EPRA查询算法，采用更精确的剪枝搜索准则，大大减少了查询所需要访问的磁盘节点，具有良好的查询性能。     

高度动态环境下移动对象连续K近邻查询算法

针对面向高度动态移动对象集的多用户连续K近部查询,提出了基于查询索引的多用户连续K近邻查询处理(Query Index based Multiple Continuous K-Nearest Neighbor Queries, QI-MCKNN)算法,阐述了查询索引的概念和构建方法,分析了格网大小对查询性能的影响,给出了相应的查询处理算法。实验表明,算法在面对高度动态的移动对象集时,查询处理性能优于基于移动对象格网索引的SEA-CNN算法。     

路网中空间关键字连续范围查询算法研究

空间关键字查询相对传统的位置相关查询而言更能满足实际查询处理的需要。着重探讨路网中结合距离和关键字相似度两个因素的空间关键字查询处理问题,提出解决路网中空间关键字连续范围查询(CRSKQ)的有效方法。提出了一个综合考虑了路网上的道路、对象和路网的连通性的路网模型以支持CRSKQ查询的处理。为了实现连续监控,所提出的算法包括两个阶段,即初始结果获取和查询结果连续监控。初始结果监控阶段,通过路网扩展和关键字匹配寻找满足要求的结果对象;在连续监控阶段,充分利用前面时刻的查询结果来减小连续监控的代价。模拟实验表明,所提出的算法是有效的。     

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

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

基于位置演进模型的两类时空查询算法

为减少历史时间窗时空查询结果偏差,通过假定移动对象在连续位置更新间做匀速直线运动,获取该对象的近似轨迹函数,基于此函数提出简化的位置演进模型。由该模型求解对象轨迹与查询区域边界相交时间点集;由轨迹函数计算对象与查询中心点间距离函数,求解距离函数间相交时间点集。给出基于简化位置演进模型的时间窗时空范围查询、最近邻查询算法。仿真结果表明,与传统算法相比,所提两类查询算法的结果准确度更高。     

路网中移动对象快照K近邻查询处理

扩展了一种支持路网中移动对象的位置相关查询框架的功能,利用存在磁盘上的R树来存储网络连通性和一种基于内存的网格结构来维持移动对象的位置更新,提出了基于范围查询(MNDR)的快照K近邻查询算法(SKNN),对空间中的任意一条边,分析可能受影响的最大数量和最小数量的网格单元格,说明用于快照范围查询处理的搜索空间的最大范围,预估包含查询结果的子空间,使用这个子空间作为范围调用MNDR来有效地计算路网中查询点的KNN POI,降低I/O成本,缩短查询时间。通过实验对比,当规模扩展到数十万的移动对象时,SKNN比种有效查询处理空间网络数据的预计算方法S-GRID有更好大的系统吞吐量。     

面向移动对象连续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位置发生变化时,进一步提出一种高效的增量查询策略,能够最大限度地利用已有查询结果减少当前查询的计算量.最后,在滴滴成都网约车数据集以及两个模拟数据集上进行大量实验,充分验证了算法的性能.     

路网中位置不确定的二元反kNN查询

针对路网限制和物体位置的不确定性,提出了路网中位置不确定的二元反kNN查询（PBRkNN）,旨在查找一组位置不确定的点,使得每个不确定点的kNN包含给定查询点的概率大于一个阈值。为了解决该问题,首先提出一种基于Dijkstra进行剪枝处理的基本算法,即PE算法;接着在PE算法的基础上通过预处理计算出每个点的kNN从而加快查询速度,即PPE算法;而为了进一步减小PPE算法中范围查询的开销,提出PPEE算法,利用网格索引来索引范围查询中要查询的不确定空间点,从而提升算法的效率。最后,在北京和加州路网数据集上进行了大量实验,结果表明通过一些预处理的策略确实可以有效地处理路网中位置不确定的二元反kNN查询。     

无线传感器网络Top-k多查询算法

针对无线传感器网络中多个Top-k查询问题,提出了一种Top-k多查询处理的算法,对接收到的多个Top-k查询请求进行预处理,预处理依据是约束条件,得出两类不同的查询集合:单约束条件的多查询和多约束条件的多查询。针对单约束条件的多查询提出了ETOP算法,该算法首先对排在时间序列最前面的Top-k查询请求进行基于网内处理,然后把查询结果存入基站缓存,并把结果的最小值设定为阈值传输到各个节点,再根据后续查询请求的查询范围进行相应的查询,从而快速地获得Top-k查询结果。实验表明:Top-k多查询方法在能够很好地实现查询的同时,减少了无线传感器网络中的传输消耗和能量消耗。     

道路网中基于RRN-Tree的CKNN查询

现有针对基于道路网络的CKNN查询研究,主要是将道路网络以路段和节点的形式进行建模,转化成基于内存的有向/无向图,该模型存在2个问题:一个是道路网络中路段数据量大,导致索引结构分支过多、移动对象更新频繁;另一个是图表示方法不能很好地处理十字路口转向、U型转弯等交通规则。针对此问题,提出道路网中基于RRN-Tree的移动对象CKNN查询算法,包括索引结构设计和移动对象查询算法设计,采用路线对道路网建模,基于网络边扩展方式,实现复杂条件下的道路网络CKNN查询。实验结果表明,在各种网络密度和兴趣点对象分布密度下,与经典的IMA/GMA算法相比,基于RRN-Tree索引方法的查询性能提高1.5倍~2.13倍。     

一种预测性连续时空区域查询处理方法

预测性连续时空区域查询在用户指定的时间范围期间持续地返回给定未来查询时间范围期间将出现在查询区域的移动对象。论文提出了一种预测性连续时空区域查询处理方法,设计了支持连续查询处理的两种索引结构。移动对象索引用于记录移动对象不断更新的位置信息,它用于支持查询的首次处理。连续查询索引结构用于记录所有查询结果可能受到移动对象位置变化影响的连续查询,它用于支持连续查询处理。实验表明,论文提出的方法能够有效地提高处理大量连续查询的效率。     

时间依赖路网上的移动对象K近邻查询算法

随着基于位置服务的广泛应用,时间依赖路网上的对象查询逐渐成为研究热点。以往研究大多只针对时间依赖路网上的静态对象(如加油站、餐厅等),未考虑到移动对象(如出租车)的情况,而移动对象的查询在日常生活中有着非常广泛的应用场景。因此,文中提出了一种针对时间依赖路网上的移动对象K近邻查询算法TD-MOKNN,该算法分为预处理阶段和查询阶段。在预处理阶段,通过建立路网和网格索引,提出了一种新的移动对象到路网的映射方法,解除了以往研究假设移动对象恰好在路网顶点上的限制;在查询阶段,采用启发式搜索,借助倒排网格索引计算了一种新的高效启发值,通过预处理信息和启发值设计了高效K近邻查询算法,并给出了算法的正确性证明和时间复杂度分析。实验验证了所提算法的有效性,相比现有算法,TD-MOKNN算法在遍历顶点数和响应时间上分别减少了55.91%和54.57%,查询效率平均提升了55.2%。     

道路网络中移动对象的索引研究

为了能有效地实现网络中移动对象的过去、当前和将来轨迹的查询,提出了一种L2R索引,它由两层R树和一个链表结构组成。两层R树用以索引道路网络和移动对象过去的运动,对象当前的位置和将来的预测轨迹信息保存在链表中。L2R索引不仅可以支持网络中的移动对象的轨迹查询,尤其是可方便的在纵向链表中查询在同条路线上的所有对象。在此索引基础上文中实施了对移动对象的范围查询和点查询,最后通过实验表明L2R结构的索引和查询性能均要优越于TPR树。     

可伸缩的增量连续k近邻查询处理

针对基于TPR树(time-parameterized R-tree)索引的大量并发CKNN(continuous k-nearest neighbor)查询处理,提出了一种可伸缩的增量连续k近邻查询处理(scalable processing of incremental continuous k-nearest neighbor queries,简称SI-CNN)框架,通过引入搜索区域进行预裁剪以减少查询更新所需要的TPR树节点访问代价,并引入了增量结果表以保存候选对象,批量地更新查询结果集,具有良好的可伸缩性.基于SI-CNN框架提出了一种增量更新的SI-CNN查询处理算法,能够基于上次查询结果增量的更新查询,支持查询集合中加入或删除查询和移动对象数据集的插入、删除等动态更新操作.实验结果与分析表明,基于SI-CNN框架的SI-CNN算法可以很好地支持大量并发的CKNN查询处理,具有良好的实用价值.