海量数据相似性查找系列1 -- Minhashing、LSH与Simhash技术汇总

范涛

发表于2017-04-19

近期对海量数据集如何实现相似查找技术进行了全面总结，并特别关注了高维稀疏数据和稠密数据。

本节主要针对高维稀疏数据集的情况展开讨论，并阐述如何利用哈希技术实现高效的相似性查找过程。

设想一个案例来阐述这个问题：在推荐系统中讨论Item-User矩阵的相关机制。假设物品的数量达到百万级别而用户数量却达到了千万级别这样的情况下矩阵会呈现出高度稀疏的特点那么如何为每个物品计算其Top N个相似物品就是一个值得深入探讨的问题

同样海量文本数据时，在这种情况下下的所有文档都可以被建模为term-document稀疏矩阵，并且我们需要确定每个文档与其最接近的N个相似 document.

如果以配对比较的方式进行，则至少会遇到以下两个主要问题：（1）算法的时间复杂度为O(n²)；（2）在对多个高维向量进行相似性评估时（例如使用Jaccard相似度），耗时较长。

为了解决这一问题的方法是什么？ 最直接的办法就是采用倒排策略。这种方法能够将时间复杂度显著降低几个数量级。然而，在实际应用中还存在另一个关键挑战，并且当处理的数据量达到一定规模时（或者说是程度），倒排列表会变得过长（或者说过于冗长），从而导致查询效率的下降

所以这一章的重点在于介绍哈希方法。这种技术以牺牲精度为代价换来显著的时间提升。

一 Minhashing

先从Mi