基于Δtree的自底向上的深度递归KNN查询算法*

Δ-tree是一种新提出的多层索引结构,能够加速主存环境中的高维查询。在该高效主存索引的基础上,提出了改进的KNN搜索算法BU_DF_knn_Search,该算法通过定位技术、自底向上、深度优先遍历及过滤策略设计而成,解决了KNN查询中搜索半径未知的难题。在高维数据集上进行了实验,结果显示算法BU_DF_knn_Search比Δ-tree已有的KNN搜索算法具有更高的效率。     

基于A-tree的递归深度优先KNN查询算法

基于△-tree提出一种用于高维数据的主存K最近邻(KNN)查询算法.该算法利用递归调用方法深度优先遍历A-tree,找到距离查询点较近的叶子节点,并选择其中较优的KNN候选点进行查询,从而缩小修剪距离、提高查询速度.实验结果表明,与已有算法相比,该算法具有更高的查询效率.     

深度优先遍历Δ-tree的非递归KNN查询

kNN查询是高维数据库中最重要的操作之一,尽管它在数据库研究中得到了极大的关注,但很少有关于主存数据库kNN查询的工作。充分利用kNN查询自身的特点,基于高效的主存索引Δ-tree设计了一种新的kNN查询算法NR_DF_knn_Search,该算法采用非递归方式深度优先搜索Δ-tree中距离查询点较近的叶子节点,能够快速找到较优的kNN候选,更新修剪距离,加大剪枝力度,缩小搜索空间,从而提高kNN查询效率。通过实验对该算法进行了估价,结果证明该算法是有效的。     

高维主存的反向K最近邻查询及连接

对高维主存的反向K最近邻(KNN)查询进行研究,提出一种Δ-RdKNN-tree索引结构。通过在该索引结构上进行主存KNN自连接,预处理数据集中点的KNN距离信息。将这些距离扩展到索引的各层节点中,基于该索引设计高维主存的反向KNN查询算法以及反向KNN连接算法。分析结果表明,该算法在高维空间中是有效的。     

基于△-tree的自底向上的深度递归KNN查询算法

△-tree是一种新提出的多层索引结构,能够加速主存环境中的高维查询.在该高效主存索引的基础上,提出了改进的KNN搜索算法BU_DF_knn_Search,该算法通过定位技术、自底向上、深度优先遍历及过滤策略设计而成,解决了KNN查询中搜索半径未知的难题.在高维数据集上进行了实验,结果显示算法BU_DF_knn_Search比△-tree已有的KNN搜索算法具有更高的效率.     

基于Δ-tree的高维数据相似连接算法

为了解决主存中高维数据相似连接问题,基于高效索引Δ-tree提出了连接两个不同数据集的主存相似连接算法Δ-tree-join*.该算法采用自顶向下的模式,充分利用Δ-tree的特性,使用较少的维数计算聚类之间的距离及数据点与聚类之间的距离,通过该距离过滤掉不必要的节点和数据点,减少计算量,提高连接效率.实验结果表明,△...     

基于Δ-tree的高维数据相似连接算法

为了解决主存中高维数据相似连接问题,基于高效索引Δ-tree提出了连接两个不同数据集的主存相似连接算法Δ-tree-join*。该算法采用自顶向下的模式,充分利用Δ-tree的特性,使用较少的维数计算聚类之间的距离及数据点与聚类之间的距离,通过该距离过滤掉不必要的节点和数据点,减少计算量,提高连接效率。实验结果表明,Δ-tree-join*是一种更适合主存的相似连接算法,比目前这方面最先进的算法EGO及EGO*具有更优的性能。     

深度优先遍历△-tree的非递归KNN查询

kNN查询是高维数据库中最重要的操作之一,尽管它在数据库研究中得到了极大的关注,但很少有关于主存数据库kNN查询的工作.充分利用kNN查询自身的特点,基于高效的主存索引△-tree设计了一种新的kNN查询算法NR-DF-knn-Search,该算法采用非递归方式深度优先搜索△-tree中距离查询点较近的叶子节点,能够快速找到较优的kNN候选,更新修剪距离,加大剪枝力度,缩小搜索空间,从而提高kNN查询效率.通过实验对该算法进行了估价,结果证明该算法是有效的.     

