not logged in. (login)

Document Information

Query Sensitive Embeddings (2007) Vassilis Athitsos,Marios Hadjieleftheriou,George Kollios and Stan Sclaroff	Download pdf
Abstract: A common problem in many types of databases is retrieving the most similar matches to a query object. Finding those matches in a large database can be too slow to be practical, especially in domains where objects are compared using computationally expensive similarity (or distance) measures. Embedding methods can significantly speed up retrieval by mapping objects into a vector space, where distances can be measured rapidly using a Minkowski metric. In this paper we present a novel way to improve embedding quality. In particular, we propose to construct embeddings that use a ``query-sensitive'' distance measure for the target space of the embedding. This distance measure is used to compare the vectors that the query and database objects are mapped to. The term ``query-sensitive'' means that the distance measure changes depending on the current query object. We demonstrate theoretically that using a query-sensitive distance measure increases the modeling power of embeddings and allows them to capture more of the structure of the original space. We also demonstrate experimentally that query-sensitive embeddings can significantly improve retrieval performance. In experiments with an image database of handwritten digits and a time-series database, the proposed method outperforms existing state-of-the-art non-Euclidean indexing methods, meaning that it provides significantly better trade-offs between efficiency and retrieval accuracy.
Published in: ACM Transactions on Database Systems (TODS), Vol. 32, No. 2, 2007.