Extremely Low Bit-Rate Nearest Neighbor Search Using a Set Compression Tree
Extremely Low Bit-Rate Nearest Neighbor Search Using a Set Compression Tree
复制标题
使用集合压缩树的极低比特率最近邻搜索
DOI：
10.1109/tpami.2014.2339821
复制
发表时间：
2014
影响因子：
23.6
通讯作者：
Andrew Zisserman
中科院分区：
文献类型：
--
作者：
Relja Arandjelović;Andrew Zisserman
这项工作的目标是一个数据结构，以支持近似最近邻搜索非常大规模的向量描述符集。我们希望优化的标准是：（i）表示的内存占用应该非常小（以便它适合主存）;（ii）原始向量的近似应该是准确的。我们介绍了一种新的编码方法，命名为集压缩树（SCT），满足这些标准。它能够精确地压缩100万个描述符，每个描述符只使用几个比特。大压缩率不是通过在每个描述符的基础上压缩，而是通过联合压缩描述符集合来实现的。我们描述了编码，解码和最近邻搜索的使用，所有这些都是非常简单的实现。该方法在标准基准测试（SIFT 1 M和8000万小图像）上进行了测试，与许多最先进的方法相比，该方法具有上级性能，包括乘积量化，局部敏感哈希，频谱哈希和迭代量化。例如，SCT使用5位比任何其他方法都具有更低的错误，即使它们每个描述符使用16位或更多位。我们还包括对标准基准测试的所有上述方法的比较。
The goal of this work is a data structure to support approximate nearest neighbor search on very large scale sets of vector descriptors. The criteria we wish to optimize are: (i) that the memory footprint of the representation should be very small (so that it fits into main memory); and (ii) that the approximation of the original vectors should be accurate. We introduce a novel encoding method, named a Set Compression Tree (SCT), that satisfies these criteria. It is able to accurately compress 1 million descriptors using only a few bits per descriptor. The large compression rate is achieved by not compressing on a per-descriptor basis, but instead by compressing the set of descriptors jointly. We describe the encoding, decoding and use for nearest neighbor search, all of which are quite straightforward to implement. The method, tested on standard benchmarks (SIFT1M and 80 Million Tiny Images), achieves superior performance to a number of state-of-the-art approaches, including Product Quantization, Locality Sensitive Hashing, Spectral Hashing, and Iterative Quantization. For example, SCT has a lower error using 5 bits than any of the other approaches, even when they use 16 or more bits per descriptor. We also include a comparison of all the above methods on the standard benchmarks.