A fast nearest neighbor search algorithm based on vector quantization
A fast nearest neighbor search algorithm based on vector quantization
复制标题
一种基于矢量量化的快速最近邻搜索算法
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
S. Corlay
中科院分区：
文献类型：
--
作者：
S. Corlay
在本文中，我们提出了一种新的快速最近邻搜索算法，基于矢量量化。像许多其他分支和边界搜索算法[1，10]一样，预处理递归地将数据集划分为不相交的子集，直到每个部分中的点的数量足够小。在此过程中，将构建搜索树数据结构。这种初步的递归数据集划分是基于初始数据集的经验分布的矢量量化。与前面引用的方法不同，这种划分不允许先验地用单个测试消除搜索树中的几个兄弟节点。为了克服这个困难，我们提出了一个算法，以减少测试的兄弟节点的数量，我们称之为“朋友Voronoi细胞”的最小列表。该方法的完整描述需要深入了解Delaunay三角剖分和Voronoi图的性质
In this article, we propose a new fast nearest neighbor search algorithm, based on vector quantization. Like many other branch and bound search algorithms [1,10], a preprocessing recursively partitions the data set into disjointed subsets until the number of points in each part is small enough. In doing so, a search-tree data structure is built. This preliminary recursive data-set partition is based on the vector quantization of the empirical distribution of the initial data-set. Unlike previously cited methods, this kind of partitions does not a priori allow to eliminate several brother nodes in the search tree with a single test. To overcome this difficulty, we propose an algorithm to reduce the number of tested brother nodes to a minimal list that we call ''friend Voronoi cells''. The complete description of the method requires a deeper insight into the properties of Delaunay triangulations and Voronoi diagrams