MapReduce如何实现LSH？

Question

假设我们希望通过MapReduce 实现局部敏感散列(LSH)。具体来说，假设签名矩阵的块由列组成，元素是键值对，其中键是列号，值是签名本身（即值向量）。

(a) 显示如何为所有波段生成桶作为单个输出 MapReduce 过程。提示：记住 Map 函数可以产生来自单个元素的多个键值对。

(b) 显示另一个 MapReduce 进程如何将 (a) 的输出转换为需要比较的对列表。具体来说，对于每一列 i，应该有我需要的那些列的列表 j > i 比较

Answer 1

(一)

Map：将元素及其签名作为输入，产生键值对（bucket_id，元素）
Reduce：生成所有波段的桶作为输出，即 (bucket_id, 列表(元素))

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, list(elements)) -> (bucket_id, 组合（列表（元素））），其中组合（）是任意两个元素从同一个桶中选择。
Reduce：输出需要的item对相比之下，具体来说，对于每一列 i，应该有一个列表需要与 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)

MapReduce如何实现LSH？

How to implement LSH by MapReduce?

mapreduce