高维空间的K最近邻查询及连接问题研究

发布时间：2017-04-02 23:07

  本文关键词：高维空间的K最近邻查询及连接问题研究，由笔耕文化传播整理发布。

【摘要】：多年来，相当数量的研究工作集中在索引多维数据。相比于一维的情况下，设计多维存取方法是困难的，因为没有保留空间的局部性的总序。对于一个给定的多维空间数据库，一旦我们找到了一个总的序，我们可以利用简单的众所周知的一维的访问方法，例如B+树，可以达到良好的查询性能。一个映射的解决方案是通过空间填充曲线。空间填充曲线已被用于在各种领域，包括数据库系统，科学计算，地理信息系统和图像处理。它们给出点的坐标和在曲线上的点的一维的序列号之间的一一对应的关系。在大多数情况下，应用一直局限于Z曲线。然而，大多数以前的工作从理论上表明， Hilbert曲线相比其它曲线表现优异的数据聚类的性能。为了减少额外的寻道时间，它更有效地获取一组连续的磁盘块，而不是一个随机的分散设置。因此，这是可取的，在多维属性空间接近的物体也是在一维的磁盘空间接近。在一维序列磁盘块上的多维数据点的好的聚类性质可以减少对于范围查询所需的磁盘访问次数。本文基于空间填充曲线的Hilbert曲线，采用随机移位的方法解决K近邻查询和K近邻连接问题。在数据挖掘和数据分析中广泛用到K近邻查询和K近邻连接，尤其是K近邻连接是K近邻查询和连接操作的联合，比较复杂。MapReduce是在一簇计算节点之间利用并行机制处理大规模数据集的编程模型，由于其简单、灵活、容错性等优点在出现之后得到广泛流行，，现在商业和科学计算中广泛应用。我们也进一步讨论了MapReduce编程模型中K近邻连接问题的解决方案。本文对于数据挖据领域中的许多应用具有一定的借鉴意义。下面介绍本文的主要研究工作。 使用Hilbert曲线，可以将多维空间中的点映射到一维空间。对于一个查询点，可以将KNN搜索转换为该点的Hilbert值的范围搜索。Hilbert曲线不能始终保持空间局部性，它会导致最终的答案可能出现潜在错误。首先，我们使用随机变换方法，独立生成输入数据集的随机变换的版本，在每个随机变换的复本上，重复执行KNN搜索。在实验中只需要O（1）的转变，可以发现对于KNN查询实验中给出很好的近似质量。这种方法可以降低错误发生的概率。此外，Hilbert曲线表现优异的数据聚类性能，从而减少额外的寻道时间。最后，只创建一次随机转移表，可用于多次不同的查询。HKNN方法也是较好的选择。 K近邻连接是k近邻查询和连接操作的组合，K近邻连接作为一个基本操作，在许多数据挖掘中应用。近年来，研究人员对于高维数据的K近邻连接十分感兴趣。通过Hilbert曲线的方式，可以映射多维空间中的点到一维空间。然而，有时Hilbert曲线可能会存在潜在的错误，不能始终保持空间局部性。本文独立制作输入数据集的随机变换版本，通过随机移位操作，我们把数据变换几次。对于每个随机变换的副本，执行K近邻连接操作，我们更倾向于通过看每个转移列表的查询点的Hilbert的前驱和后继者，找到真正的最近邻。检查一个以上的前驱和后继者，可以提高近似的质量，取得更好的结果。虽然HKNNJ算法并没有zχ-kNNJ算法速度快，但是它具有较好的聚类性能和实际应用价值。因此它也是一个更好的选择。 在许多数据挖掘应用中广泛使用K近邻连接，它是一个基本操作，对一个数据集R中的每一条记录，它可以从另一个数据集S中找到它的k最近邻。这个操作的难度很大，执行起来也很耗时。随着维数的增加，对于大多数的数据集最近和最远的邻居的距离迅速下降很快，这也就是所谓的维数灾难。在大型集群中，MapReduce是一种有效的、故障容错、负载分布均衡的框架，在本文中，我们研究如何利用Hilbert曲线在MapReduce中实现K近邻连接操作。我们提出了一个三阶段的方法并考察了每个阶段。对于我们提出的算法，我们在Hadoop上实现，并在真实数据集上分析其性能特征。 本文最后，我们在MapReduce框架继续研究了KNN连接问题。解决K近邻连接的一种直接的方法就是采用块嵌套循环的方法。其主要思想是划分R和S到若干大小相等的块，对每一个可能的块（一个来自R，另一个来自S）被划分到一个桶。使用嵌套循环，在那个桶里能找到在本地块R的每个记录的在本地块S中的K最近邻。桶加载R树是高效的，在R树实现K近邻搜索也是高效的。在这基础上，我们为桶内局部的S块建立Hilbert R树索引，来帮助找到相同桶内的K近邻。大量的实验表明，我们提出的方法是有效的和可扩展的。
【关键词】：K近邻 Hilbert曲线 空间填充曲线 K近邻连接 MapReduce Hilbert R树
【学位授予单位】：吉林大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP311.13
【目录】：

