超平面树:度量空间中相似性搜索的索引结构

Haperplane Tree: A Structure of Indexing Metric Spaces for Similarity Search Queries

相似性搜索是从数据库中检索出同给定数据对象相似的数据对象 ,已有的基于R tree的相似性搜索 ,当搜索空间的维的个数较小时效率较高 ,但当搜索空间的维的个数较大时则效率很低 针对此问题 ,提出了新的度量空间分割方法和索引结构 pgh tree,利用数据对象与很少几个固定参考对象的距离之差进行数据分割和索引 ,产生一个平衡的索引树 在此基础上 ,提出了新的算法 ,利用查询数据对象与固定参考对象的距离之差过滤掉大部分的不相关数据 ,具有较小的I/O代价和距离计算复杂性 ,平均复杂性为θ(n0 58) ,是目前复杂性最小的相似性搜索算法 另外还讨论了基于 pgh tree的最近相邻点搜索策略 .

Similarity search queries find proximity objects in database with a fixed object. R-tree based methods of existing similarity search queries have high efficiency for low dimension, but have low efficiency for high dimension. To solve this problem, pgh-tree is proposed, which is a new indexing metric space. Using metrics information of object to only few fixed objects, indexing structure and partitioning metric spaces are made to create an indexing tree with balance. An algorithm suitable for similarity search queries is presented on metric spaces under the indexing structure. The algorithm overcomes the shortcomings of the exiting algorithms. It uses difference of distance between the two reference points. It reduces the number of passes of scanning database so that I/O overhead is reduced significantly. Average complex of it is θ(n 0.58). Analysis and experimental results show that the algorithm is more efficient than others. In addition, a strategy of K-nearest neighborhood search is also discussed under pgh-tree.