Using the triangle inequality to reduce the number of comparisons required for similarity-based retrieval

Julio E. Barros; James C. French; Worthy N. Martin; Patrick M. Kelly; T. Michael Cannon

doi:10.1117/12.234778

13 March 1996 Using the triangle inequality to reduce the number of comparisons required for similarity-based retrieval

Julio E. Barros, James C. French, Worthy N. Martin, Patrick M. Kelly, T. Michael Cannon

Proceedings Volume 2670, Storage and Retrieval for Still Image and Video Databases IV; (1996) https://doi.org/10.1117/12.234778
Event: Electronic Imaging: Science and Technology, 1996, San Jose, CA, United States

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.

Citation Download Citation

Julio E. Barros, James C. French, Worthy N. Martin, Patrick M. Kelly, and T. Michael Cannon "Using the triangle inequality to reduce the number of comparisons required for similarity-based retrieval", Proc. SPIE 2670, Storage and Retrieval for Still Image and Video Databases IV, (13 March 1996); https://doi.org/10.1117/12.234778

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available