Multiple complementary inverted indexing based on multiple metrics
Multiple complementary inverted indexing based on multiple metrics
复制标题
DOI：
10.1007/s11042-018-6439-x
复制
发表时间：
2018-08
影响因子：
3.6
通讯作者：
Kai Zhang;Wen-gang Zhou;Shaoyan Sun;Bin Li
中科院分区：
文献类型：
--
作者：
Kai Zhang;Wen-gang Zhou;Shaoyan Sun;Bin Li
基于矢量量化的倒排索引是大规模信息检索中的一种常用技术。利用基于某种相似性度量的矢量量化，样本空间被划分为一些Voronoi单元，并且每个单元中的样本由倒排列表索引。通过查找查询所在的单元格，可以有效地识别查询的最近邻居。为了提高查全率，样本空间划分已经多次执行，并使用不同的k-means初始化来构建多个倒排索引。而对于单个相似性度量，例如，欧氏距离，多个倒排索引之间可能存在高相关性，这限制了召回率的可能增益。本文提出了一种基于多个相似性度量的多样本空间划分的多倒排索引方法。此外，几种技术，用于定义多个指标进行了实证研究。在3个有代表性的数据集上进行了实验，百万级SIFT和GIST特征集以及深度学习产生的特征集，以适当地评估所提出的方法的有效性。实验结果表明，该方法在查全率和检索时间上与现有的倒排索引方法相比具有较好的性能，其中Latin-Hypercube加权方法能够产生更多样的多个度量，在查全率上获得更好的增益。
Inverted indexing based on vector quantization has been a popular technique in large scale information retrieval. With vector quantization based on a certain similarity metric, the sample space is partitioned into some voronoi cells, and samples in each cell are indexed by an inverted list. The nearest neighbors of a query are efficiently identified by looking up the cell where the query is located. To improve the recall, the sample space partitioning has been performed multiple times with different initializations ofk-means to build multiple inverted indexes. While with the single similarity metric, e.g., Euclidean distance, high correlation may exist between multiple inverted indexes, which constrains the possible gain in recall. A new multiple inverted indexing method based on multiple sample space partitioning with multiple different similarity metrics is presented in this paper. Furthermore, several techniques for defining multiple metrics are investigated empirically. Experiments are conducted on 3 representative datasets, million-scale SIFT and GIST feature sets and a deep-learning-produced feature set, to properly evaluate the effectiveness of the proposed method. Experiment results show that the proposed method has competitive performance compared with the state-of-the-art inverted indexing methods in terms of recall and retrieval time, and the Latin-Hypercube weighting method can generate better diverse multiple metrics and get better gain in recall.