时空数据库中反向最近邻查询的方法研究

随着无线通讯及连续移动对象寻轨技术的高速发展,迫切需要提出解决大量移动对象查询的有效方法。本文提出了一个解决连续移动点反向最近邻查询的算法,同时也提出了解决连续移动点的最近邻查询算法。     

范围最近邻查询方法研究

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

基于路网的连续K最近邻查询

连续K最近邻(CKNN)查询是最近邻查询的扩展,可广泛地应用于地理信息系统、城市规划、智能交通等领域.CKNN查询搜索某一路径上所有点的K个最近的感兴趣对象.本文研究基于交通路网的连续K最近邻查询问题,不同于传统的基于欧式空间的CKNN查询,基于路网的CKNN查询中对象间的距离度量不再是欧式距离,而是基于路网的最短可达距离.显然,传统的基于欧式距离的CKNN查询算法并不能直接应用于基于路网的CKNN查询问题.本文提出了一种基于路网的高效的CKNN查询算法-IIE算法,广泛实验表明本文提出的IIE算法优于传统的IE算法.     

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

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

基于Voronoi图的最近邻查询的索引结构的研究

基于Voronoi图的最近邻查询在计算几何中已被研究了相当长一段时间。但在以往的研究中,基于Voronoi图的最近邻查询究竟是基于何种具体的索引结构去实现对查询空间的搜索的,却很少被提及。本文把传统的R树和Voronoi图在解决最近邻查询问题中的优越性相结合,提出了一种新的索引结构:VR树。进而提出了基于VR树索引结构的NN查询算法并对这该算法进行分析,在理论上证明了这个算法较基于R树索引结构的最近邻查询算法优。     

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

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

道路网络中移动对象的连续反k最近邻查询算法

在道路网络中,对象的位置和运动被约束在网络中,对象之间的距离不是传统的欧氏距离,而是由网络连通性决定的网络距离,基于欧氏空间的反k最近邻查询算法不适用于道路网络。为了解决道路网络中移动对象连续的反k最近邻查询问题,给出了道路网络的一种索引结构及一种利用扩展树处理查询的方法,在此基础上,提出了道路网络中适用与单、双色连续反k最近邻查询算法（CRkNNMA算法）,证明了该算法的正确性。     

基于不确定Voronoi图的概率障碍最近邻查询

障碍最近邻查询是针对存在障碍物情况下的一类最近邻查询问题,在地理信息系统以及存在障碍的空间分析等领域有着重要的应用价值。不确定对象的障碍最近邻查询问题将不确定因素引入到障碍最近邻查询中,使其更贴近现实需求。针对不确定对象的障碍最近邻查询问题,提出不确定对象的障碍距离和障碍作用集等概念,利用不确定Voronoi图的性质,提出基于不确定Voronoi图的概率障碍最近邻查询算法,实验结果表明,提出的算法具有较好的性能。     

K-最近邻分类技术的新发展与技术改进

K-最近邻算法是数据挖掘分类方法中最常用的算法之一.在很多实际问题上都有应用.本文对近年来基于K-最近邻算法的各种改进技术进行了分析.从速度提高和准确度提高两个方面给予了归纳.     

空间网络数据库中基于M-tree索引的反最近邻查询算法

欧式空间中的反k最近邻查询算法不适用于空间网络环境,故采用任意度量空间中的M-tree索引结构,进行空间网络数据库中的反k最近邻查询处理.首先通过预计算的方法得到网络距离信息,依据此距离信息,对空间网络对象建立M-tree索引结构.然后,给出并证明了M-tree中间结点修剪定理,提出一种适用于空间网络环境的反k最近邻查询算法.最后实验验证了该算法的有效性.     

分布式网络中 CKNN 查询的 BORA 优化汇聚

针对时空数据库中,移动对象轨迹的连续K近邻查询(continuous K nearest neighbor query,CKNN)的查询效率较低的问题,以及在分布式的移动对象数据库(moving objects databases,MOD)环境下,提升对应查询结果的数据汇聚效率问题进行了研究.在CKNN查询中,设计优化了查询海滩线的更新算法,通过在轨迹数据结构中增加更新标志位,减少了轨迹线段参与的判定运算;同时在假设的类网格覆盖的分布式空间环境下,利用基于Bresenham覆盖的路由汇聚(Bresenham-based overlay for routing and aggregation,BORA)方法,进行查询结果的汇聚;并针对不同近邻参数、轨迹数目、移动对象速度、汇聚方式等对查询时间的影响进行了仿真实验;仿真结果表明,不同参数数值的增加延长了处理时间,基于BORA的汇聚方式比一般的汇聚方式节省了更多的处理时间,提高了系统查询及处理的效率.     

空间多样化约束下的移动k近邻查询

考虑为移动中的查询对象连续返回k个距离近并且满足空间多样化约束的对象，提出了空间多样化约束下的移动k近邻(SDC-MkNN)查询.在此，满足空间多样化约束代表对象之间的相互距离大于距离阈值.为了高效处理SDC-MkNN查询问题，提出了两种基于安全区域技术的算法.算法均通过减少重新计算查询结果的次数来提高查询效率.其中一种为精确算法EA，可连续返回精确的查询结果；另一种为近似算法ρAA，可连续返回具有近似率保障的近似查询结果.采用真实数据集验证了所提出算法的有效性.     

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

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

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

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

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

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

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

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

P2P环境下面向不确定数据的kNN查询方法

由于仪器的不精确和网络延时等原因,在传感器网络和P2P系统中数据都存在不确定性.为解决此问题,基于现有的集中式的不确定数据的kNN查询方法,提出了一种在P2P环境中对不确定数据的kNN查询方法.该方法在super-peer的网络拓扑结构的基础上,以一种扩展的R树(P2PR-tree)作为此查询算法的空间索引结构,解决P2P环境中对多维数据的索引.并且结合两种剪枝策略减小了候选集的范围和减少了查询在P2P网络中的网络代价.实验结果表明,该方法在减少网络代价方面具有较高的性能.     

一种基于路网D树的无线广播环境下路网最近邻查询处理算法

位置相关查询是数据库领域的一个研究热点。重点研究了无线广播环境下路网最近邻查询（NN）处理问题。对一个给定的路网结构及路网上分布的数据对象,构造对应的路网Voronoi图（NVD）,并在NVD图的基础上构建路网D树索引结构。然后,将路网D树索引结构线性化以支持无线广播环境下路网NN查询的处理,并提出了相应的路网NN查询处理算法。模拟实验表明,所提出的算法是有效的。