一种高维数据的近似最近邻检索方法及检索系统

• 摘要：

  本发明公开一种高维数据的近似最近邻检索方法及检索系统,其中,方法包括:步骤1,建立初始化索引,以及高维数据库点集的最近邻表;步骤2,根据初始化索引,获得待检索数据点若干个最邻近点构成的初始候选点集;步骤3,构造临时点集,在最近邻表中查询初始候选点集中各数据点的若干个近邻点,并添加至临时点集中;步骤4,将临时点集中距离待检索数据点距离最小的若干个数据点作为新的候选点集;步骤5,将新的候选点集作为初始候选点集;重复步骤3~步骤5,直至候选点集中的数据点不再更新或者迭代次数达到预定值.利用本发明可以大大提高精度,候选最邻近点集具有指数级收敛速度,大大加快了检索速度,提高了高维数据最近邻点的检索效率.

• 专利类型：

  发明专利

• 申请/专利号：

  CN201610045628.2

• 申请日期：

  2016.01.22

• 公开/公告号：

  CN105550368A

• 公开/公告日：

  2016-05-04

• 发明人：

  蔡登 金仲明 万信逸 付聪

• 申请人：

  浙江大学

• 主分类号：

  G06F17/30(2006.01)I,G,G06,G06F,G06F17

• 分类号：

  G06F17/30(2006.01)I,G,G06,G06F,G06F17,G06F17/30

• 主权项：

  一种高维数据的近似最近邻检索方法,其特征在于,包括:步骤1,采用初始化检索方法对高维数据库点集,建立初始化索引,并建立所述高维数据库点集的最近邻表;步骤2,根据初始化索引,获得待检索数据点在所述高维数据库点集中的若干个最邻近点,若干个最邻近点构成初始候选点集;步骤3,构造临时点集,针对初始候选点集中的每个数据点,在最近邻表中查询该数据点的若干个近邻点,并将查到的各近邻点以及初始候选点添加至临时点集中;步骤4,计算临时点集中所有数据点与待检索数据点的距离,将距离最小的若干个数据点作为新的候选点集;步骤5,将新的候选点集作为初始候选点集;步骤6,重复步骤3~步骤5,直至候选点集中的数据点不再更新或者迭代次数达到预定值,输出候选点集中距离待检索数据点最近的若干数据点作为近似最近邻数据点进行.