Unified framework for fast exact and approximate search in dissimilarity spaces
Author:
Open Access
- 1 November 2007
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 32 (4)
Abstract
In multimedia systems we usually need to retrieve database (DB) objects based on their similarity to a query object, while the similarity assessment is provided by a measure which defines a (dis)similarity score for every pair of DB objects. In most existing applications, the similarity measure is required to be a metric, where the triangle inequality is utilized to speed up the search for relevant objects by use of metric access methods (MAMs), for example, the M-tree. A recent research has shown, however, that nonmetric measures are more appropriate for similarity modeling due to their robustness and ease to model a made-to-measure similarity. Unfortunately, due to the lack of triangle inequality, the nonmetric measures cannot be directly utilized by MAMs. From another point of view, some sophisticated similarity measures could be available in a black-box nonanalytic form (e.g., as an algorithm or even a hardware device), where no information about their topological properties is provided, so we have to consider them as nonmetric measures as well. From yet another point of view, the concept of similarity measuring itself is inherently imprecise and we often prefer fast but approximate retrieval over an exact but slower one. To date, the mentioned aspects of similarity retrieval have been solved separately, that is, exact versus approximate search or metric versus nonmetric search. In this article we introduce a similarity retrieval framework which incorporates both of the aspects into a single unified model. Based on the framework, we show that for any dissimilarity measure (either a metric or nonmetric) we are able to change the “amount” of triangle inequality, and so obtain an approximate or full metric which can be used for MAM-based retrieval. Due to the varying “amount” of triangle inequality, the measure is modified in a way suitable for either an exact but slower or an approximate but faster retrieval. Additionally, we introduce the TriGen algorithm aimed at constructing the desired modification of any black-box distance automatically, using just a small fraction of the database.Keywords
This publication has 49 references indexed in Scilit:
- Feature-based similarity search in 3D object databasesACM Computing Surveys, 2005
- Properties of embedding methods for similarity searching in metric spacesIEEE Transactions on Pattern Analysis and Machine Intelligence, 2003
- Region proximity in metric spaces and its use for approximate similarity searchACM Transactions on Information Systems, 2003
- Searching in metric spaces with user-defined and approximate distancesACM Transactions on Database Systems, 2002
- Clustering for approximate similarity search in high-dimensional spacesIEEE Transactions on Knowledge and Data Engineering, 2002
- Classification with nonmetric distances: image retrieval and class representationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- Indexing large metric spaces for similarity search queriesACM Transactions on Database Systems, 1999
- Approximate similarity retrieval with M-treesThe VLDB Journal, 1998
- Fast nearest-neighbor search in dissimilarity spacesIEEE Transactions on Pattern Analysis and Machine Intelligence, 1993
- Hardware algorithms for determining similarity between two stringsIEEE Transactions on Computers, 1989