基于空间网络数据库的组最近邻居查询

组最近邻居查询是空间数据库在最近邻居查询上的新问题.目前,对组最近邻居查询的研究局限于欧氏空间,考察的只是对象间的相对位置关系,无法处理现实生活中对象间的连通性问题.鉴于此,本文基于空间网络数据库提出以网络距离为度量标准的组最近邻居查询概念,进而提出作为其算法基础的增量最近邻居查询算法INNN,最后构造出算法NMQM.
实验证明,NMQM是一种有效的组最近邻居查询算法.     

面向移动对象的高效组最近邻居查询方法

组最近邻居查询是移动对象数据库重要的查询类型之一。本文提出了一种基于网格索引结构的剪枝搜索策略,将空间区域划分为网格,通过对象点的网格单元标识减少组最近邻居查询所需要的节点访问代价。用步长迭代法得到查询对象集的质心,提出了一种移动对象组最近邻居查询MOGNN算法,采用更精确的裁剪搜索空间准则,减少了查询所需要访问的节点数目。实验结果与分析表明,基于网格索引的MOGNN查询算法具有良好的查询性能。     

一种有效的历史移动对象轨迹的k最近邻居查询算法

近10多年来,研究者们已经在k最近邻居(kNN)查询方面做了很多工作,但是对于移动对象轨迹的kNN查询处理却研究得很少.鉴于此,研究了在存储有历史移动对象轨迹信息的TB树结构上的kNN查询问题,并且提出了一种有效的基于最佳优先搜索范例的kNN(k≥1)查询算法,称为BFPkNN.BFPkNN是一种I/O最佳的算法,即它仅仅访问有可能包含最终结果的结点.同时,为了减少存储空间和CPU代价,又提出了若干有效的剪枝策略.大量的实验证明BFPkNN在效率和可扩展性上均大大胜过其他同类算法.     

加权路网空间中动态聚集最近邻居查询算法

聚集最近邻居（ANN）查询作为空间数据库的经典问题在网络链路结构优化、物流集散点选址、共享汽车服务等方面有着重要的意义,能有效促进物流、移动互联网行业以及运筹学等领域的发展。现有的研究存在如下不足：缺少针对大规模动态路网数据的高效索引结构,在数据点位置实时移动以及路网权重动态更新的场景下算法的查询效率较低。针对上述不足,提出动态场景下的ANN查询算法。首先利用G-tree作为路网索引,提出将四叉树和k-d树等空间索引结构与增量欧氏空间限制（IER）算法结合起来的剪枝方法,以完成静态空间下的ANN查询;随后针对动态场景下数据点位置频繁更新的问题,加入时间窗口及安全区域更新策略,以减少算法的重复计算次数,实验结果表明效率能提高8%～85%;最后针对路网权重变化的ANN查询问题,提出两个基于校正的连续查询方法,在历史查询结果的基础上,根据权重变化的增量来得到当前的查询结果,在某些场景中能够有效降低50%左右的误差。理论研究和实验结果表明,所提算法能够高效并且较为准确地解决动态场景下的ANN查询问题。     

基于Voronoi图的路网k聚集最近邻居节点查询方法

道路网络中的k最近邻居节点(k-NN)查询及其变种越来越受到研究者们的关注.其中,k聚集最近邻居节点(k-ANN)查询能为多个查询点返回聚集距离最小的前k个被查对象,因此具有较高的研究价值及广阔的应用前景.目前解决该查询问题的主要方法是根据A*算法在路网上通过逐步扩展来搜寻结果,这样会导致响应时间很长,不能满足用户的需...     

移动对象的动态反向k最近邻研究

反向最近邻查询是空间数据库中最重要的算法之一。传统的反向最近邻查询方法主要是针对静态对象的查询,随着无线通讯和定位技术的快速发展,移动对象发出的查询请求成为新的研究热点。该文将TPR-tree作为算法的索引结构,并提出了基于矩形框的对角线的修剪策略,将半平面修剪策略进行改进,给出了移动对象的动态反向k最近邻的查询方案。     

利用覆盖区域设计与实现移动对象索引

对移动对象索引频繁更新问题进行了研究,提出了一种基于区域覆盖的空间索引结构虚拟网格四分树(virtual grid quadtree,VGQ);通过索引移动对象所在的区域而非移动对象本身来减少由于移动对象位置的改变而引起的索引结构的改变,并给出了近似连续范围查询算法及增量和自底向上优化策略。实验结果表明,VGQ在查询效率和空间使用上是一种有效的索引方法。     

改进的CNN搜索算法

对如何寻找一个新插入点覆盖的所有分点问题进行了研究,提出了适用于搜索移动对象的一个最近邻居的直接比较方法,其计算量要少于原来CNN搜索算法所采用的方法。对于搜索移动对象的多个最近邻居的情况,提出了一种避免计算新插入点到所有分点距离的动态比较方法。     

移动对象的反向k近邻查询算法的研究

传统的反向k近邻查询的研究主要集中在k=1时的单色移动对象的反向最近邻查询上,单色和双色的反向k近邻查询问题还没有解决。利用网格索引结构结合60°平面修剪策略,提出了一种解决单色和双色的移动对象的连续反向k近邻查询方法。最后实验结果验证了算法的有效性。     

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

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

基于Voronoi图及其对偶图的反最近邻查询

