使用"最近邻居"进行数据库索引和查找不完全匹配

Question

我正在处理一个有趣的问题.

我有生物识别系统,使用John Daugman的算法将人类虹膜转换成二进制代码(对于我们大学的一些研究).

虹膜代码是"平坦的"(它不是存储为圆形,而是转换为矩形):

column 1 | column 2 | column 3 | ...

10011001 ...
10110111
01100010
...

其中列代表30位.问题是每次虹膜扫描都有自己的噪声掩模(眼睑,反射......),匹配不是100%,但最好是96-98%左右.

到目前为止,我们正在使用这样的算法(汉明距离匹配):

mask = mask1 & mask2;
result = (code1 ^ code2) & mask;

// ration of 1 bits allowed by mask
double difference = (double)one_bits(result)/one_bits(mask); 

问题是我们现在正在构建真实的虹膜数据库(大约1200-1300个主题,每个3-5个虹膜样本,你必须计算轮换,所以你需要为每个进行大约10次测试).我们需要将当前样本与整个数据库进行比较(在80*30位上进行65000次比较),结果显示速度很慢.

问题:是否存在反映数据结构的哈希函数(当几位变化时稍微改变一下)或"容错"？我们需要在整个数据库中构建快速搜索算法(因此我们正在寻找可能的方法来索引它).

更新:我想它应该通过某种"最近邻居"查找来实现,或者使用某种类型的聚类(其中类似的虹膜将被分组,并且在第一轮中仅检查一些代表).

Answer 1

检查局部敏感散列(LSH),如实施此.

"nilsimsa代码类似于散列,但与散列不同,消息中的小变化会导致nilsimsa代码发生微小变化.这样的函数称为局部敏感散列."

如何理解局部敏感哈希？