Share Email Print

Proceedings Paper

Similarity indexing: algorithms and performance
Author(s): David A. White; Ramesh C. Jain
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

Efficient indexing support is essential to allow content-based image and video databases using similarity-based retrieval to scale to large databases (tens of thousands up to millions of images). In this paper, we take an in depth look at this problem. One of the major difficulties in solving this problem is the high dimension (6-100) of the feature vectors that are used to represent objects. We provide an overview of the work in computational geometry on this problem and highlight the results we found are most useful in practice, including the use of approximate nearest neighbor algorithms. We also present a variant of the optimized k-d tree we call the VAM k-d tree, and provide algorithms to create an optimized R-tree we call the VAMSplit R-tree. We found that the VAMSplit R-tree provided better overall performance than all competing structures we tested for main memory and secondary memory applications. We observed large improvements in performance relative to the R*-tree and SS-tree in secondary memory applications, and modest improvements relative to optimized k-d tree variants.

Paper Details

Date Published: 13 March 1996
PDF: 12 pages
Proc. SPIE 2670, Storage and Retrieval for Still Image and Video Databases IV, (13 March 1996); doi: 10.1117/12.234810
Show Author Affiliations
David A. White, Univ. of California/San Diego (United States)
Ramesh C. Jain, Univ. of California/San Diego (United States)

Published in SPIE Proceedings Vol. 2670:
Storage and Retrieval for Still Image and Video Databases IV
Ishwar K. Sethi; Ramesh C. Jain, Editor(s)

© SPIE. Terms of Use
Back to Top