スケッチを用いた検索における2段階フィルタリングの有効性の検証
スケッチを用いた検索における2段階フィルタリングの有効性の検証
复制标题
使用草图验证搜索中两步过滤的有效性
DOI：
10.11517/jsaifpai.123.0_24
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
久保山 哲二
中科院分区：
文献类型：
--
作者：
樋口 直哉;今村 安伸;篠原 武;平田 耕一;久保山 哲二
我们考虑使用草图的最近邻搜索，草图是压缩表示数据点的位串。使用草图的k-最近邻搜索在两个阶段的过程中进行。第一阶段，过滤，使用草图来选择k′个候选者，其中k′≥ k。第二阶段从候选者中选择k个最近邻。过滤中的选择是基于查询点和数据点的草图之间的非对称距离作为候选选择的优先级，而不是传统上使用的汉明距离。非对称距离D1和D∞由查询点和数据点之间的距离的下界的L1样和L∞样聚合定义。对于相对较短的草图（如24位或28位），我们可以通过按不对称距离的顺序枚举草图来有效地选择候选项。本文研究了枚举法的多线程并行加速问题。虽然D1在过滤方面优于D∞，但D1顺序的草图枚举不容易并行化。另一方面，D∞阶的枚举可以有效地并行化.我们提出了一种双重过滤的方法，选择草图的D1从枚举的D∞顺序。
We consider the nearest neighbor search using sketches, which are bitstrings compactly representing data points. A k-nearest neighbor search using sketches is carried out in a two-stage process. The first stage, filtering, uses the sketches to select k′ candidates, where k′≥ k. The second stage selects the k nearest neighbor from the candidates. The selection in filtering is based on asymmetric distances between a query point and sketches of data points as a priority for candidate selection, instead of the Hamming distance traditionally used. The asymmetric distances D1 and D∞ are defined by the L1-like and L∞-like aggregation of the lower bounds of the distances between the query point and data points. With relatively short sketches such as 24-bit or 28-bit, we can efficiently select candidates by enumerating sketches in the order of asymmetric distance. In this paper, we consider the speedup of enumeration methods by parallel computing with multithread. Although D1 outperforms D∞ in filtering, the enumeration of sketches in D1 order is not easy to be parallelized. On the other hand, the enumeration in D∞ order can be efficiently parallelized. We propose a method of double filtering that selects sketches by D1 from the parallelly enumerated ones in D∞ order.