如何用MapReduce实现LSH？
如何用MapReduce实现LSH？
提问于 2015-03-28 18:28:54
假设我们希望通过MapReduce实现本地敏感散列(LSH)。具体来说，假设签名矩阵的块由列组成，元素是键值对，其中键是列号，值是签名本身(即值的向量)。
(a)演示如何为所有带生产桶，作为单个MapReduce过程的输出。提示:请记住，Map函数可以从单个元素生成多个键值对。
(b)显示另一个MapReduce进程如何将(a)的输出转换为需要比较的对列表。具体来说，对于每一列i，都应该有一个列j>i的列表，需要与之进行比较。
Stack Overflow用户
回答已采纳
发布于 2015-04-07 17:52:00
(a)
- Map:元素及其签名作为输入，生成键值对(bucket_id，元素)。
- 减少:为所有波段产生输出的桶，即(bucket_id，list(元素))
map(key, value: element):
split item to bands
for band in bands:
for sig in band:
key = hash(sig) // key = bucket id
collect(key, value)
reduce(key, values):
collect(key, values)(b)
- Map:输出(a)作为输入，在同一个桶中生成组合列表，即(bucket_id，列表(元素)) -> (bucket_id，组合(列表(元素)，组合()是从同一个桶中选择的任意两个元素。
- 减少:输出需要比较的项目对，特别是对于每一列i，应该有一个列j>i的列表，这些列需要与我进行比较。
map(key, value):
for itemA, itemB in combinations(value)
key = (itemA.id, itemB.id)
collect(key, [itemA, itemB])
reduce(key, values):
collect(key, values)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/29320943
复制相关文章
相似问题
腾讯云开发者
