Dimensionality reduction and similarity computation by inner-product approximations

Ömer Egecioglu, Hakan Ferhatosmanoglu, Umit Ogras

Research output: Contribution to journalArticlepeer-review

38 Scopus citations


As databases increasingly integrate different types of information such as multimedia, spatial, time-series, and scientific data, it becomes necessary to support efficient retrieval of multidimensional data. Both the dimensionality and the amount of data that needs to be processed are increasing rapidly. Reducing the dimension of the feature vectors to enhance the performance of the underlying technique is a popular solution to the Infamous curse of dimensionality. We expect the techniques to have good quality of distance measures when the similarity distance between two feature vectors Is approximated by some notion of distance between two lower-dimensional transformed vectors. Thus, it Is desirable to develop techniques resulting In accurate approximations to the original similarity distance. In this paper, we investigate dimensionality reduction techniques that directly target minimizing the errors made in the approximations. In particular, we develop dynamic techniques for efficient and accurate approximation of similarity evaluations between high-dimensional vectors based on inner-product approximations. Inner-product, by itself, is used as a distance measure in a wide area of applications such as document databases. A first order approximation to the inner-product is obtained from the Cauchy-Schwarz inequality. We extend this idea to higher order power symmetric functions of the multidimensional points. We show how to compute fixed coefficients that work as universal weights based on the moments of the probability density function of the data set. We also develop a dynamic model to compute the universal coefficients for data sets whose distribution is not known. Our experiments on synthetic and real data sets show that the similarity between two objects in high-dimensional space can be accurately approximated by a significantly lower-dimensional representation.

Original languageEnglish (US)
Pages (from-to)714-726
Number of pages13
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number6
StatePublished - Jun 2004
Externally publishedYes


  • Dimensionality reduction
  • High-dimensional data
  • Inner-product approximation
  • P-NORMS, similarity search

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Dimensionality reduction and similarity computation by inner-product approximations'. Together they form a unique fingerprint.

Cite this