空间k近邻查询的新策略

有效执行空间k近邻查询是地理信息系统尤其关心的问题,空间近邻查询是基于空间索引的树的遍历过程,苦测量距离和剪枝策略选取适当,可以极大地减少搜索空间所需访问的事点数,基于Rousspoulos等提出的测量距离,提出2个新的近邻搜索剪枝策略,用于空间k近邻查询,给出了搜索算法,并用算例表明该策略具有更好的剪枝效果,提高了空间k近邻查询的效率。     

公路网上移动对象连续k近邻查询的一种方法

公路网上移动对象连续k近邻查询是最近时空数据库查询中的一个研究热点,它是在一个时间段内找到离查询点最近的K个移动对象.我们分析了现有查询方法,存在的问题主要是运动对象位置随时间而频繁变化以至于不能及时更新运动对象的信息而导致返回KNN结果不正确.为了解决这些问题,采用一种距离预计算方法,使计算量减少,从而为更新通讯获得更多时间.通过实验证明,我们提出的方法是有效的.     

无线数据广播环境下k近邻查询研究

近邻查询问题是基于位置的查询的重要问题之一,是要找到距离查询点最近的k个对象的集合。无线数据广播技术能够有效地避免C/S模式在处理海量数据时的弊端,也能够对用户的位置信息进行隐私保护。将无线数据广播技术应用到k近邻查询中,利用Hilbert曲线组织空间结构,结合无线数据广播技术具有线性的特性,通过过滤和剪枝两个步骤,最终找到查询点的k个最近邻集合。     

Spark环境下基于网格索引的轨迹k近邻查询方法

移动对象轨迹的k近邻(k nearest neighbor trajectories,kNNT)查询是一种重要的空间信息服务,主要用于寻找与给定轨迹最近邻的k条轨迹,被广泛地应用于智能交通、信息推荐等领域。随着轨迹数据量的快速增长,由于单机计算资源的限制,传统集中式环境下的kNNT查询效率和可扩展性无法满足实际要求。为了解决这个问题,设计了轨迹数据的分布式网格索引结构,该索引在Spark环境下将轨迹切分并映射到网格中,并引入轨迹还原表以保留查询时候选子轨迹段间的连续性。基于此索引,提出了Spark环境下的轨迹k近邻查询方法kNNT-Grid。实验结果表明,kNNT-Grid方法在分布式环境下实现了良好的查询效率和可扩展性,能够应对海量轨迹数据的k近邻查询需求。     

GRkNN:一种组反k近邻查询方法

针对传统查询方法在查询点有多个对象时,对每个查询点逐个执行查询导致运行时间较长的问题,提出一种组反k近邻查询(GRkNN)方法.该方法将多个查询点视为一个整体考虑,并采用剪枝和核实两阶段策略.实验表明,该方法能更有效地实现数据库更新操作,缩短了运行时间.     

基于数据广播的空间关键字查询处理

为了解决无线广播环境下空间关键字查询的问题,研究广播环境下空间关键字k近邻查询处理(BkSKQ),设计了一种结合kd树、倒排位图和(1,m)索引机制的空间关键字索引(ISKW)结构,以有效地组织对象的关键字信息、位置信息以及索引信息.该索引结构为客户的查询处理提供有效的指导,使得他们尽可能只下载查询处理所必须的数据信息.在ISKW索引结构的基础上,提出了BkSKQ查询处理算法.最后,通过模拟实验验证了提出的索引结构和算法的性能,实验结果表明所提出方法在访问时间和调谐时间上明显优于基于IR树的方法(BIRM).     

连续近邻查询方法的研究

连续近邻查询(CNN)是时空数据库中一种重要的查询类型。Voronoi图解决连续近邻查询问题,思想简单明晰,但Voronoi图构造代价太高,尤其是高阶的Voronoi图。本文利用分枝限界的思想去界定预创建Voronoi图生成点范围的上限。提出了一种动态地创建局部Voronoi图的办法解决连续近邻查询问题。这种方法只是在给定查询段上所有点的k个近邻范围上限内创建一个局部的k阶Voronoi图,这样会大大降低基于Voronoi图的连续k近邻查询的代价。     

面向组近邻的Top-k空间偏好查询

空间偏好查询是当前空间查询研究中的一类热点问题,而现有的空间偏好查询不能有效支持面向组用户的位置服务应用.为此,提出一类新型空间偏好查询——面向组近邻的Top-k空间偏好查询(Topk spatial preference query for group nearest neighbor).该查询通过查找特征对象的λ子集组近邻最终为用户返回评分值最高的前k个λ子集.为了高效执行这一查询,给出了两种查询算法:TSPQ-G及TSPQ-G*.其中TSPQ-G*在TSPQ-G的基础上,通过空间剪枝及高效的特征对象索引树遍历策略大幅减少I/O代价,进而有效提高了该查询的执行效率.实验采用多个数据集验证了所提算法在不同参数设置下的有效性.     

路网中速度不确定移动对象的K范围近邻查询方法

