Abstract
This work addresses approximate nearest neighbor search applied in the domain of large-scale image retrieval. Within the group testing framework we propose an efficient off-line construction of the search structures. The linear-time complexity orthogonal grouping increases the probability that at most one element from each group is matching to a given query. Non-maxima suppression with each group efficiently reduces the number of false positive results at no extra cost. Unlike in other well-performing approaches, all processing is local, fast, and suitable to process data in batches and in parallel. We experimentally show that the proposed method achieves search accuracy of the exhaustive search with significant reduction in the search complexity. The method can be naturally combined with existing embedding methods.
Abstract (translated)
这项工作涉及在大规模图像检索领域中应用的近似最近邻搜索。在组测试框架内，我们提出了一种有效的搜索结构离线构造。线性时间复杂度正交分组增加了来自每个组的至多一个元素与给定查询匹配的概率。每组的非最大值抑制有效地减少了假阳性结果的数量，无需额外费用。与其他表现良好的方法不同，所有处理都是本地的，快速的，适合批量和并行处理数据。我们通过实验证明，该方法实现了穷举搜索的搜索精度，并大大降低了搜索复杂度。该方法可以自然地与现有的嵌入方法相结合。
URL
https://arxiv.org/abs/1807.09848
