如何用MapReduce实现LSH

Question

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

（a） 展示如何将所有频段的bucket作为单个频段的输出MapReduce过程。提示：记住Map函数可以产生单个元素中的几个键值对。

（b） 展示另一个MapReduce进程如何将（a）的输出转换为需要比较的对的列表。具体地对于每列i，应该有一个列j>i的列表，我需要和这些列在一起比较。

Answer 1

（a）

• Map：元素及其签名作为输入，生成键值对（bucket_id，element）
• Reduce：生成所有频段的bucket作为输出，即。（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，即（bucket_id，list（elements））->（bucket_id，组合（list（elements）），哪个组合（）是任意两个元素从同一个桶中选择
• 减少：输出项目对需要比较，具体来说，对于每一列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)