Pivot Generation Algorithm with a Complete Binary Tree for Efficient Exact Similarity Search
Pivot Generation Algorithm with a Complete Binary Tree for Efficient Exact Similarity Search
复制标题
DOI：
10.1587/transinf.2017edp7077
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Yuki Yamagishi;K. Aoyama;Kazumi Saito;Tetsuo Ikeda
中科院分区：
文献类型：
--
作者：
Yuki Yamagishi;K. Aoyama;Kazumi Saito;Tetsuo Ikeda
提出了一种加速大规模数据集精确相似搜索的轴心集生成算法。为了处理大规模的数据集，离线高效地构建搜索索引和在线快速精确地进行相似度搜索是非常重要的。本文提出的算法采用了两种新颖的技术：分层数据划分和快速枢轴优化技术，有效地生成了胜任枢轴。为了有效地利用少量的枢轴，前者根据分配的两个枢轴的秩顺序，递归地将数据集划分为两个大小相同的子集，从而得到一个完整的二叉树。后者通过熟练地操作映射到枢轴空间的数据对象，以较低的计算成本计算一个定义的目标函数进行枢轴优化。由于生成的枢轴提供了查询对象和数据对象之间距离的严格下限，因此精确的相似性搜索算法有效地避免了不必要的距离计算。我们证明了使用所提出算法生成的枢轴的搜索算法以极高的速率减少了距离计算，对于真实的大规模图像数据集的范围查询问题。关键词：相似度搜索，枢轴生成，完全二叉树
This paper presents a pivot-set generation algorithm for accelerating exact similarity search in a large-scale data set. To deal with the large-scale data set, it is important to efficiently construct a search index offline as well as to perform fast exact similarity search online. Our proposed algorithm efficiently generates competent pivots with two novel techniques: hierarchical data partitioning and fast pivot optimization techniques. To make effective use of a small number of pivots, the former recursively partitions a data set into two subsets with the same size depending on the rank order from each of two assigned pivots, resulting in a complete binary tree. The latter calculates a defined objective function for pivot optimization with a low computational cost by skillfully operating data objects mapped into a pivot space. Since the generated pivots provide the tight lower bounds on distances between a query object and the data objects, an exact similarity search algorithm effectively avoids unnecessary distance calculations. We demonstrate that the search algorithm using the pivots generated by the proposed algorithm reduces distance calculations with an extremely high rate regarding a range query problem for real large-scale image data sets. key words: similarity search, pivot generation, complete binary tree