LSH Spark 千万级用户/Item 相似度计算 cosine-lsh-join-spark: Approximate Nearest Neighbors in Spark

标签: | 发表时间:2018-08-03 15:32 | 作者:
出处:https://github.com

Cosine LSH Join Spark

A spark library for approximate nearest neighbours (ANN).

Background

In many computational problems such as NLP, Recommendation Systems and Search, items (e.g. words) are represented as vectors in a multidimensional space. Then given a specific item it's nearest neighbours need to be find e.g. given a query find the most similar ones. A naive liner scan over the data set might be too slow for most data sets.

Hence, more efficient algorithms are needed. One of the most widely used approaches is Locality Sensitive Hashing (LSH). This family of algorithms are very fast but might not give the exact solution and are hence called approximate nearest neighbours (ANN). The trade off between accuracy and speed is generally set via parameters of the algorithm.

Joiner Interface

This is an interface to find the k nearest neighbors from a data set for every other object in the same data set. Implementations may be either exact or approximate.

    trait Joiner {
    def join(matrix: IndexedRowMatrix): CoordinateMatrix
}

matrix is a row oriented matrix. Each row in the matrix represents an item in the dataset. Items are identified by their matrix index. Returns a similarity matrix with MatrixEntry(itemA, itemB, similarity).

Example

    // item_a --> (1.0, 1.0, 1.0)
// item_b --> (2.0, 2.0, 2.0)
// item_c --> (6.0, 3.0, 2.0)

val rows = Seq(
  IndexedRow(1, Vectors.dense(1.0, 1.0, 1.0)),
  IndexedRow(2, Vectors.dense(2.0, 2.0, 2.0)),
  IndexedRow(5, Vectors.dense(6.0, 3.0, 2.0))
)
val matrix = new IndexedRowMatrix(sc.parallelize(rows))
val similariyMatrix = joiner.join(matrix)

val results = similariyMatrix.entries.map {
      entry =>
        "item:%d item:%d cosine:%.2f".format(entry.i, entry.j, entry.value)
    }

results.foreach(println)

// above will print:
// item:2 item:3 cosine:0,87
// item:1 item:3 cosine:0,87
// item:1 item:2 cosine:1,00

Please see included Main.scalafile for a more detailed example.

Implementations of the joiner interface

LSH

This is an implementation of the following paper for Spark:

Randomized Algorithms and NLP: Using Locality Sensitive Hash Function for High Speed Noun Clustering

-- Ravichandran et al.

The algorithm determines a set of candidate items in the first stage and only computes the exact cosine similarity for those candidates. It has been succesfully used in production with typical run times of a couple of minutes for millions of items.

Note that candidates are ranked by their exact cosine similarity. Hence, this algorithm will not return any false positives (items that the system thinks are nearby but are actually not). Most real world applications require this e.g. in recommendation systems it is ok to return similar items which are almost as good as the exact nearest neighbours but showing false positives would result in senseless recommendations.

    val lsh = new Lsh(
  minCosineSimilarity = 0.5,
  dimensions = 2,
  numNeighbours = 3,
  numPermutations = 1,
  partitions = 1,
  storageLevel = StorageLevel.MEMORY_ONLY
)

Please see the original publication for a detailed description of the parameters.

NearestNeighbours

Brute force method to compute exact nearest neighbours. As this is a very expensive computation O(n^2) an additional sample parameter may be passed such that neighbours are just computed for a random fraction. This interface may be used to tune parameters for approximate solutions on a small subset of data.

QueryJoiner Interface

An interface to find the nearest neighbours in a catalog matrix for each entry in a query matrix. Implementations may be either exact or approximate.

    trait QueryJoiner {
  def join(queryMatrix: IndexedRowMatrix, catalogMatrix: IndexedRowMatrix): CoordinateMatrix
}

Implementations of the QueryJoiner Interface

QueryLsh

Standard Lsh implementation. A query matrix is hashed multiple times and exact hash matches are searched for in a catalog Matrix. These candidates are used to compute the exact cosine distance.

QueryHamming

Implementation based on approximated cosine distances. The cosine distances are approximated using hamming distances which are way faster to compute. The catalog matrix is broadcasted. This implementation is therefore suited for tasks where the catalog matrix is very small compared to the query matrix.

QueryNearestNeighbours

Brute force O(size(query) * size(catalog)) method to compute exact nearest neighbours for rows in the query matrix. As this is a very expensive computation additional sample parameters may be passed such that neighbours are just computed for a random fraction of the data set. This interface may be used to tune parameters for approximate solutions on a small subset of data.

Maven

The artifacts are hosted on Maven Central. For Spark 1.x add the following line to your build.sbt file:

    libraryDependencies += "com.soundcloud" % "cosine-lsh-join-spark_2.10" % "0.0.5"

For Spark 2.x use:

    libraryDependencies += "com.soundcloud" % "cosine-lsh-join-spark_2.10" % "1.0.1"

