algorithm – 索引相似性搜索
发布时间：2020-12-14 04:42:20 所属栏目：大数据 来源：网络整理
导读：我有大约100M数字向量( Minhash指纹),每个向量包含0到65536之间的100个整数,我正在尝试使用 Jaccard similarity对这个指纹数据库进行快速相似性搜索,即给出一个查询向量(例如[1],30,9,42,…])找到此查询集与100M集数据库的交集/并集的比率. 要求是在笔记本电
|
我有大约100M数字向量(
Minhash指纹),每个向量包含0到65536之间的100个整数,我正在尝试使用
Jaccard similarity对这个指纹数据库进行快速相似性搜索,即给出一个查询向量(例如[1],30,9,42,…])找到此查询集与100M集数据库的交集/并集的比率.
要求是在笔记本电脑上以< 1秒(不包括索引/文件IO时间)返回查询向量的k个“最近邻居”.所以显然需要某种索引,问题是如何最有效的方法来解决这个问题. 笔记： 我尝试使用0700第3章中描述的简单locality sensitive hashing technique,将每个向量分成20个“带”或长度为5的片段,将这些片段转换为字符串(例如[1,2,45,3] – > ;“124523”)并使用这些字符串作为哈希表中的键,其中每个键包含“候选邻居”.但问题是,它为这些片段中的某些片段创建了太多候选者,而且频段数量的变化无济于事. 解决方法
解决这个问题的一种方法如下：
(1)将向量排列成树(基数树). (2)用模糊标准查询树,换句话说,匹配是树的每个节点的值的差异是否在阈值内 (3)从(2)生成包含所有匹配向量的子树 (4)现在,用较小的阈值重复子树上的过程(2) 继续,直到子树有K项.如果K项目太少,则采用前一个树并计运算符树每个成员的Jacard距离,并排序以消除最差的匹配,直到您只剩下K个项目为止. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |