并行度量空间相似性索引mvp

《并行度量空间相似性索引mvp》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、并行度量空间相似性索引MVP第1章绪言1.1研究目的和意义基于内容的相似性搜索(Similarityquery)是一种重要的信息检索类型，广泛存在于数据库和数据挖掘应用中。随着多媒体技术的发展和推广普及，基于复杂数据对象(空间数据、文本、图像、音频、视频、时空序列等)的海量数据库不断涌现，相似性搜索已经成为多媒体信息系统基于内容搜索的基本需求，其性能已经成为衡量多媒体系统查询功能的重要指标[2]，而在近年来蓬勃发展的计算生物学研究任务中，相似性搜索所占比例高达35%[3]。传统的相似性搜索是用多维索引（multi-dimensionalindexing）技术实现的。其基本思想是提取数据对象的

2、特征向量并将其映射到向量空间，然后用L族距离计算其相似性。例如针对一维数据（多维数据的一种）的索引技术的研究成果已经很成熟而且丰富多样，如二叉树排序树、平衡二叉树、B-树[4]、B+树[5]、RB-tree[6]树以及各种排序查找方法，虽然这些成果的最初目的是实现快速的精确查找，但是可以不加修改的应用于相似性搜索领域的研究。相应的在多维与高维数据的索引技术领域已有的研究成果有多种,并且同样可以用于相似性搜索领域，如Grid-File[7]、K-Dtree[8]、R-tree[9]以及应对高维数据的方法，如空间填充曲线[10]，VA-file[11]等，这些方法广泛应用于以地理信息系统为代表的

3、领域，取得了较好的效果。但是，随着新的数据类型层出不穷，向量空间索引的局限性也越来越明显地表现出来：(1)数据对象必须以特征向量来表示。(2)数据间的匹配必须用包括欧几里德距离在内的L族距离或其简单变形来衡量越来越多的数据类型不能满足以上两个条件。例如，用于图像类型的颜色直方图等的距离函数因为存在关联而不能用欧几里德距离来表示[8]，基因或者蛋白质序列的相似性基本是用海明距离(Hammingdistance)或者加权编辑距离(ental,PCA等。在所有的这些选择方法中，包含候选点与数据集合中其余数据对象之间的距离计算和比较，所以我们可以给每一个节点的支撑点选择划分操作到不同的索引构建线程中

4、并行执行；（2）数据划分：首先需要计算数据集合中每个对象与支撑点的距离，然后根据支撑点的距离值信息，将原始数据集中的对象按照距离值大小排序，所以我们给不同节点的数据划分操作一个执行任务，所有这些任务并行执行。.......第3章并行分布式MVP-tree设计和实现....433.1引言.....433.2MVP-tree多机并行构建思路....433.3MVP-tree多机并行查询思路....443.4并行分布式MVP-tree性能测试......453.4.1并行分布式MVP-tree构建性能实验测试......453.4.2并行分布式MVP-tree查询性能实验测试......483.5

5、本章小结.....50第4章总结与展望.......524.1论文工作总结.....524.2展望.....53第3章并行分布式MVP-tree设计和实现3.1引言目前，计算机相当的普及，用普通计算机组建集群的成本越来越低，而集群有单台计算机机系统无法相比的处理存储资源和可扩展性优势，这突出了在集群上实现基于度量空间索引的通用相似性搜索系统的并行化进而提高相似性检索性能的重要性，本章讲述了在由多台计算机组建的集群上实现MVP-tree的多机并行化方法。3.2MVP-tree多机并行构建思路在所有的分布式索引架构中，一般认为局部索引架构的性能最好，所以本论文研究采用局部索引架构构建多机并行的M

6、VP-tree相似性检索系统。图4.1展示的是本论文采用局部索引架构构建索引时的数据划分与构建过程。首先，用户在客户端提交原始数据，客户端根据用户访问的集群配置信息发送连接请求到集群中所有的计算节点以确认计算节点是否完好，然后发送索引构建参数（包括数据类型，支撑点数目，数据分块数目，索引名字等）到计算节点，参数发送完毕后根据完好节点的数目将用户提交的数据划分为相应数目的分块并发送到每一个计算节点上。计算节点接受到客户端发送的参数后启动与数据类型相应的数据接收过程，接受完数据并将数据存储到本地磁盘后开始执行索引构建任务，在索引构建过程中，根据用户指定的参数调用相应的串行构建或者多线程并行构建方

7、法。在索引构建完毕后，将构建索引的信息反馈到客户端，客户端在发送完参数和数据后进入睡眠等待状态，当计算节点返回索引构建信息后唤醒客户端，客户端汇总所有的索引构建信息后反馈到用户。...........总结首先，实现了通用数据管理分析系统UMAD，独立完成其相似性索引模块以及三个基础模块：支撑点模块、距离模块、数据对象模块。用目前最流行的MVP-tree作为相似性搜索系统模块GeDBIT的索引结构，并利用GeD