or if you're on scala 2.11.x use:

    libraryDependencies += "com.soundcloud" % "cosine-lsh-join-spark_2.11" % "1.0.1"

Releasing (maintainers only)

In order to release the library using the release plugin sbt release, you need to set up the following:

Contributors

Özgür Demir

Rany Keddo

Alexey Rodriguez Yakushev

Aaron Levin

相关 [lsh spark 千万] 推荐:

LSH Spark 千万级用户/Item 相似度计算 cosine-lsh-join-spark: Approximate Nearest Neighbors in Spark

- -
This family of algorithms are very fast but might not give the exact solution and are hence called approximate nearest neighbours (ANN). This is an interface to find the k nearest neighbors from a data set for every other object in the same data set.

图像检索中为什么仍用BOW和LSH

- - CSDN博客推荐文章
  去年年底的时候在一篇 博客中,用ANN的框架解释了BOW模型[1],并与LSH[2]等哈希方法做了比较,当时得出了结论,BOW就是一种经过学习的Hash函数. 去年再早些时候,又简单介绍过LLC[3]等稀疏的表示模型,当时的相关论文几乎一致地得出结论,这些稀疏表示的方法在图像识别方面的性能一致地好于BOW的效果.

Spark概览

- - 简单文本
Spark具有先进的DAG执行引擎,支持cyclic data flow和内存计算. 因此,它的运行速度,在内存中是Hadoop MapReduce的100倍,在磁盘中是10倍. 这样的性能指标,真的让人心动啊. Spark的API更为简单,提供了80个High Level的操作,可以很好地支持并行应用.

Spark与Mapreduce?

- - 崔永键的博客
我本人是类似Hive平台的系统工程师,我对MapReduce的熟悉程度是一般,它是我的底层框架. 我隔壁组在实验Spark,想将一部分计算迁移到Spark上. 年初的时候,看Spark的评价,几乎一致表示,Spark是小数据集上处理复杂迭代的交互系统,并不擅长大数据集,也没有稳定性. 但是最近的风评已经变化,尤其是14年10月他们完成了Peta sort的实验,这标志着Spark越来越接近替代Hadoop MapReduce了.

Spark迷思

- - ITeye博客
目前在媒体上有很大的关于Apache Spark框架的声音,渐渐的它成为了大数据领域的下一个大的东西. 证明这件事的最简单的方式就是看google的趋势图:. 上图展示的过去两年Hadoop和Spark的趋势. Spark在终端用户之间变得越来越受欢迎,而且这些用户经常在网上找Spark相关资料. 这给了Spark起了很大的宣传作用;同时围绕着它的也有误区和思维错误,而且很多人还把这些误区作为银弹,认为它可以解决他们的问题并提供比Hadoop好100倍的性能.

Spark 优化

- - CSDN博客推荐文章
提到Spark与Hadoop的区别,基本最常说的就是Spark采用基于内存的计算方式,尽管这种方式对数据处理的效率很高,但也会往往引发各种各样的问题,Spark中常见的OOM等等. 效率高的特点,注定了Spark对性能的严苛要求,那Spark不同程序的性能会碰到不同的资源瓶颈,比如:CPU,带宽、内存.

局部敏感哈希开源项目和论文 Locality-Sensitive Hashing (LSH) · Jian Zhou

- -
Although no single definition of a similarity measure exists, usually such measures are in some sense the inverse of distance metrics.. JorenSix/TarsosLSHA Java library implementing Locality-sensitive Hashing (LSH), a practical nearest neighbour search algorithm for multidimensional vectors that operates in sublinear time..

Spark&Spark性能调优实战

- - CSDN博客互联网推荐文章
       Spark特别适用于多次操作特定的数据,分mem-only和mem & disk. 其中mem-only:效率高,但占用大量的内存,成本很高;mem & disk:内存用完后,会自动向磁盘迁移,解决了内存不足的问题,却带来了数据的置换的消费. Spark常见的调优工具有nman、Jmeter和Jprofile,以下是Spark调优的一个实例分析:.

Mesos上部署spark

- - 开源小站
还是回到之前一直持续的 Mesos话题. 在之前的环节里,我们已经尝试了Mesos的安装,Marathon守护服务以及相对比较主流的Mesos作为Hadoop的资源管理器的实际操作. 这次就说说同属于伯克利出品的Spark. 其实spark最初0.7以前的版本还没有自己的资源管理系统,资源的调度都是通过Mesos来执行的.

Spark容错机制

- - zzm
一般来说,分布式数据集的容错性有两种方式: 数据检查点和记录数据的更新. 面向大规模数据分析,数据检查点操作成本很高,需要通过数据中心的网络连接在机器之间复制庞大的数据集,而网络带宽往往比内存带宽低得多,同时还需要消耗更多的存储资源. 因此,Spark选择记录更新的方式. 但是,如果更新粒度太细太多,那么记录更新成本也不低.