Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases

By Christian Böhm, Stefan Berchtold, Daniel A. Keim. 2001

963 citations recorded by the source corpus.

During the last decade, multimedia databases have become increasingly important in many application areas such as medicine, CAD, geography, and molecular biology. An important research issue in the field of multimedia databases is the content-based retrieval of similar multimedia objects such as images, text, and videos. However, in contrast to searching data in a relational database, a content-based retrieval requires the search of similar objects as a basic functionality of the database system. Most of the approaches addressing similarity search use a so-called feature transformation that transforms important properties of the multimedia objects into high-dimensional points (feature vectors). Thus, the similarity search is transformed into a search of points in the feature space that are close to a given query point in the high-dimensional feature space. Query processing in high-dimensional spaces has therefore been a very active research area over the last few years. A number of new index structures and algorithms have been proposed. It has been shown that the new index structures considerably improve the performance in querying large multimedia databases. Based on recent tutorials [Berchtold and Keim 1998], in this survey we provide an overview of the current state of the art in querying multimedia databases, describing the index structures and algorithms for an efficient query processing in high-dimensional spaces. We identify the problems of processing queries in high-dimensional space, and we provide an overview of the proposed approaches to overcome these problems.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Information Retrieval & Search, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

In Signal Processing

Citations in the corpus

Product Quantization for Nearest Neighbor Search (2011, background): “Nearest neighbor search is inherently expensive due to the curse of dimensionality [3], [4].”
Succinct nearest neighbor search (2011, methodology): “other topics for exact proximity searching [7, 21, 12, 4].”
Searching with quantization: approximate nearest neighbor search using short codes and distance estimators (2009, background): “Nearest neighbor search is inherently expensive due to the curse of dimensionality [1, 2].”
iDistance: An adaptive B+-tree based indexing method for nearest neighbor search (2005, methodology): “However, linear scan remains an ecient search strategy for similarity search [ Beyer et al. 1999 ].”
A PCA-based similarity measure for multivariate time series (2004, neutral): “Without this property, the filter and refinement phases of existing multidimensional indexing techniques cannot be utilized, because false dismissals may occur in the filter phase [3, 5, 17].”
Multiple feature hashing for real-time large scale near-duplicate video retrieval (2011, background): “Many indexing meth-ods in database literature have been proposed to support multi-media search, such as tree-structures [3], dimensionality reduction [28], hashing [6], and others [5].”
Searching with expectations (2010, background): “Nearest neighbor (NN) search is inherently expensive due to the curse of dimensionality [2, 1].”
Approximate Nearest Neighbor Search by Residual Vector Quantization (2010, background): “Approximate nearest neighbor search (ANN) is proposed to tackle the curse of the dimensionality problem [1,2] in exact nearest neighbor (NN) searching.”
View-based 3-D object recognition using shock graphs (2002, background): “A complete survey of the subject can be found in [10].”
Image retrieval: Ideas, influences, and trends of the new age (2008, neutral): “Surveys also exist on closely related topics such as relevance feedback [Zhou and Huang 2003], high-dimensional indexing of multimedia data [Bohm et al. 2001], face recognition [Zhao et al. 2003] (useful for face-based image retrieval), applications of CBIR to medicine [Muller et al. 2004], and…”
Near neighbor searching with K nearest references (2015, background): “in application papers, surveys [10,16,28,50] and even books [47,57].”