基于支撑点空间模型的度量空间索引研究

度量空间索引把数据抽象成度量空间的点，利用用户定义距离函数的三角不等性来实现高速相似性搜索。它不用把数据转换成坐标系中的点，距离函数也不限于欧氏距离，高度的普遍适用性使其在多媒体和计算生物等领域有着广泛的应用前景。多年来，国内外学者设计了一批索引方法，并取得了一定的应用成果。然而，坐标的缺失导致理论研究分析难以进行，目前大部分的方法是启发式的。各种方法自成一家，无法进行统一的分析、比较和评测，整个领域缺乏理论基础，进展缓慢。.项目负责人近期总结提出的支撑点空间模型把度量空间索引转移到具有坐标的向量空间中。以此为基础，本项目将运用数学工具深入研究度量空间索引的主要问题，如支撑点选取和数据划分等，完善支撑点空间模型，建立统一化索引结构，对现有方法做到知其所以然，提供其分析、对比、改进和预测平台，明确度量空间索引和高维向量空间索引的关系，从而建立度量空间索引理论框架，为本领域研究打开新的局面。

度量空间索引把多种数据抽象成度量空间的点，利用用户定义距离函数的三角不等性来实现高速相似性搜索，具有高度的普遍适用性。本项目以支撑点空间模型为基础，重点研究支撑点选取和数据划分等问题，完善支撑点空间模型，建立统一化索引结构。. 项目进展顺利，各项研究认为均已如期完成。在度量空间索引的理论框架方面，我们提出了大数据抽象（big data abstraction）概念，并设计了一个基于度量空间的大数据并行计算模型；在支撑点选择方面，提出一个距离敏感的支撑点选取目标函数和一种估算数据内在维度的方法，设计多个基于统计方法的支撑点选取算法和一个基于抽样的增量式支撑点选取算法框架；在数据划分方面，提出了CGHT树，将三大索引流派统一起来并进行了性能分析，对VP树和VP森林的对比研究，设计一个三路数据划分算法，并提出逐个支撑点的数据划分算法框架；在应用方面，设计实现UMAD软件包，进行了度量空间异常点检测和度量空间分类研究，实现了蛋白质质谱相似性搜索软件MSIndex，并面向时序医疗数据进行了度量空间索引应用。项目成果包括学术论文23篇，其中CCF-A类论文5篇，JCR-1区论文4篇；获批软件著作权8项，有5项专利进人实审；培养硕士研究生7人，博士研究生1人，4名本科生被美国名校录取；举办学术会议2次，参加国际学术会议5次。. 目前大数据的研究基本集中于其大量和快速的挑战，而针对多样性挑战的研究较少。度量空间方法把多种类型的数据抽象到统一的度量空间，针对度量空间的特性构造通用的数据管理分析系统，是应对大数据多样性挑战的有效手段之一。本项目研究完善了度量空间索引的理论框架，并对支撑点选择和数据划分两个基本问题进入了深入研究，为度量空间数据管理分析研究奠定了良好的基础。