We introduce a new distance-preserving compact representation of multi-dimensional 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(d B/\epsilon) + \log n)$ bits per point from which one can approximate the distances up to a factor of $1 \pm \epsilon$. Our algorithm almost matches the recent bound of~\cite{ indyk2017near} while being much simpler. We compare our algorithm to Product Quantization (PQ)~\cite{ jegou2011product}, a state of the art heuristic metric compression method. We evaluate both algorithms on several data sets: SIFT (used in \cite{ jegou2011product}), MNIST~\cite{ lecun1998mnist}, New York City taxi time series~\cite{ guha2016robust} 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.
Categories: cs.DS