Уменьшение с помощью фильтра цветения

Question

Я хотел бы получить быстрое приближенное заданное членство, основанное на строковой функции, примененной к большому Spark RDD String Vectors (~ 1B records). В принципе идея заключалась бы в том, чтобы свести к нулю Bloom filter. Этот цветной фильтр затем может быть передан работникам для дальнейшего использования.

Более конкретно, я в настоящее время

rdd: RDD[Vector[String]] 
f: Vector[String] => String 
val uniqueVals = rdd.map(f).distinct().collect() 
val uv = sc.broadcast(uniqueVals) 

Но uniqueVals слишком велико, чтобы быть практичными, и я хотел бы заменить его чем-то меньшим (и известный) размера, т.е. в цвете фильтра.

Мои вопросы:

• является возможным уменьшить в фильтр Блума, или я должен собрать, а затем построить его в драйвере?

• Есть ли зрелая реализация фильтра Scala/Java Bloom, которая подходит для этого?

Answer 1

Да, фильтры Bloom могут быть уменьшены, потому что у них есть хорошие свойства (это monoids). Это означает, что вы можете выполнять все операции агрегации параллельно, эффективно используя только один проход над данными, чтобы построить BloomFilter для каждого раздела, а затем объединить эти BloomFilters, чтобы получить один BloomFilter, который вы можете запросить для contains.

Существует не менее двух реализаций BloomFilter в Scala, и оба они кажутся зрелыми проектами (фактически не использовали их в производстве). Первый - Breeze, а второй - Twitter's Algebird. Оба варианта содержат реализации разных эскизов и многое другое.

Это пример того, как сделать это с Breeze:

import breeze.util.BloomFilter 

val nums = List(1 to 20: _*).map(_.toString) 
val rdd = sc.parallelize(nums, 5) 

val bf = rdd.mapPartitions { iter => 
    val bf = BloomFilter.optimallySized[String](10000, 0.001) 
    iter.foreach(i => bf += i) 
    Iterator(bf) 
}.reduce(_ | _) 

println(bf.contains("5")) // true 
println(bf.contains("31")) // false