Abstract
The quadratic form distance (QFD) has been utilized as an e ective similarity function in multimedia retrieval, in particular, when a histogram representation of objects is used. Unlike the widely used Euclidean distance, the QFD allows to arbitrarily correlate the histogram bins (dimensions), allowing thus to better model the similarity between histograms.
However, unlike Euclidean distance, which is of linear time complexity, the QFD requires quadratic time to evaluate the similarity of two objects. In consequence, indexing and querying a database under QFD are expensive operations.
In this paper we show that, given static correlations between dimensions, the QFD space can be transformed into an equivalent Euclidean space. Thus, the overall complexity of indexing and searching in the QFD similarity model can be reduced qualitatively.