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

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.