Practical Data-Dependent Metric Compression with Provable Guarantees
We introduce a new distance-preserving compact representation of multidimensional point-sets. Given n points in a d-dimensional space where each coordinate is represented using B bits (i.e., dB bits per point), it produces a representation of size O(d log(dB/ ) + log n) bits per point from which one can approximate the distances up to a factor of 1 ± . Our algorithm almost matches the recent bound of [6] while being much simpler. We compare our algorithm to Product Quantization (PQ) [7], a state of the art heuristic metric compression method. We evaluate both algorithms on several data sets: SIFT (used in [7]), MNIST [11], New York City taxi time series [4] and a synthetic one-dimensional data set embedded in a high-dimensional space. With appropriately tuned parameters, our algorithm produces representations that are comparable to or better than those produced by PQ, while having provable guarantees on its performance.
This paper presents an impressive algorithm that embeds a set of data points into a small dimensional space, represented by a near-optimal number of bits. The most appealing aspect of this paper is to provide a simple but provable dimensionality reduction algorithm, and supported by empirical experiments.
=== Strengths ===
This paper is supported by strong theoretical analysis. And, it is much simpler algorithm than [5] with a slightly worse bit complexity.
=== Weaknesses ===
1. This is an example of data-dependent compression algorithm. Though this paper presents a strong theoretical guarantee, it needs to be compared to state-of-the art data-dependent algorithms. For example,
 - Optimized Product Quantization for Approximated Nearest Neighbor Search, T. Ge et al, CVPR’13
 - Composite Product Quantization for Approximated Nearest Neighbor Search, T. Zhang et al, ICML’14
 - And, other recent quantization algorithms.
2. The proposed compression performs worse than PQ when a small code length is allowed, which is the main weakness of this method, in view of a practical side.
3. When the proposed compression is allowed to have the same bit budget to represent each coordinate, the pairwise Euclidean distance is not distorted? Most of compression algorithms (not PCA-type algorithms) suffer from the same problem.
=== Updates after the feedback ===
I've read other reviewers' comments and authors' feedback. I think that my original concerns are resolved by the feedback. Moreover, they suggest a possible direction to combine QuadSketch with OPQ, which is appealing.