大数据处理（1）高维向量相似度匹配
文本相似度匹配
from 《Scaling Up All Pairs Similarity Search》
海量文本的成对相似度的高性能计算（待续） - 马东什么的文章 - 知乎 https://zhuanlan.zhihu.com/p/457947482
摘要：
对于高维空间中的大量稀疏向量数据，我们研究了寻找相似性分数(由余弦距离等函数确定)高于给定阈值的所有向量对的问题。我们提出了一个简单的算法，基于新的索引和优化策略，解决了这个问题，而不依赖于近似方法或广泛的参数调整。我们展示了该方法在广泛的相似阈值设置中有效地处理各种数据集，与以前的最先进的方法相比有很大的加速。
(海量成对文本相似度问题对于反欺诈而言非常重要，因为无论是电商中重要的地址信息，还是设备或用户的离散features之间的相似度计算和构图，都依赖于高性能的文本相似度计算方法，在实践中，我们不可能直接写双循环去做计算，即使是离线也往往需要耗费大量的时间)
一、介绍
许多现实世界的应用程序需要解决一个相似度搜索问题，在这个问题中，人们对所有相似度高于指定阈值的对象对都感兴趣。
- web搜索的查询细化:搜索引擎通常会建议其他查询公式（例如你在百度中输入百，会给你推荐百度）。生成此类查询建议的一种方法是根据查询[19]的搜索结果的相似性来查找所有的相似查询对。由于目标是只提供高质量的建议，所以我们只需要找到相似度高于阈值的查询对（topk问题）。
- 协同过滤:协同过滤算法通过确定哪些用户有相似的品味来进行推荐。因此，算法需要计算相似度高于某个阈值的相似用户对。
- 接近重复的文档检测和消除:特别是在文档索引领域，检测和清除等价的文档是重要的。在许多情况下，由于简单的相等性检验不再满足要求，微小修改的存在使这种检测变得困难。通过具有很高的相似度阈值的相似度搜索，可以实现近重复检测（这方面的工作之前看过simhash，google做海量网页去重的方法）。
- 团伙检测:最近的工作已经应用算法在一个应用程序中寻找所有相似的用户，以识别点击欺诈者[13]团伙。