Query vector projection access method

Abstract

We present a new multi-dimensional access method for querying by similarity in databases of high-dimensional vectors. The query vector projection access method (QVPAM) addresses the shortcomings of other dimensionality reduction techniques by deriving the best transformation of the vectors at query-time. QVPAM creates a projection library that contains building blocks for constructing the transformations. QVPAM rapidly searches the projection library at query-time in order to select the set of projection elements that minimizes the work for processing the query. Since the selected set does not need to be complete, QVPAM effectively trades-off query precision and query response time. We describe QVPAM and demonstrate its performance in the content-based querying of a database of high-dimensional color histograms.