基于MapReduce快速kNN Join方法

kNN连接是空间数据库领域里一个基本而又重要的问题,被广泛地应用于多个其他领域.它对提高众多实际应用的性能有着重要意义.随着目前参加kNN连接的数据集的增大和要求的响应时间的缩短(尤其在一些应急环境中),作者实际上对kNN连接的效率要求更高.然而,目前的方法大多基于单个进程或者单台机器,并不具有很好的伸缩性.为了解决这个问题,作者引入了map-reduce框架来运行kNN join并提出了两种新的方法:基于map-reduce的分布式网格概略化kNN join(DSGMP-J)和基于map-reduce的voronoi diagram下kNN join(VDMP-J).并把它们和最新的方法 H-BNLJ进行了实验对比.实验结果证明了作者提出的DSGMP-J和VDMP-J方法具有较优的伸缩性.

pgi-distance:一种高效的并行KNN-join处理方法

KNN-join是一种新近才提出的操作,它在数据挖掘中有着广泛的应用.利用KNN-join的"一次一个集合"的性质,一些数据挖掘任务,例如分类、例外挖掘和聚类等,就会更加容易地进行.MuX和Goreder则是两种专为KNN-join设计的算法.为了综合利用这两种方法的优点,一种新的KNN-join并行处理方法——pgi-distance(parallel grid index-distance)——被提了出来.pgi-distance使用双层结构,可以对I/O和CPU进行同时优化;基于距离的索引能够让它更好地适应数据维度和分布的变化.由于采用的是各DBMS厂商广泛支持的B+树索引,这让pgi-distance得以成为一种更为实用的KNN-join处理方法.在合成数据集和真实数据集上的测试也表明pgi-distance是实用的和高效的.

一种基于主存Δ-tree的高维数据KNN连接算法

KNN连接作为数据挖掘的基元,可以用来大幅度提高相似搜索、数据分析和数据挖掘的速度.到目前为止,对KNN连接的研究主要在基于磁盘系统的背景下进行,假设数据库太大以至于不能装入主存.随着RAM越来越大,价格也越来越低廉,这种假设逐渐受到挑战.因此,有必要重新对基于主存的KNN连接进行研究.在高效主存索引的基础上,采用编码解码、自底向上、深度优先遍历和剪枝等技术提出了一种新的KNN连接算法Δ-tree-KNN-Join.该算法解决了KNN连接中确定搜索半径困难的问题,提高了连接效率.在真实数据和合成聚类数据上进行了实验,结果显示Δ-tree-KNN-Join是一种有效的主存KNN连接算法.

高维主存kNN连接索引结构的核心算法

kNN(k最近邻)连接是高维数据库中的一种重要但代价昂贵的基本操作。随着RAM容量越来越大且价格逐渐低廉,更多的数据集能够被装入主存。如何实现快速主存kNN连接,引起人们的关注。索引Δ-tree-R和-Δtree-S是根据kNN连接的特点专门为主存kNN连接设计的索引。结合编码、节点中心重合技术,给出了构建Δ-tree-R和-Δtree-S的核心算法及相关证明,实验表明,基于该索引的主存kNN连接算法-Δtree-KNN-Join明显优于目前已存在的可用于主存的kNN连接算法Gorder。

基于数据流的k-近邻连接算法

k-近邻连接查询是空间数据库中一种常用的操作,该查询处理过程涉及连接和最近邻查询两个复杂操作。传统的集中式k-近邻连接查询算法已不能适应当前呈爆炸式增长的数据规模,设计分布式k-近邻连接查询算法成为了目前亟需解决的问题。现有的分布式k-近邻连接查询算法都包括了多轮串行的MapReduce任务,而每个MapReduce任务均需要读写分布式文件系统,导致MapReduce不能有效表达多个任务之间的依赖关系,因此算法效率低下。首先提出了一种基于数据流的计算框架,该框架建立在MapReduce之上,将数据处理过程按照数据流图建模。在该框架基础上,提出了一种高效的k-近邻连接算法,它利用空间填充曲线将多维数据映射为一维数据,从而将k-近邻连接查询转化为一维范围查询。实验结果表明,该算法的可扩展性较高,且效率比现有算法更优。

大数据相似性连接查询技术研究进展

为了深入理解和全面把握大数据相似性连接查询技术的研究进展,更好地促进其在图片聚类、实体解析、相似文档检测、相似轨迹检索等领域的广泛应用,对大数据相似性连接查询技术相关研究工作进行了深入调研和分析。首先对相似性连接查询的基本概念进行了介绍,然后分别对集合、向量、空间数据、概率数据、字符串等不同类型大数据的相似性连接查询相关研究工作进行了深入研究,对其优缺点进行了分析和总结。最后,指出了大数据相似性连接查询面临的若干挑战性问题及未来的研究重点。