• date: 2021-04-10
  • author: 李建中 张兆功
  • keywords: 相似性搜索 度量空间 数据库 数据挖掘
背景

图像数据库、遗传学、信息检索、数据挖掘中的时间序列分析、文本匹配、空间数据库等数据库应用都存在相似性搜索问题(similarity search). 还有一类查询是给定一个数据对象，寻找距离该对象最近的K个数据对象，即所谓的KNN查询(K-nearest neighborhood search).

数据对象的相似性通过应用领域中的距离函数计算得到。目前的相似性搜索算法可以分为以下四类：

  1. 基于距离变换算法：首先将数据对象映射到欧几里得空间中，利用低维欧几里得空间中的高效查询技术完成相似性搜索。这类搜索只适用于数据间具有较强相关性的数据集合。
  2. 基于空间分割算法：这类算法将整个数据空间分割为规则或不规则的子空间。如R-tree等，当维数较低时较为高效，维数增加时退化为线性扫描。
  3. 基于曲线添充算法：将高维空间分割为规则的cell，对cell进行编码或索引，从而映射到一维空间。但相似搜索结果存在遗漏问题。
  4. 基于距离索引算法：通过对数据对象之间的距离信息进行索引。mvp-tree, gh-tree, gh-tree不是平衡树，平衡化mvp-tree是平衡树，但区域不对称。
目标
  1. 避免数据重复问题，保证树的平衡性
  2. 如何减少距离计算次数
  3. 如何减少I/O操作开销
  4. 保证可扩展性。当数据量变大且维数增加时，系统效率不减，解决维数灾难问题。
    本文综合考虑目标1、2，深入研究距离索引办法，再gh-tree和M-tree的基础上提出新的数据存储结构pgh-tree以及基于该数据结构的相似性搜算法，解决上述四个问题。