Techniques and data structures for efficient multimedia retrieval based on similarity

Abstract—As more and more information is captured and stored in the digital form, many techniques and systems have been devel-oped for indexing and retrieval of text documents, audio, images, and video. The retrieval is normally based on similarities between extracted feature vectors of the query and stored items. Feature vectors are usually multidimensional. When the number of stored objects and/or the number of dimensions of the feature vectors are large, it will be too slow to linearly search all stored feature vec-tors to find those that satisfy the query criteria. Techniques and data structures are thus required to organize feature vectors and manage the search process so that objects relevant to the query can be located quickly. This paper provides a survey of these techniques and data structures. Index Terms—Efficient search, multidimensional data struc-tures, multimedia databases, multimedia indexing and retrieval. I