How to Approximate the Inner-product: Fast Dynamic Algorithms forEuclidean Similarity

We develop dynamic dimensionality reduction based on the approximation of thestandard inner-product. This results in a family of fast algorithms forchecking similarity of objects whose feature representations are largedimensional real vectors, a common situtiton in various multimedia databases.The method uses the power symmetric functions of the components of the vectors,which are powers of the p-norms of the vectors for p = 1, 2,.., m. The numberm of such norms used is a parameter of the algorithm whose simplest instancegives a first-order approximation implied by the Cauchy-Schwarz inequality. Weshow how to compute fixed coefficients that work as universal weights based onthe moments of the probability density function assumed for the distribution ofthe components of the input vectors in the data set. If the distribution ofthe components of the vectors is not known we show how the method can beadapted to work dynamically by incremental adjustment of the parameters.