CYPK-KNN:一种改进的移动对象KNN查询算法

目的改进YPK—KNN算法以提高其查询效率，方法利用网格对移动对象进行索引．确定一个尽可能小的搜索区域，使得此区域一定包含距离查询点最近的K个移动对象，然后在此区域内完成查询．最的KNN查询，结果针对真实数据集的实验结果表明在同等条件下，改进算法的查询执行时间明显小于原算法．而且随着移动对象个数的增加和网格划分粒度的减小这种优势随之增加．结论改进的移动对象YPK—KNN查询算法有效提高了原算法的查询效率．     

基于网格索引的Top-k偏好查询算法

目的设计基于网格索引的Top-k偏好查询算法,提高Top-k偏好查询问题的解决效率.方法利用网格索引,采用概念划分的方法,实现基于范围查询和NN查询两种方式的Top-k偏好查询算法.结果通过真实数据集测试结果表明算法能够结合网格索引的优点,与基于R树索引的传统算法相比,在k值不断增加的情况下,查询效率提高了50%,能适应多种空间特征数据对象集合.结论网格索引可以有效处理Top-k偏好查询.     

一种改进的散乱数据点的k近邻快速搜索算法

提出了一种基于二次分割的自适应最小包围盒的栅格化策略，提高了散乱数据点k近邻搜索算法的速度。采用传统分块算法对点云空间进行首次分割，在此基础上估算点云平均点距，并利用平均点距估算结果对点云数据空间重新进行划分。分块结果使得k近邻搜索算法的搜索范围大大缩小，搜索速度明显提高。     

基于多线程的不确定移动对象连续k近邻查询

针对不确定数据下的大规模连续k近邻查询请求,基于不确定移动对象连续k近邻查询的Rate方法,提出高效的基于多核多线程的并行查询处理框架.根据查询对象的运动速度与相对位置确定查询请求间是否采用查询复用,确定查询复用时的距离边界.提出密度网格扩展的多线程数据分发方法,解决了负载均衡问题,将空间位置相邻的查询请求划分到同一线程,提高查询复用率.通过多线程间的内存共享机制,对计算过的移动对象的预测区域实现计算复用.在大规模交通数据集上验证了所提算法的有效性与查询性能,相比传统的Rate方法,所提并行算法的加速比可达37.     

一种快速的反向k近邻查找算法及其改进

提出一种快速的反向k近邻查找算法,该方法利用现代计算机具有外存便宜、运行速度快的特点,预先计算数据之间的距离,并组织为数据索引块存储于外存,由计算机在空闲时自动进行维护.在进行反向最近邻查询时,只需读入相应的索引块,就可进行直接查询,其时间复杂度为O(N),而且不受k的影响.为减少索引块的读取时间,提出一种改进方法来有效地压缩索引块,仅用必要的二进制位来存储对象之间的距离,并将冗余减少到最低水平,提高了算法的效率.最后通过实验分析评估算法的有效性和效率.     

基于相关反馈的高维图像检索方法

传统索引方法在高维情况下会面临维数灾难问题，基于向量近似的索引方法是有效的高维检索方法．对向量近似方法中k近邻搜索算法加以改进，应用到基于相关反馈的交互式图像检索系统中．根据反馈过程前后的距离变化特性，在进行k近邻搜索过程中，将上轮次的查询结果和用户反馈信息用作过滤信息，可减少特征向量的访问数量．在大容量真实图像数据库上的实验表明，将新算法应用干相关反馈过程的图像检索中，可提高k近邻搜索速度．     

R-树和四叉树的空间索引结构:RQOP_树