K范围近邻查询是指查找给定范围区域内所有点的近邻对象。现有工作主要考虑对象固定不动情况下的K范围近邻查询,实际上对象不但可能移动,而且由于外界环境和自身情况等不确定性因素的影响,移动对象运动速度的不确定性也是客观存在的。基于此,本文考虑了速度不确定移动对象的K范围近邻查询,提出路网中速度不确定的移动对象的K范围近邻查询的处理算法,利用共享查询的思想减少了冗余查询的代价,最后,通过实验验证了所提算法的有效性。     

公路网移动终端的KNN查询技术

公路网中移动兴趣点(POIs)的查询处理是一个难点,目前的研究多基于欧氏距离对静态POIs进行处理,不能很好地适应移动环境下终端弱连接和频繁移动的需要.文中在公路网移动计算场景下,设计了一种存储分区数据对象的结构来表示公路网图形模型,提出适用于移动终端的连续KNN查询(CQ-KNN)算法.该算法改进了Wang等提出的MKNN算法,将逐层渐近探测和检索边列表结合起来进行近邻查询,避免了MKNN算法在限定层数不够却不得不执行范围查询时所带来的开销;同时使用缓存策略来支持移动终端提交的连续查询请求,并给出基于广播位置失效报告的缓存一致性维护策略.仿真结果表明,CQ-KNN算法较MKNN算法有更快的CPU处理速度和更短的网络响应延时,并且能支持移动终端的离线KNN近似查询.     

范围最近邻查询方法研究

范围最近邻(RNN)查询检索到一个区域内每个点的最近邻(NN),它是点和连续最近邻查询的推广.本文将范围看作矩形,分析了二维空间中范围最近邻查询的性质,描述了算法处理过程,并对提出的算法进行了性能分析.     

无索引空间数据库的基于最优点的集合最近邻查找算法

针对度量空间中的无索引空间数据库,提出一种基于最优点的集合最近邻查找算法及其改进算法.采用真实数据集与人工生成的数据集对算法进行测试,评估所提出算法的效率.实验结果表明,所提算法的效率优于组最近邻居查询算法,并且对于高维数据空间,所提出的算法有较高的稳定性.由于查询区域中数据点的数量比较少,改进的基于最优点的集合最近邻...     

不同维数下空间对象的反最近邻查询

反最近邻查询是在最近邻查询基础上提出的一种新的查询类型,是空间数据库的应用拓展,在不同维数下,根据不同的索引结构,反映出空间对象的反最近邻查询差异性较大,从不同索引结构的特性出发,分析了低维环境下基于R*-树的反最近邻查询优势,提出高维环境下一种新的基于SRdnn-树索引结构的空间对象反最近查询方法,优化了不同维数下空间对象的反最近查询性能,提高了查询效率.     

空间数据库反向最近邻聚类方法

针对当前空间数据库聚类方法未考虑降维后的距离特征反向结果, 导致空间数据分量失真, 存在聚类精度低、 耗时长的问题, 提出一种空间数据库反向最近邻聚类方法. 首先, 通过选取训练样本集实现核矩阵的特征分解, 获得其距离特征修正值去除初始值的影响; 然后, 根据核主成分分析（KPCA）降维并结合降维后的距离特征反向结果, 利用反向最近邻聚类方法与扩展的部分失真搜索法相结合, 实现空间数据的聚类; 最后利用选定的聚类中心对数据集进行计算, 计算数据集第一维分量与聚类中心第一维分量之间的失真, 得到反向最近邻, 直至所有空间数据均找到所属类别, 最终完成空间数据库反向最近邻聚类. 实验结果表明, 该方法提高了空间数据的聚类精度, 减少了空间数据聚类所用时间.     

移动查询点的最近邻查询方法研究

移动查询点的最近邻查询在时空数据库查询的领域具有很重要的地位。本文提出了一个以处理动态环境下的K个最近邻居(K-NN)查询问题的有效的方法。     

约束的移动对象最近邻轨迹查询

提出了一种新的查询概念,即约束的移动对象最近邻轨迹(constrained nearest neighbor search on moving objects trajectories,简称CNNMOT)查询.针对两阶段算法分阶段处理最近邻查询和范围查询的缺陷,对传统空间最近邻算法进行了改进和扩展,使其能够合并到一步完成,并对传统的mindist定义进行了修改.实验结果表明:该改进算法能较好地克服两阶段算法的缺陷,并在数据量较大时仍保持较高的性能.     

Efficient evaluation of monitoring top-t most influential places

The continuous top-t most influential place (CTtMIP) query is defined formally and solved efficiently in this paper. A CTtMIP query continuously monitors the t places with the maximum influence from the set of places, where the influence of a place is defined as the number of its bichromatic reverse k nearest neighbors (BRkNNs). Two new metrics and their corresponding rules are introduced to shrink the search region and reduce the candidates of BRkNNs checked. Extensive experiments confirm that our proposed approach outperforms the state-of-the-art competitor significantly.     

并行空间连接查询处理

基于顺序空间连接查询的效率不能令人满意，利用并行控制提高空间连接查询效率。空间连接查询的并行处理方法最重要的特征是任务分配根据多路平面扫描顺序，避免了连接处理过程中处理器之间的通信花费，提出基于空间连接花费模型的任务分配方法和基于花费估计的动态任务分配策略，并给出了花费模型。该模型经实际应用效果明显。