求解高维相似度矩阵（All Pairs Similarity Search，or Pairwise Similarity），或者在大规模数据集上挖掘Top-K最相似的items（K-Nearest Neighbor Graph Construction， or TopK Set expansion），主要有如下几种方法（以Document Similarity为例）：

1. Brute Force：最直接、暴力的方法，两个for循环，计算任意两篇文档之间的相似度，时间复杂度为O(n^2)。这种方法可以得到最好的效果，但是计算量太大，效率较差，往往作为baseline。 http://52opencourse.com/?qa=blob&qa_blobid=13813575554602706934
2. Inverted Index Based：由于大量文档之间没有交集term，为了优化算法性能，只需计算那些包含相同term文档之间的相似度即可，算法伪代码如下：s&source=web&cd=1&ved=0CGMQFjAA&url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.102.2601&rep=rep1&type=pdf&ei=neXAT__LHuHL2QWtuZFW&usg=AFQjCNH26Z_aV-WjeDKDEKeHghEXK_WdEw&sig2=whlI8tFEP0HrZ0ZEFx1I5gScaling Up All Pairs Similarity Search》、《Pairwise document similarity in large collections with MapReduce》、《Brute Force and Indexed Approaches to Pairwise Document Similarity Comparisons with MapReduce》。
3. Locality Sensitive Hashing（LSH）：通过对文档进行某种度量操作后将其分组散列在不同的桶中。在这种度量下相似度较高的文档被分在同一个桶中的可能性较高。主要用于Near-duplicate detection和Image similarity identification等，详细见：《Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality》、《Google news personalization: scalable online collaborative filtering》。

基于Inverted Index Based和Locality Sensitive Hashing（LSH）方法，利用MapReduce分布式计算框架，可以较好的解决高维相似度矩阵计算的问题，那么再抛一个实际中面临的问题：不断产生新的数据项，如何高效更新相似度矩阵？

基于Inverted Index Based的方法，因倒排拉链长短不一，较长的拉链难免成为短板，如何缓解、解决？

稍微转换一下思路：将问题从相似度矩阵计算变成相似对象计算，对于聚类等需要相似度计算的应用尽量保证最终结果不变。处理数据时的瓶颈主要由两个方面造成：1) 数据规模很大；2) 用来表示数据的特征维度很大。fandy这里介绍的是Jimmy Lin在SIGIR09上介绍的基于Map Reduce的pairwise similarity计算。除了简单粗暴的方法之外，还提出了使用Inverted Index来加速，这里基于的观察是对于特征没有交集的对象相似度自然为0，那么就无需比较。我们可以进一步考虑即使两者特征有重合，是否需要比较呢？答案是否定的，例如两个对象想重合的特征具有比较小的数值，那么他们的相似度远低于阈值，从而确定他们是不相似的。因此，可以借鉴similarity search中的不少研究成果（Near-duplicate detection也属于这个范畴），使用Prefix-filtering的方法快速缩小比较所用的搜索空间。最简单的做法是：利用常规的特征选择方法选出一定比例的特征作为对象prefix，这样等同于做了降维处理，同时基于inverted index本身对应的词汇V的大小也缩小了，从而进一步降低了比较的次数。我们可以将Prefix中任一特征重合的对象归入同一个block。一个对象可以属于多个blocks。这里block有点类似上文中提到的基于一个term或一维feature对应的对象集合。这里省去了理论部分来说明如何选择prefix，以及如何避免False negative（即应该相似，但是被排除在block之外）的产生的证明。这种方法可以是多阶段的（一般为2阶段），每一阶段的完成均缩小搜索空间。和基于map-reduce的pairwise similarity计算比较，该方法的初始阶段（或阶段1）由于维度比较小，可以直接放入内存在单机迅速完成，此后每阶段产生的block均相互独立，可进行更高级的相似度比较操作。我们可以在每次block内处理完根据对象对合并（类似reduce），也可以在分成block之后，根据对象来构建连通分量，基于连通分量进行独立相似度计算。如若连通分量很大，可以进一步分多阶段处理。当得到的连通分量大小适中时，可以分多核或多机独立运行。这里我们计算得到的pairwise 相似度不完整，不仅不包括不相关的，还排除弱相关的。和inverted index based相比，LSH-based是全局相似的，将相似的对象排放在一起，这样增加了访问的locality特性，从而支持快速scan，避免随机访问。类似地，LSH也可以被应用在多阶段相似对象计算中的block生成从而缩小搜索空间。

对于新产生的数据，根据其表示的特征（无论是基于prefix-filtering的还是完整的高维表示），插入到倒排索引相应的posting list中，或LSH相应的bucket中（注意，其实LSH或SimHash可以被看作是一种直接生成哈希（比如利用海明距离等）来保证全局相似和相似对象连续存储特点的高效算法）。这里相似度矩阵的更新分为新产生数据之间的相似度计算，以及新产生数据和原有关联数据之间的相似度计算。那么从矩阵上来看其实增加了3个子矩阵，如果相似度是对称的，那么其实就独立计算两块子矩阵，而其中每块均利用同样的map-reduce的思路，对于同一posting list中或bucket中的进行map，而之后根据对象配对进行reduce。这里无需对于posting list或bucket中的所有对象配对进行map，只需要针对新产生的数据，等于在map和reduce之上增加了一个filter减少了数据处理量。对于新产生数据量比较少的情况下，建议直接加载到内存来处理，并将shuffling变成基于内存形成流水线操作。如果新产生数据比较大时（可批量处理），操作和之前一致。对于删除，并不删除相似度矩阵中的行列，而是将单元格置0等作为标记。类似地，更新操作（虽然比较少见），可以简单地作为删除和新增操作的叠加。Inverted Index比较长的时候可以考虑将其分成不断的sub-posting-list，并设置landmark ID来管理sub lists和原本的long list的对应关系，这类方法也称之为block-based inverted index。当然过长的posting list就代表着是一个DF很高（即出现在很多对象（视为文档）中），通过合适的特征选择，即可排除在prefix之外，那么也间接解决了这个问题。

make sense

之前重点关注全局相似/非近似的解决方案，缺少Prefix-filtering的介绍，谢谢haofen补充。

其实，为了节省计算资源，完全可以将《Scaling Up All Pairs Similarity Search》提到的许多优化思想、prefix filtering等策略引入到MapReduce框架中，因为的确存在这样的情况：即使两者特征有重合，也没必要做比较。因为最相似的往往只有少数，而且一般的需求也仅是Top-K。

总之，优化目的是缩小搜索空间，减少计算量，节省存储空间。

“和inverted index based相比，LSH-based是全局相似的，将相似的对象排放在一起，这样增加了访问的locality特性，从而支持快速scan，避免随机访问。” 请问这句是什么意思？inverted index based也是全局解吧？！

haofen提到的 “Inverted Index比较长的时候可以考虑将其分成不断的sub-posting-list，并设置landmark ID来管理sub lists和原本的long list的对应关系，这类方法也称之为block-based inverted index。当然过长的posting list就代表着是一个DF很高（即出现在很多对象（视为文档）中），通过合适的特征选择，即可排除在prefix之外，那么也间接解决了这个问题。” 优化也是很实用的策略。