Efficient k-Nearest Neighbor Queries with the Signature Quadratic Form Distance

A frequently encountered query type in multimedia databases is the k-nearest neighbor query which finds the k-nearest neighbors of a given query. To speed up such queries and to meet the user requirements in low response time, approximation techniques play an important role. In this paper, we present an efficient approximation technique applicable to distance measures defined over flexible feature representations, i.e. feature signatures. We apply our approximation technique to the recently proposed Signature Quadratic Form Distance applicable to feature signatures. We performed our experiments on numerous image databases, gathering k-nearest neighbor query rankings in significantly low computation time with an average speed-up factor of 13.