Share Email Print

Proceedings Paper

Using the triangle inequality to reduce the number of comparisons required for similarity-based retrieval
Author(s): Julio E. Barros; James C. French; Worthy N. Martin; Patrick M. Kelly; T. Michael Cannon
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

Dissimilarity measures, the basis of similarity-based retrieval, can be viewed as a distance and a similarity-based search as a nearest neighbor search. Though there has been extensive research on data structures and search methods to support nearest-neighbor searching, these indexing and dimension-reduction methods are generally not applicable to non-coordinate data and non-Euclidean distance measures. In this paper we reexamine and extend previous work of other researchers on best match searching based on the triangle inequality. These methods can be used to organize both non-coordinate data and non-Euclidean metric similarity measures. The effectiveness of the indexes depends on the actual dimensionality of the feature set, data, and similarity metric used. We show that these methods provide significant performance improvements and may be of practical value in real-world databases.

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.234778
Show Author Affiliations
Julio E. Barros, Univ. of Virginia and Los Alamos National Lab. (United States)
James C. French, Univ. of Virginia (United States)
Worthy N. Martin, Univ. of Virginia (United States)
Patrick M. Kelly, Los Alamos National Lab. (United States)
T. Michael Cannon, Los Alamos National Lab. (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
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?