DocumentCode :
1804791
Title :
Indexing Methods for Similarity Searching
Author :
Samet, Hanan
Author_Institution :
Dept. of Comput. Sci., Maryland Univ., College Park, MD
fYear :
2007
fDate :
24-28 Sept. 2007
Abstract :
An overview is given of the various techniques and issues involved in providing indexing support for similarity searching. Similarity searching is a crucial part of retrieval in multimedia databases used for applications such as pattern recognition, image databases, and content-based retrieval. It involves finding objects in a data set S that are similar to a query object q based on some distance measure d which is usually a distance metric. The search process is usually achieved by means of nearest neighbor finding. Existing methods for handling similarity search in this setting fall into one of two classes. The first is based on mapping to a vector space. The vector space is usually of high dimension which requires special handling due to the fact indexing methods do not discriminate well in such spaces. In particular, the query regions often overlap all of the blocks that result from the decomposition of the underlying space. This has led to some special solutions that make use of a sequential scan. An alternative is to use dimension reduction to find a mapping from a high-dimensional space into a low-dimensional space by finding the most discriminating dimensions and then index the data using one of a number of different data structures such as k-d trees, R-trees, quadtrees, etc. The second directly indexes the objects based on distances making use of data structures such as the vp-tree, M-tree, etc.
Keywords :
data structures; database indexing; multimedia databases; content-based retrieval; data structures; image database; indexing methods; multimedia database; pattern recognition; similarity searching; Content based retrieval; Image databases; Image retrieval; Indexing; Information retrieval; Multimedia databases; Nearest neighbor searches; Pattern recognition; Q measurement; Vegetation mapping;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Current Trends in Computer Science, 2007. ENC 2007. Eighth Mexican International Conference on
Conference_Location :
Michoacan
Print_ISBN :
978-0-7695-2899-1
Type :
conf
DOI :
10.1109/ENC.2007.9
Filename :
4351415
Link To Document :
بازگشت