基于广义超曲面树的相似性搜索算法

相似性搜索是数据挖掘的主要领域之一.它在数据库中检索出相似的数据,发现数据间的相似性.它可以应用于图像数据库、空间数据库和时间序列分析.对于欧氏空间(一种特殊的度量空间),相似性搜索算法中基于r-tree的方法,在低维时是高效的,当维数增加时,r-tree的方法将退化为线性扫描.该现象被称为维数灾难(dimensionalitycurse),主要原因是存在数据重复.当数据量很大且维数很高时,距离计算和i/o操作将非常费时.提出了度量空间上新的空间分割方法和索引结构rgh-tree,利用数据库的数据对象与很少几个固定参考对象的距离信息进行数据分割和分布,产生一个各节点没有数据重复的平衡树.另外,在rgh-tree的基础上提出了相应的相似性搜索算法,该算法具有较小的i/o代价和距离计算次数,平均复杂性近似为o(n0.58).解决了目前算法存在的一些问题.