• 摘要5-7
• Abstract7-13
• 第1章 绪论13-19
• 1.1 研究背景13-16
• 1.1.1 多维数据13
• 1.1.2 多维索引方法13-15
• 1.1.3 空间填充曲线方法15-16
• 1.2 研究意义16
• 1.3 本文主要工作16-17
• 1.4 本文组织结构17-19
• 第2章 基础知识19-33
• 2.1 空间多维曲线19-23
• 2.2 Hilbert 曲线23-29
• 2.2.1 Hilbert 曲线背景23
• 2.2.2 Hilbert 曲线相关工作23-28
• 2.2.3 Hilbert 曲线的绘制方式28-29
• 2.3 OpenStreetMap 数据集29-32
• 2.4 本章小结32-33
• 第3章 基于 Hilbert 曲线的 KNN 查询33-45
• 3.1 引言33
• 3.2 k 近邻定义及性质33-39
• 3.2.1 符号与特性33-35
• 3.2.2 形式化定义35-36
• 3.2.3 k 近邻性质36-39
• 3.3 利用随机位移的近似 KNN 算法39-41
• 3.4 实验结果与分析41-44
• 3.4.1 实验设置和数据集41
• 3.4.2 实验结果41-44
• 3.5 本章小结44-45
• 第4章 基于 Hilbert 曲线的 KNN 连接45-55
• 4.1 引言45
• 4.2 相关工作45-46
• 4.3 K 近邻连接定义及性质46
• 4.4 蛮力算法46-48
• 4.5 随机变换处理 KNN 连接48-50
• 4.5.1 随机变换48-49
• 4.5.2 KNN 连接的过程49-50
• 4.6 实验结果与分析50-53
• 4.6.1 实验环境和数据集50-51
• 4.6.2 实验结果51-53
• 4.7 本章小结53-55
• 第5章 基于 MapReduce 的 KNN 连接55-65
• 5.1 引言55-56
• 5.2 相关工作56
• 5.3 MapReduce 框架56-59
• 5.4 KNN 连接过程59-61
• 5.4.1 划分值59-60
• 5.4.2 本地的 KNN60-61
• 5.4.3 全局 KNN61
• 5.5 实验结果与分析61-63
• 5.5.1 实验设置和数据集61
• 5.5.2 实验结果61-63
• 5.6 本章小结63-65
• 第6章 基于 Hilbert R 树的 KNN 连接65-75
• 6.1 引言65
• 6.2 相关工作65-66
• 6.3 Hilbert R 树66-67
• 6.4 并行块嵌套循环的 KNN 连接67-69
• 6.5 基于 Hilbert R 树的 KNN 连接69-70
• 6.6 实验结果与分析70-73
• 6.6.1 实验设置和数据集70
• 6.6.2 实验结果70-73
• 6.7 本章小结73-75
• 第7章 结论与展望75-77
• 7.1 本文的工作75-76
• 7.2 未来工作展望76-77
• 参考文献77-85
• 作者简介及在学期间所取得的科研成果85-86
• 致谢86

【参考文献】

中国期刊全文数据库 前10条

1 徐红波;郝忠孝;;一种基于Z曲线近似k-最近对查询算法[J];计算机研究与发展;2008年02期

2 崔杰;李陶深;兰红星;;基于Hadoop的海量数据存储平台设计与开发[J];计算机研究与发展;2012年S1期

3 徐红波;郝忠孝;;基于空间填充曲线网格划分的最近邻查询算法[J];计算机科学;2010年01期

4 徐红波;郝忠孝;;基于Hilbert曲线的高维k-最近对查询算法[J];计算机工程;2008年02期

5 徐红波;郝忠孝;;基于Hilbert曲线的近似k-最近邻查询算法[J];计算机工程;2008年12期

6 何小苑;闵华清;;基于聚类的Hilbert R-树空间索引算法[J];计算机工程;2009年09期

7 徐红波;;空间填充曲线映射算法研究[J];科技信息(科学教研);2007年35期

8 刘俊岭;孙焕良;;多维度量空间中发现相互kNN(英文)[J];计算机科学与探索;2010年10期

9 杨景涛;吴立德;;带聚类的Hilbert R-树建树算法[J];模式识别与人工智能;2001年01期

10 林伟伟;刘波;;基于动态带宽分配的Hadoop数据负载均衡方法[J];华南理工大学学报(自然科学版);2012年09期

中国博士学位论文全文数据库 前2条

1 徐红波;基于空间填充曲线高维空间查询算法研究[D];哈尔滨理工大学;2010年

2 袁培森;基于LSH的Web数据相似性查询研究[D];复旦大学;2011年

  本文关键词：高维空间的K最近邻查询及连接问题研究，由笔耕文化传播整理发布。

本文编号：283291