一种在KNN查询处理中预估剪枝阈值的方法

KNN查询是多媒体数据库管理系统中最具代表性的查询方式之一。与范围查询不同,KNN查询过程中缺乏固定的剪枝阈值。为达到剪枝的目的KNN算法使用保守的KNN距离剪枝,通常把到当前访问过的第K个最近点的距离作为剪枝阈值。传统的KNN查询处理算法在找到K个候选查询结果之前无法生成剪枝阈值,使得在此期间所有访问到的节点都被置入待访问节点队列。文中提出了在KNN查询处理中预估剪枝阈值的方法,该方法在找到K个候选查询结果前通过分析当前所访问过的页区域来预估剪枝阈值,试验表明使用预估剪枝阈值进行剪枝可有效缩短待访问节点队列的长度。     

一种在KNN查询处理中预估剪枝阈值的方法

KNN查询是多媒体数据库管理系统中最具代表性的查询方式之一。与范围查询不同，KNN查询过程中缺乏固定的剪枝阈值。为达到剪枝的目的KNN算法使用保守的KNN距离剪枝，通常把到当前访问过的第K个最近点的距离作为剪枝阈值。传统的KNN查询处理算法在找到K个候选查询结果之前无法生成剪枝阈值，使得在此期间所有访问到的节点都被置入待访问节点队列。文中提出了在KNN查询处理中预估剪枝阈值的方法，该方法在找到K个候选查询结果前通过分析当前所访问过的页区域来预估剪枝阈值，试验表明使用预估剪枝阈值进行剪枝可有效缩短待访问节点队列的长度。     

基于范围查询的移动对象快照KNN查询算法

提出一种基于范围查询的移动对象快照K最近邻(KNN)查询算法——SKNN。预估包含结果集的子空间,使用该子空间作为范围,计算查询点的KNN兴趣点,以降低I/O成本。引入移动数据库中的缓存技术,缩短查询的平均响应时间。实验结果表明,当移动对象的规模较大时,SKNN算法的性能较优。     

一种基于加权KNN的大数据集下离群检测算法

传统KNN算法是在基于距离的离群检测算法的基础上提出的一种在大数据集下进行离群点挖掘的算法, 然而KNN算法只以最近的第k个部居的距离作为判断是否是离群点的标准有时也失准确性。给出了一种在大数据 集下基于KNN的离群点检测算法,即在传统KNN方法的基础上为每个数据点增加了权重,权重值为与最近的k个 邻居的平均距离,离群点为那些与第k个部居的距离最大且相同条件下权重最大的点。算法能提高离群点检测的准 确性,通过实验验证了算法的可行性,并与传统KNN算法的性能进行了对比。     

一种基于加权KNN的大数据集下离群检测算法

传统KNN算法是在基于距离的离群检测算法的基础上提出的一种在大数据集下进行离群点挖掘的算法,然而KNN算法只以最近的第k个邻居的距离作为判断是否是离群点的标准有时也失准确性.给出了一种在大数据集下基于KNN的离群点检测算法,即在传统KNN方法的基础上为每个数据点增加了权重,权重值为与最近的k个邻居的平均距离,离群点为那些与第k个邻居的距离最大且相同条件下权重最大的点.算法能提高离群点检测的准确性,通过实验验证了算法的可行性,并与传统KNN算法的性能进行了对比.     

时态约束下的频繁模式挖掘算法

时态数据是一类重要的数据信息.利用数据中包含的时间属性可以形象描述数据中潜在的变化规律,预测将来可能的发展趋势.本文提出一种时态频繁模式挖掘算法(TemFP).根据现有的时态查询函数,该算法给出一种用于存储频繁模式时态属性的双树结构(DB+-tree).利用包含DB+-tree的时态频繁模式树,使用户定义的时态规则快速查询成为可能.实验结果表明该算法是有效和可扩展的.     

KNNOI在缺失数据补值中的应用