最近邻查询是地理信息系统领域经常遇到的问题,而反最近邻查询是在最近邻查询的基础上提出的一种新的查询类型。在分析利用Voronoi图进行最近邻查询的基础上,提出了基于Voronoi图及其对偶图Delaunay图的反最近邻查询,大大缩小了在海量空间数据库中进行反最近邻查询的查询范围。     

时空数据库变体最近邻查询问题探讨

最近邻查询在地理信息系统、智能交通系统、多媒体应用以及数据挖掘等领域有着广泛的应用,随着对最近邻查询问题研究的深入,其应用前景和发展空间将更为广阔。针对近几年时空数据库中提出的最近邻查询的多种变体查询问题进行了详细地介绍和分析,总结了解决这些变体最近邻查询问题的有效方法,最后对最近邻查询问题的发展方向进行了展望。     

道路网络中的多类型K最近邻查询

空间数据库的多类型最近邻查询逐渐受到人们的关注,关于K最近邻查询的研究也较多,但多类型K最近邻查询的研究还存在空白。针对道路网络中的多类型K-最近邻（MT-KNN）问题,结合多类型最近邻查询及K最近邻查询的理论,提出了多类型K最近邻查询算法。通过对分层编码视图进行扩展,建立了多路径分层编码视图,并利用逐步扩展局部路径的方法,实现了多类型K最近邻查询,实验结果分析表明算法具有较好的性能。     

空间数据库平面线段近邻查询问题研究

空间数据库的近邻查询近几年受到人们越来越多的关注.近邻查询根据程度不同可分为点与点的近邻查询、点与线段、线段与线段的近邻查询.目前,前两者研究的较多,后者没有查到相关文献.提出平面线段与线段的近邻查询问题.有针对性地解决一些空间物体无法抽象为点的情况.平面线段的近邻查询在现实中有着广泛的应用价值.根据平面线段与线段是否相交分为两类;不相交的平面线段再根据位置关系分成9种情况.分别对上述各种情况进行讨论研究.给出了线段近邻查询的筛选规则、定理和查询算法,进行了实验分析和比较,新方法实现了平面线段与线段的近邻查询,具有较高的查询效率.     

基于差分隐私的社交网络位置近邻查询方法

针对社交网络中近邻位置查询时个人位置隐私泄漏的问题,采用地理不可区分性机制对位置数据添加随机噪声,提出了一种隐私预算分配方法。首先,对空间区域进行网格化分割,根据用户在不同区域的位置访问量来个性化分配隐私预算;然后,为了解决在扰动位置数据集中近邻查询命中率偏低的问题,提出了一种组合增量近邻查询（CINQ）算法,以扩大需求空间的检索范围,并利用组合查询过滤冗余数据。在仿真实验中,与SpaceTwist算法相比,CINQ算法的查询命中率提高了13.7个百分点。实验结果表明,CINQ算法有效解决了因为查询目标的位置扰动所带来的查询命中率偏低问题,适用于社交网络应用中扰动位置的近邻查询。     

移动对象最近邻查询实时更新算法

在移动对象最近邻查询实时更新算法中,安全区一般是难以求解的不规则凸多边形。针对该问题,将安全区设计为圆形,在此基础上提出一种效率更高的移动对象最近邻查询更新算法。将算法分别运行于基站上的最近邻管理系统和移动对象上的Client管理系统,实验结果表明,该算法可以降低系统的存储代价,提高其数据处理性能。     

面向存在不确定对象的组最近邻查询方法

组最近邻查询是空间对象查询领域的一类重要查询,通过该查询可找到距离给定查询点集最近的空间对象.由于图像分辨率或解析度的限制等因素,空间对象的存在不确定性广泛存在于某些涉及图像处理的查询应用中.这些对象位置数据的存在不确定性会对组最近邻查询结果产生影响.本文给出面向存在不确定对象的概率阈值组最近邻查询定义,设计了高效的查询处理机制,通过剪枝优化等手段提高概率阈值组最近邻查询效率,并进一步提出了高效概率阈值组最近邻查询算法.采用多个真实数据集对概率阈值组最近邻算法进行了实验验证,结果表明所提算法具有良好的查询效率.     

On multi-type reverse nearest neighbor search

This paper presents a study of the Multi-Type Reverse Nearest Neighbor (MTRNN) query problem. Traditionally, a reverse nearest neighbor (RNN) query finds all the objects that have the query point as their nearest neighbor. In contrast, an MTRNN query finds all the objects that have the query point in their multi-type nearest neighbors. Existing RNN queries find an influence set by considering only one feature type. However, the influence from multiple feature types is often critical for strategic decision making in many business scenarios, such as site selection for a new shopping center. To that end, we first formalize the notion of the MTRNN query by considering the influence of multiple feature types. We also propose R-tree based algorithms to find the influence set for a given query point and multiple feature types. Finally, experimental results are provided to show the strength of the proposed algorithms as well as design decisions related to performance tuning.     

不确定性对象的反向最近邻查询

多数不确定性对象的反向近邻查询不能明确回答某个不确定性对象是否为查询对象的反向最近邻,针对该问题,提出概率反向最近邻查询的概念,设计不确定性对象的概率反向最近邻查询的索引结构,给出一种基于该结构的不确定性对象的反向最近邻查询算法。