Transform-based compression for quadratic similarity queries

摘要

This paper considers the problem of compression for similarity queries [1] and discusses transform-based compression schemes. Here, the focus is on the tradeoff between the rate of the compressed data and the reliability of the answers to a given query. We consider compression schemes that do not allow false negatives when answering queries. Hence, classical compression techniques need to be modified. We propose transform-based compression schemes which decorrelate original data and regard each transform component as a distinct D-admissible system. Both compression and retrieval will be performed in the transform domain. The transform-based schemes show advantages in terms of encoding speed and the ability of handling high-dimensional correlated data. In particular, we discuss component-based and vector-based schemes. We use P{maybe}, a probability that is related to the occurrence of false positives to assess our scheme. Our experiments show that component-based schemes offer both good performance and low search complexity.