mapreduce 相似度
- 作者: 容易吗我30141521
- 来源: 51数据库
- 2020-09-22
et expansion），主要有如下几种方法（以Document Similarity为例）：Brute Force：最直接、暴力的方法，两个for循环，计算任意两篇文档之间的相似度，时间复杂度为O(n^2)。这种方法可以得到最好的效果，但是计算量太大，效率较差，往往作为baseline。
Inverted Index Based：由于大量文档之间没有交集term，为了优化算法性能，只需计算那些包含相同term文档之间的相似度即可，算法伪代码如下：基于MapReduce的分布式计算框架如下：为了进一步优化计算，节省空间，研究人员提出了一系列剪枝策略和近似算法，详细见：《Scaling 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》。
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》。
mapreduce是一种编程模型，用于大规模数据集（大于1tb）的并行运算。概念"map（映射）"和"reduce（归约）"，和它们的主要思想，都是从函数式编程语言里借来的，还有从矢量编程语言里借来的特性。它极大地方便了编程人员在不会分布式并行编程的情况下，将自己的程序运行在分布式系统上。 当前的软件实现是指定一个map（映射）函数，用来把一组键值对映射成一组新的键值对，指定并发的reduce（归约）函数，用来保证所有映射的键值对中的每一个共享相同的键组。
Inverted Index Based：由于大量文档之间没有交集term，为了优化算法性能，只需计算那些包含相同term文档之间的相似度即可，算法伪代码如下：基于MapReduce的分布式计算框架如下：为了进一步优化计算，节省空间，研究人员提出了一系列剪枝策略和近似算法，详细见：《Scaling 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》。
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》。
mapreduce是一种编程模型，用于大规模数据集（大于1tb）的并行运算。概念"map（映射）"和"reduce（归约）"，和它们的主要思想，都是从函数式编程语言里借来的，还有从矢量编程语言里借来的特性。它极大地方便了编程人员在不会分布式并行编程的情况下，将自己的程序运行在分布式系统上。 当前的软件实现是指定一个map（映射）函数，用来把一组键值对映射成一组新的键值对，指定并发的reduce（归约）函数，用来保证所有映射的键值对中的每一个共享相同的键组。
推荐阅读