KNN是常用有效的分类算法,在数据分类及故障诊断中有很多的应用,同时KNN也被应用于缺失数据的补值算法中。传统的KNN方法通过计算数据点之间的欧式距离并排序,得到K个距离最近的点,通过K个点的数值对缺失值进行补值计算。但在此过程中,距离的计算受到变量数据分布的特点及不同变量数据分布不一致等的影响,从而影响补值结果。本论文提出了一种基于次序的KNN计算方法 KNNOI(KNN based on Order Imputation),通过对变量进行排序,应用变量的排序序号差计算数据点的距离,代替原来的距离计算方法。将此算法应用于数据补值,研究了排序方式及参数的选择对补值的影响,与传统的KNN算法进行了比较。实验结果表明,基于排序的算法补值得到的结果要优于传统的KNN方法。     

基于贪心策略的最近邻Top-k偏好查询方法

传统Top-[k]空间关键字查询忽略了兴趣对象周围的基础设施属性对于用户偏好的影响,针对该问题,研究了基于影响区域约束关系的Top-[k]空间关键字偏好查询问题,设计了一种基于贪心策略的最近邻算法GS-NNA（Greedy Strategy based Nearest Neighbor Algorithm）。该算法采用R*-tree和倒排文件两种索引结构,结合贪心思想和最近邻算法,每次选择分值最高的兴趣对象作为候选结果集,并利用阈值判定条件对R*-tree进行剪枝。实验结果表明,GS-NNA算法与现有相关算法相比,有效提高了查询效率。     

基于双层网格索引的移动对象KNN查询算法

移动对象KNN查询技术是当前数据库领域中的一个研究热点.实际的移动对象的应用多数存在由对象速度变化引起的动态负载问题,而现有KNN查询算法较少考虑该问题.提出了一种基于双层网格索引的移动对象KNN查询算法.算法采用粗细双层网格将不同速度的移动对象分开索引,对于速度快的对象在粗网格中索引,速度慢的在细网格中索引,减少了索引的更新次数,提高了KNN查询的效率.针对真实数据集实验结果表明,基于双层网格索引结构的移动对象KNN查询算法与以往采用单层网格的算法相比,能有效地解决动态负载问题.     

基于Voronoi划分的位置数据KNN查询处理方法

K最近邻(KNN)查询是空间数据查询研究的重要内容。目前的KNN查询方法在处理大规模的位置数据时,存在着更新和查找失衡的问题,导致查询效率较低。因此,提出基于Voronoi划分的位置数据KNN查询处理方法。首先,创建了一个二级空间索引结构——VRI,包含VHash和VR树两部分。一级索引结构VHash表示Voronoi图的直邻;二级索引结构VR树,按照各Voronoi单元所在的最小矩形区域的重叠面积,自下而上地生成对应的R树。其次,基于VRI索引结构提出了位置数据的KNN查询算法及动态维护算法,在KNN查询方法中,采用VR树进行定位,VHash查找K近邻,能够有效地对查询点定位,查找速度快。再次,针对数据更新的情况,索引结构也能够及时更新,在更新的时间段内,对于位置数据随时间变化的KNN查询,提出了利用记录表进行有效查询的方法。最后,实验表明,提出的基于Voronoi划分的空间索引结构和其对应的KNN查询算法均具有较好的性能和适应性。     

Finsler度量在KNN算法中的应用研究

为了克服传统K近邻(Knearest neighbor,KNN)算法在距离定义上的不足,提出了一种基于Finsler度量的KNN算法(Finsler metric KNN,FMKNN)。该算法将样本点间的距离定义为Finsler度量,保留了样本属性对样本间距离度量的影响,使得样本点间的距离度量更具一般性。在手写体数据集上的实验表明,FMKNN算法的分类准确率高于传统KNN算法。     

利用分区和距离实现高维空间快速KNN查询

在高维空间KNN查询算法中,近似向量和一维转换表示法能有效克服维数灾难,结合这两种思想,提出一种基于区位码和距离的索引结构(BD)以实现快速KNN查询.根据高维空间向量分布特点,合理分区使得大量分布在空间表面的点尽可能地划分到不同的分区中,提高检索剪枝效率.引入区位码概念和转换函数,将高维向量近似表示并转换为一维数值形式,组织成B 树索引.利用快速KNN查询算法,实现两层过滤,缩小搜索范围,降低树搜索代价.采用模拟数据和真实数据,大量实验验证了BD比其他同类索引具有更高的检索效率.