针对现有的基于R-树和四叉树的空间索引结构中存在的问题,通过建立数据矩形间的序关系对数据空间进行分割,提出了一种新的空间数据索引结构:RQOP树.在此结构中,节点的构造是按照空间数据的分布来进行的而不是像其它基于R-树和四叉树的空间索引结构只是对数据空间进行均匀划分而得到,使树的高度尽可能低,同时使兄弟节点间的交叠相对较小.在区域查询算法中引入了查询窗口包含节点MBR的判断加快了查询的速度.给出了RQOP树的生成、节点插入和区域查询算法,并给出了相应算法的可行性和正确性定理及时间复杂度分析.实验表明:新索引结构的查询速度明显加快.     

支持高效路径查询的数据空间索引方法

首先,通过索引连接例子,分析了影响效率的因素。在扩展倒排索引基础上,构建了B-树索引,以支持大规模数据的高效查找。然后,构建了二级索引,以减少索引连接中的大量重复判断。最后,提出了路径查询算法。实验结果表明:该索引方法能够有效地解决索引连接问题和显著地改善数据空间路径查询效率。     

度量空间中基于距离孤立点的快速挖掘

将数据点的k最近邻（k-NN）距离作为孤立程度指标能够有效地发现数据集中的孤立点,但是基本算法需要O(N2)次数据点间的距离计算,不适用于大数据集.为此提出了一种利用度量空间中三角不等式的快速挖掘算法--提前修剪（ADVP）.ADVP利用每次k-NN查询中保存的近邻点到被查询点的距离计算出近邻点的孤立程度上界.孤立程度上界小于已发现最弱孤立点的孤立程度的数据点可被修剪而无须进行k-NN查询.基于抽样方法优化了搜索次序以提高修剪效果.同时将ADVP自然地扩展为增量式算法.在标准大数据集上的实验结果表明,ADVP和现有算法相比明显节省了计算开销,具有更好的伸缩性;增量式ADVP能够有效地处理新增数据.     

三维散乱数据点集k近邻的快速搜索算法

从数据点的空间排列特点出发提出了k近邻搜索算法，利用多向链表对数据集进行排序，综合考虑了数据集的范围、点的总数、搜索步长及最近点数目k，并采用了空间包围策略，可以给出接近于最佳搜索速度的步长e和k值，并且在搜索终止准则上进行改进，使近邻点的搜索范围大大缩小，搜索速度加快。     

基于V~＋图的移动K近邻查询研究

移动K近邻查询（MkNN）找到一个移动查询点的K个连续最近邻。目前解决此类查询的方法有两种：利用采样的方法和基于安全区域的方法。在传统的安全区域方法基础上提出一种基于安全区域的技术来计算MkNN,称为V＋图。此方法除了数据对象外还利用查询点和查询空间的信息,给出基于V＋图的MkNN查询算法和相应定理及其证明。     

基于聚集块的多用户连续K最近邻多线程查询

当对城市道路网络中的对象进行查询时,已研究出连续的K近邻查询技术,但在一般情况下服务器会同时收到多个查询请求,为了提高查询效率,降低多查询代价,提出一种聚集块的共享查询算法并建立多用户连续查询处理框架,采用流水线处理策略,将查询分为查询预处理、查询执行及查询结果分发3个执行阶段,利用扩展树存储查询结果。实验结果表明,在目标点分布比较密集的情况下,本算法明显优于其它算法。     

移动点的反向最近邻查询

反向最近邻（RNN）查询是空间数据库查询的一个重要的问题。随着无线通讯的发展,时空数据库中反向最近邻查询问题越来越受到关注。本文基于Voronoi图的定义和性质,采用一种不同于Delaunay三角剖分的另外一种三角剖分进行研究,其优势在于对于某个特定点,包含它的三角形的数量较少,查询效率较高。     

一种连续最近邻查询的优化方法

连续最近邻查询是空间数据库中最重要的查询之一,在地理信息系统和位置定位服务等领域有重要应用.给定一个空间数据集P和查询线段q,连续最近邻查询返回结果＜R,T＞,其中T是一个间隔,R是这个间隔中所有点的最近邻.已有的连续最近邻查询算法无法实现I/O的优化,为此,提出一种优化的连续最近邻查询方法,该方法具有较高的I/O效率,不仅在减少磁盘访问数量方面进行优化,同时也提高CPU的性能.     

