Journal
ACM TRANSACTIONS ON DATABASE SYSTEMS
Volume 28, Issue 4, Pages 517-580Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/958942.958948
Keywords
algorithms; theory; hiearchical metric data structures; similarity searching; distance-based indexing; nearest neighbor queries; range queries; ranking
Ask authors/readers for more resources
Similarity search is a very important operation in multimedia databases and other database applications involving complex objects, and involves finding objects in a data set S similar to a query object q, based on some similarity measure. In this article, we focus on methods for similarity search that make the general assumption that similarity is represented with a distance metric d. Existing methods for handling similarity search in this setting typically fall into one of two classes. The first directly indexes the objects based on distances (distance-based indexing), while the second is based on mapping to a vector space (mapping-based approach). The main part of this article is dedicated to a survey of distance-based indexing methods, but we also briefly outline how search occurs in mapping-based methods. We also present a general framework for performing search based on distances, and present algorithms for common types of queries that operate on an arbitrary search hierarchy. These algorithms can be applied on each of the methods presented, provided a suitable search hierarchy is defined.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available