# 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:

-- 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

## 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模型，并与LSH等哈希方法做了比较，当时得出了结论，BOW就是一种经过学习的Hash函数. 去年再早些时候，又简单介绍过LLC等稀疏的表示模型，当时的相关论文几乎一致地得出结论，这些稀疏表示的方法在图像识别方面的性能一致地好于BOW的效果.

## Spark概览

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

- - 崔永键的博客

- - ITeye博客

- - CSDN博客推荐文章

## 局部敏感哈希开源项目和论文 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调优的一个实例分析：.

- - 开源小站