Dynamic Dimensionality Reduction and Similarity DistanceComputation by Inner Product Approximations

Developing efficient ways for dimensionality reduction is crucial for the queryperformance in multimedia databases. For approximation queries a carefulanalysis must be performed on the approximation quality of the dimensionalityreduction technique. Besides having the lower-bound property, we expect thetechniques to have good quality of distance measures when the similaritydistance between two feature vectors is approximated by some notion of distancebetween two lower dimensional transformed vectors. Thus it is desirable todevelop techniques which have accurate approximations to the originalsimilarity distance when we eschew the lower-bound property.In this paper, we develop dynamic dimensionality reduction based on theapproximation of the standard inner-product. The method uses the powersymmetric functions of the components of the vectors, which are powers of thep-norms of the vectors for p = 1,2,.., m. The number m of such norms used is aparameter of the algorithm whose simplest instance gives a first-orderapproximation implied by the Cauchy-Schwarz inequality. We show how to computefixed coefficients that work as universal weights based on the moments of theprobability density function assumed for the distribution of the components ofthe input vectors in the data set. If the distribution of the components ofthe vectors is not known we show how the method can be adapted to workdynamically by incremental adjustment of the parameters.The experiments conducted on various distributions show that with thistechnique the similarity between two objects in high dimensional space can beaccurately approximated by a significantly lower dimensional representation.