基于多级索引的高维数据近似最近邻搜索

摘要：

当前的高维数据最近邻搜索方法大多应用单级索引,导致近邻搜索稳定性较差,且时间开销较大.为此提出基于多级索引的高维数据近似最近邻搜索方法.利用二级距离敏感哈希算法(M2LSH)实现多级索引.将第一次哈希处理的高维数据输入哈希桶内,使用二次哈希映射桶号,使其在一维空间中呈现.依据各桶内数据量完成临近哈希桶合并,将新哈希桶作为候选搜索集合,实现高维数据近似最近邻搜索.实验结果表明:不同相邻桶距离下,所提算法优化后的近似比率均可保持在1左右,搜索效果大幅度提升,且稳定性较好;将该算法的哈希函数数量和哈希桶宽度分别设置为12、3,能获得更优异的搜索效果,并极大地节省时间开销,说明多级索引是处理高维数据近似最近邻问题的有效方法.

关键词：多级索引、高维数据、近似最近邻、距离敏感哈希、哈希桶

所属期刊栏目：39

分类号：TP311.3(计算技术、计算机技术)

在线出版日期：2023-01-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：398-401