[译]针对大数据的Jaccard相似度计算优化

在大量数据对间计算Jaccard相似度是一个巨大的难题。因为它的复杂度是O(N^2). 然而这里有许多优化技术能够显著地降低计算量。我花了大约一周的时间搜索了相关资料,研究了大量技术。下面是我找到的不同方法的总结,同时提供了部分有用信息的链接。值得提到的是以下两个非常有用的资料:
《Similarity Joins in Relational Databases》第六章
《Mining Massive Datasets》第三章

  1. 基于Token的过滤:
    想法:根据token来放置数据,同时仅仅考虑至少有一个token匹配的数据对。

Continue reading