Similarity Search Using Metric Trees

Bhavin Bhuta, Gautam Chauhan


The traditional method of comparing values against database might work well for small database but when the database size increases invariably then the efficiency takes a hit. For instance,image plagiarism detection software has large amount of images stored in the database, when we compare the hash values of input query image against that of database then the comparison may consume a good amount of time.  For this reason we introduce the concept of using metric trees which makes use metric space properties for indexing in databases.  In this paper, we have provided the working of various nearest neighbor search trees for speeding up this task. Various spatial partition and indexing techniques are explained in detail and their performance in real-time world is provided.

Full Text:



N. Katayama, S. Satoh. The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries. In Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data, Tucson, Arizona

Ch´avez, E., Navarro, G., Baeza-Yates, R., Marroqu´ın, J.L.: Searching in metric spaces. ACM Computing Surveys 33(3) (2001) 273–321

Burkhard, W.A. and Keller, R.M. Some Approaches to Best-Match File Searching", Communications of the ACM 16 (4), April 1973, 230-236.

Baeza-Yates, Ricardo, et al. "Proximity matching using fixed-queries trees."Combinatorial Pattern Matching. Springer Berlin Heidelberg, 1994.

Bozkaya, Tolga, and Meral Ozsoyoglu. "Distance-based indexing for high-dimensional metric spaces." ACM SIGMOD Record. Vol. 26. No. 2. ACM, 1997.

Chandran, Sharat. Introduction to kd-trees. University of Maryland Department of Computer Science.

Wald I, Havran,On building fast kd-trees for ray tracing, and on doing that in O(N log N), 2006

Tomas G. Rokicki, An Algorithm for Compressing Space and Time, 2006.


  • There are currently no refbacks.