基于模糊k近邻的样本预选取的支持向量机分类算法

在支持向量机（SVM）方法中采用模糊☆近邻方法进行样本预选取,旨在保留最优分类超平面附近的样本点,去除远处样本点,使训练样本集减小,消除冗余,从而减小所需内存．实验结果表明,该方法无论是训练速度还是分类精度都远远好于单独的SVM分类器．     

空间数据库中反k最远邻查询方法

在欧式空间下反最远邻查询算法的研究已取得了很多成果,但反尼最远邻查询问题还未得到有效解决。本文提出一种反k最远邻查询算法,有效地解决了反足最远邻查询问题,查询算法采用了过滤一提炼的解决模型。在过滤阶段,提出了反远中垂线裁剪方法。该裁剪法是通过做中垂线来过滤不是查询点的反七最远邻的点。在提炼阶段,提出了反远范围尼查询提炼方法。该提炼方法是通过判断对象点是否在设定的范围外来验证该点是否是查询点的反女最远邻。最后通过实验验证了所提算法的有效性。     

一种改进KNN的无人机图像快速拼接方法

为了更好解决基于K近邻算法特征匹配速度问题,采用图像像素点经纬度数据加快特征点匹配的无人机图像拼接方法。利用拍摄图片信息里的地理坐标,计算影像像素点经纬度数据,然后计算出两张图像重合部分,利用重合部分特征点经纬度数据大致相同这一特点提高K近邻算法匹配速度,改进后的算法在匹配准确度比传统算法提高了43%左右,最后选用最佳缝合线法对图像进行拼接,获得了质量较好的全景图。     

Real-time road traffic states estimation based on kernel-KNN matching of road traffic spatial characteristics

The accurate estimation of road traffic states can provide decision making for travelers and traffic managers. In this work,an algorithm based on kernel-k nearest neighbor(KNN) matching of road traffic spatial characteristics is presented to estimate road traffic states. Firstly, the representative road traffic state data were extracted to establish the reference sequences of road traffic running characteristics(RSRTRC). Secondly, the spatial road traffic state data sequence was selected and the kernel function was constructed, with which the spatial road traffic data sequence could be mapped into a high dimensional feature space. Thirdly, the referenced and current spatial road traffic data sequences were extracted and the Euclidean distances in the feature space between them were obtained. Finally, the road traffic states were estimated from weighted averages of the selected k road traffic states, which corresponded to the nearest Euclidean distances. Several typical links in Beijing were adopted for case studies. The final results of the experiments show that the accuracy of this algorithm for estimating speed and volume is 95.27% and 91.32% respectively, which prove that this road traffic states estimation approach based on kernel-KNN matching of road traffic spatial characteristics is feasible and can achieve a high accuracy.     

一种基于影响区域的CBRkNN查询方法

针对以集合点为发起者的双色反向k最近邻（BRkNN）查询效率问题,提出一种联合查询方法.BRkNN查询查找的是以查询点为k最近邻的点集,双色反向k最近邻联合(CBRkNN)查询查找的是以查询集合中某一设施集合为k最近邻的点集.该方法通过构造查询集合的影响区域来处理CBRkNN查询问题,任何一个物体落入影响区域就是查询结果,反之则不属于查询结果.算法通过画出用户感兴趣设施集合和用户不感兴趣设施集合之间的所有垂直平分线,计算集合中每个设施的优势支配区域,找出被优势支配区域覆盖个数小于k次的凸多边形区域以构造影响区域.在此基础上算法对影响区域进行点包含性查询得到最终结果.通过实验验证了算法在不同的用户规模、用户感兴趣/不感兴趣设施规模和不同的k值条件下都具有较小的时间消耗,从而说明影响区域的使用可以提高查询方法的有效性.