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

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

基于格网划分的道路最近邻查询算法

针对现有道路最近邻查询算法均以数据点作为道路端点进行查询,并未考虑数据点在道路上的情况,使得在大数据量时查询效率不够理想的问题,利用格网划分算法进行解决。利用分治法的思想,将查询区域进行格网划分,缩小有效的查询区域,快速定位查询点所在道路,进而找到最近邻数据点。研究结果表明:当数据量足够大时,格网划分算法与增量网络扩张(INE)算法相比,查询时间明显降低,效率明显提升,格网划分查询的时间复杂度为O(1);当数据量较少时,格网划分算法与INE算法相比,查询时间减少并不明显,表明格网划分算法更适用于大数据量最近邻查询。     

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

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

一种基于人工免疫的小波特征集合最近邻人脸识别算法

将人工免疫及集合最近邻方法应用于人脸检测中,实现一种基于特征的人脸检测算法.首先对人脸图象进行多分辨率小波分解,用低频分量来描述人脸识别,实现数据压缩,并有效削弱光照的影响;然后对小波低频图象进行傅立叶变换,分析变换后的系数矩阵,取得人脸图象的特征向量;采用了人工免疫中的克隆选择算法,对一个人的多张不同表情的人脸图像进行训练,产生一个简约特征集合,用这个简约集合代表此人的人脸特征数据库;就待识别人脸而言,以待识别人脸到人脸数据库中各个人脸特征集合的集合最近邻作为识别结果.实验结果表明,人工免疫算法可以有效地获取训练样本的人脸特征集简约集合,再通过集合最近邻进行人脸识别,可以提高准确率.     

路网中基于预计算的跳跃式查询最近邻的算法

在空间网络数据库(SNDB)中,最近邻查询(NN)在基于位置的服务(LBS)中尤为关键.现有的查询处理方法大多依赖于路网的稀疏程度,其他处理方法如UNICONS等改进了该不足,但可能存在过计算的问题.针对后者,本文提出并证明了基于非交叉点路径中的预计算理论,同时基于该理论提出一种通用的基于SNDB的NN查询处理方法,该方法通过跳跃式查询交叉点的最近邻来降低预计算的代价.通过实验,验证了本文提出的处理方法在最近邻查询中的正确性和有效性,特别是在交叉点分布稀疏的路径上,性能优势尤为明显.     

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

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

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

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

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

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

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

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

自适应最近邻预测

研究了在最近邻预测中如何选择最近邻的阶数的问题。考虑了两种根据训练样本来确定近邻阶数ｋｎ与ｋｎ的方法。还证明了使用这些近邻阶数来进行预测可以达到最优预测以及进行了随机模拟计算,计算结果与文中理论相当吻合,并且揭示了最优近邻阶数ｋ０ｎ与样本量ｎ之间关系。     

范围最近邻查询方法研究

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

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

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

基于最优投影和动态阈值的最近邻搜索算法

作者在前人工作成果的基础上,提出并实现了一种基于最优投影和动态阈值调整的最近邻搜索算法DTA(Dynamic Threshold Algorithm);证明了最优投影线定理和投影邻域定理;并分析了DTA算法与SNN算法相比在算法性能上的优势.实验结果表明,当数据规模增大时,DTA算法的运行时间增加相对缓慢,在大规模数据集上DTA算法的运行时间可达传统算法的10%以下;DTA算法对阈值的变化不敏感,能适应不同分布的数据集合.     

一种新的最近邻聚类算法

在分析现有最近邻聚类算法所存在问题的基础上,提出了一种先利用均值规格化的思想来确定算法的初始半径,然后根据启发式规则修改聚类半径的新的最近邻聚类算法.同时,给出了聚类有效性函数对得到的聚类结果进行合理性判断.     

基于交叉覆盖算法的改进算法-最近邻交叉覆盖算法

交叉覆盖算法分类时着重在于两类的交界部分,混杂在另外一类中往往无助于提高分类器的效率,反而会增加分类器的计算负担。本文提出一种基于交叉覆盖算法的最近邻交叉覆盖算法(NN-ACA):对进行训练的原始样本数据进行预处理,删除这些不同类的最近邻点,得到精简后的样本集,再对该样本集使用交叉覆盖算法。通过实验和与SVM的比较,结果表明NN-ACA在一定的样本规模表现了速度和分类正确性上的优越性。     

基于最近邻法的短时交通流预测

针对交通流量变化存在周期性和随机性的特点，提出一种基于最近邻法的预测方法．着重介绍了状态向量构造、近邻范围确定和权重计算方法三方面的研究．根据流量与速度、占有率的关系，认为状态向量中不必考虑速度和占有率这两个交通参数；与传统最近邻法不同，近邻的个数不设为常量，而取决于所能搜索到的记录数；通常根据距离远近赋予权重的规则不可靠，而采用了等权重法．通过实际数据检验，预测误差低于7％．     

空间k近邻查询的新策略

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

多维近邻密度估计的Lp模强相合性

设X_1,…,X_n是i.i.d.的具有密度f(x)的d维随机变量。设S_(x,a(x))是中心在x且至少包含X_1,…,X_n中k_n个点的最小的球,则f_n(x)=R_n/(n|S_(x,a(x)|)是f(x)一个近邻估计。我们证明了:假如lim k_n/n=0,lim k_n/logn=∞以及flog~ f在任何有界Borel集上可积(或∫f'(x)dx<∞,p>1),则对任何有界Borel集A有(或p>1)。反之,如,则有∫f~p(x)dx<∞,lim n→∞k_n/n=0和lim n→∞k_n=∞。     

Nearest neighbor search algorithm forGBD tree spatial data structure

： This paper describes the nearest neighbor （NN） search algorithm on the GBD（generalized BD） tree. The GBD tree is a spatial data structure suitable for two- or three-dimensional data and has good performance characteristics with respect to the dynamic data environment. On GIS and CAD systems, the R-tree and its-successors have been used. In addition, the NN search algorithm is also proposed in an attempt to obtain good performance from the R-tree. On the other hand, the GBD tree is superior to the R-tree with respect to exact match retrieval, because the GBD tree has auxiliary data that uniquely determines the position of the object in the structure. The proposed NN search algorithm depends on the property of the GBD tree described above. The NN search algorithm on the GBD tree was studied and the performance thereof was evaluated through experiments.