Tree-Structured Vector Quantization for Similarity Queries
Hanwei Wu, Qiwen Wang, Markus Flierl · 2017
This paper considers the problem of compression for similarity queries and discusses tree-structured vector quantizers. Here, the focus is on the trade of between the rate of the compressed data and the reliability of the answers to a given query. This problem is different from classical quantization as there is no need to reconstruct the original data. Instead, compression is determined by the reliability of answering given queries. We consider compression schemes that do not allow false negatives when answering queries. Hence, classical vector quantization needs to be modified. We propose quantizers that hierarchically cluster the data into sphere-shaped quantization cells. The query process will be guided by decision rules that avoid false negatives. In particular, we discuss two classic clustering methods, namely k-means and k-center. We use P{maybe}, a probability that is related to the occurrence of false positives, and the computational cost of queries to assess our scheme. Our experiments show that k-center clustering generally performs better than k-means clustering, while tree-structured clustering reduces the computational cost of queries for both methods.