You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by Yunni <gi...@git.apache.org> on 2016/11/14 04:43:57 UTC
[GitHub] spark pull request #15874: Spark 18408 yunn api improvements
GitHub user Yunni opened a pull request:
https://github.com/apache/spark/pull/15874
Spark 18408 yunn api improvements
## What changes were proposed in this pull request?
(1) Change output schema to `Array of Vector` instead of `Vectors`
(2) Use `numHashTables` as the dimension of Array and `numHashFunctions` as the dimension of Vector
(3) Rename `RandomProjection` to `BucketedRandomProjectionLSH`, `MinHash` to `MinHashLSH`
(4) Make `randUnitVectors/randCoefficients` private
(5) Make Multi-Probe NN Search and `hashDistance` private for future discussion
## How was this patch tested?
Related unit tests are modified to make sure the performance of LSH are ensured, and the outputs of the APIs meets expectation.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/Yunni/spark SPARK-18408-yunn-api-improvements
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/spark/pull/15874.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #15874
----
commit 559c09904538012b70bcb3493b8bc287dd855b2d
Author: Yun Ni <yu...@uber.com>
Date: 2016-11-07T21:30:32Z
[SPARK-18334] MinHash should use binary hash distance
commit 517a97bd16f3771d9abbcdf54957a011f5f87adc
Author: Yunni <eu...@gmail.com>
Date: 2016-11-08T06:15:24Z
Remove misleading documentation as requested
commit b546dbd207a04e73bde097f25cae8c927322c2ae
Author: Yun Ni <yu...@uber.com>
Date: 2016-11-08T18:54:09Z
Add warning for multi-probe in MinHash
commit a3cd9281d1fb8d969cb8bdd32ae8c5b9c373ad3b
Author: Yun Ni <yu...@uber.com>
Date: 2016-11-08T18:55:49Z
Merge branch 'SPARK-18334-yunn-minhash-bug' of https://github.com/Yunni/spark into SPARK-18334-yunn-minhash-bug
commit c8243c7def8c270072edd5889cea7fd02677b44f
Author: Yun Ni <yu...@uber.com>
Date: 2016-11-09T23:11:20Z
(1) Fix documentation as CR suggested (2) Fix typo in unit test
commit 6aac8b343c5ea3a91b8517a2d3f47ed055ece9ad
Author: Yun Ni <yu...@uber.com>
Date: 2016-11-09T23:22:27Z
Fix typo in unit test
commit 98707436ea8a90599fd8615a47afff3bf29a3ae6
Author: Yun Ni <yu...@uber.com>
Date: 2016-11-14T04:25:17Z
[SPARK-18408] API Improvements for LSH
commit 0e9250be0142691e9e085ed1260f83f8ed40f5e4
Author: Yun Ni <yu...@uber.com>
Date: 2016-11-14T04:38:44Z
(1) Fix description for numHashFunctions (2) Make numEntries in MinHash private
commit adbbefe1777db8fb85a0af59c11e5840d3bc91ee
Author: Yun Ni <yu...@uber.com>
Date: 2016-11-14T04:43:30Z
Add assertion for hashFunction in BucketedRandomProjectionLSHSuite
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88128199
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -31,13 +31,9 @@ import org.apache.spark.sql.types.StructType
/**
* :: Experimental ::
*
- * Model produced by [[MinHash]], where multiple hash functions are stored. Each hash function is
- * a perfect hash function:
- * `h_i(x) = (x * k_i mod prime) mod numEntries`
- * where `k_i` is the i-th coefficient, and both `x` and `k_i` are from `Z_prime^*`
- *
- * Reference:
- * [[https://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia on Perfect Hash Function]]
+ * Model produced by [[MinHashLSH]], where multiple hash functions are stored. Each hash function is
+ * a perfect hash function for a specific set `S` with cardinality equal to a half of `numEntries`:
--- End diff --
You are right. Actually the correct universal hash function is (ax+b) % p % m (https://en.wikipedia.org/wiki/Universal_hashing#Hashing_integers), which is approximately
min-wise independent families (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.8215&rep=rep1&type=pdf)
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88128823
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ---
@@ -66,10 +66,10 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]]
self: T =>
/**
- * The hash function of LSH, mapping a predefined KeyType to a Vector
+ * The hash function of LSH, mapping an input feature to multiple vectors
--- End diff --
Fixed
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88128341
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -74,9 +72,12 @@ class MinHashModel private[ml] (
}
@Since("2.1.0")
- override protected[ml] def hashDistance(x: Vector, y: Vector): Double = {
+ override protected[ml] def hashDistance(x: Seq[Vector], y: Seq[Vector]): Double = {
// Since it's generated by hashing, it will be a pair of dense vectors.
- x.toDense.values.zip(y.toDense.values).map(pair => math.abs(pair._1 - pair._2)).min
+ // TODO: This hashDistance function is controversial. Requires more discussion.
--- End diff --
JIRA opened and linked
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on the issue:
https://github.com/apache/spark/pull/15874
Hi @sethah, grouping to a number of buckets does not really affect the independence since p is a mach larger prime. For example, in http://people.csail.mit.edu/mip/papers/kwise-lb/kwise-lb.pdf, they use "mod b".
Since we don't care about the hash universe here, I am OK with changing to `(ax + b mod p)` if you think that makes more sense?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88351984
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -31,36 +31,34 @@ import org.apache.spark.sql.types.StructType
/**
* :: Experimental ::
*
- * Model produced by [[MinHash]], where multiple hash functions are stored. Each hash function is
- * a perfect hash function:
- * `h_i(x) = (x * k_i mod prime) mod numEntries`
- * where `k_i` is the i-th coefficient, and both `x` and `k_i` are from `Z_prime^*`
- *
- * Reference:
- * [[https://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia on Perfect Hash Function]]
+ * Model produced by [[MinHashLSH]], where multiple hash functions are stored. Each hash function is
+ * a perfect hash function for a specific set `S` with cardinality equal to `numEntries`:
+ * `h_i(x) = ((x \cdot a_i + b_i) \mod prime) \mod numEntries`
*
* @param numEntries The number of entries of the hash functions.
* @param randCoefficients An array of random coefficients, each used by one hash function.
--- End diff --
Need to update description
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88142430
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ---
@@ -179,16 +211,13 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]]
inputName: String,
explodeCols: Seq[String]): Dataset[_] = {
require(explodeCols.size == 2, "explodeCols must be two strings.")
- val vectorToMap = udf((x: Vector) => x.asBreeze.iterator.toMap,
- MapType(DataTypes.IntegerType, DataTypes.DoubleType))
val modelDataset: DataFrame = if (!dataset.columns.contains($(outputCol))) {
transform(dataset)
} else {
dataset.toDF()
}
modelDataset.select(
- struct(col("*")).as(inputName),
- explode(vectorToMap(col($(outputCol)))).as(explodeCols))
+ struct(col("*")).as(inputName), posexplode(col($(outputCol))).as(explodeCols))
--- End diff --
Yeah I still get it. Did you use the code above? It's not directly copy pasted from the existing tests.
````
- memory leak test *** FAILED *** (8 seconds, 938 milliseconds)
[info] org.apache.spark.SparkException: Job aborted due to stage failure: Task 0 in stage 3.0 failed 1 times, most recent failure: Lost task 0.0 in stage 3.0 (TID 204, localhost, executor driver): org.apache.spark.SparkException: Managed memory leak detected; size = 33816576 bytes, TID = 204
[info] at org.apache.spark.executor.Executor$TaskRunner.run(Executor.scala:295)
[info] at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
[info] at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
[info] at java.lang.Thread.run(Thread.java:745)
[info]
[info] Driver stacktrace:
[info] at org.apache.spark.scheduler.DAGScheduler.org$apache$spark$scheduler$DAGScheduler$$failJobAndIndependentStages(DAGScheduler.scala:1435)
[info] at org.apache.spark.scheduler.DAGScheduler$$anonfun$abortStage$1.apply(DAGScheduler.scala:1423)
[info] at org.apache.spark.scheduler.DAGScheduler$$anonfun$abortStage$1.apply(DAGScheduler.scala:1422)
[info] at scala.collection.mutable.ResizableArray$class.foreach(ResizableArray.scala:59)
[info] at scala.collection.mutable.ArrayBuffer.foreach(ArrayBuffer.scala:48)
[info] at org.apache.spark.scheduler.DAGScheduler.abortStage(DAGScheduler.scala:1422)
[info] at org.apache.spark.scheduler.DAGScheduler$$anonfun$handleTaskSetFailed$1.apply(DAGScheduler.scala:802)
[info] at org.apache.spark.scheduler.DAGScheduler$$anonfun$handleTaskSetFailed$1.apply(DAGScheduler.scala:802)
[info] at scala.Option.foreach(Option.scala:257)
[info] at org.apache.spark.scheduler.DAGScheduler.handleTaskSetFailed(DAGScheduler.scala:802)
[info] at org.apache.spark.scheduler.DAGSchedulerEventProcessLoop.doOnReceive(DAGScheduler.scala:1650)
[info] at org.apache.spark.scheduler.DAGSchedulerEventProcessLoop.onReceive(DAGScheduler.scala:1605)
[info] at org.apache.spark.scheduler.DAGSchedulerEventProcessLoop.onReceive(DAGScheduler.scala:1594)
[info] at org.apache.spark.util.EventLoop$$anon$1.run(EventLoop.scala:48)
[info] at org.apache.spark.scheduler.DAGScheduler.runJob(DAGScheduler.scala:628)
[info] at org.apache.spark.SparkContext.runJob(SparkContext.scala:1896)
[info] at org.apache.spark.SparkContext.runJob(SparkContext.scala:1909)
[info] at org.apache.spark.SparkContext.runJob(SparkContext.scala:1922)
[info] at org.apache.spark.sql.execution.SparkPlan.executeTake(SparkPlan.scala:333)
[info] at org.apache.spark.sql.execution.CollectLimitExec.executeCollect(limit.scala:38)
[info] at org.apache.spark.sql.Dataset$$anonfun$org$apache$spark$sql$Dataset$$execute$1$1.apply(Dataset.scala:2323)
[info] at org.apache.spark.sql.execution.SQLExecution$.withNewExecutionId(SQLExecution.scala:57)
[info] at org.apache.spark.sql.Dataset.withNewExecutionId(Dataset.scala:2717)
[info] at org.apache.spark.sql.Dataset.org$apache$spark$sql$Dataset$$execute$1(Dataset.scala:2322)
[info] at org.apache.spark.sql.Dataset.org$apache$spark$sql$Dataset$$collect(Dataset.scala:2329)
[info] at org.apache.spark.sql.Dataset$$anonfun$head$1.apply(Dataset.scala:2065)
[info] at org.apache.spark.sql.Dataset$$anonfun$head$1.apply(Dataset.scala:2064)
[info] at org.apache.spark.sql.Dataset.withTypedCallback(Dataset.scala:2747)
[info] at org.apache.spark.sql.Dataset.head(Dataset.scala:2064)
[info] at org.apache.spark.sql.Dataset.take(Dataset.scala:2279)
[info] at org.apache.spark.sql.Dataset.showString(Dataset.scala:247)
[info] at org.apache.spark.sql.Dataset.show(Dataset.scala:596)
[info] at org.apache.spark.sql.Dataset.show(Dataset.scala:555)
[info] at org.apache.spark.sql.Dataset.show(Dataset.scala:564)
[info] at org.apache.spark.ml.feature.BucketedRandomProjectionLSHSuite$$anonfun$3.apply$mcV$sp(BucketedRandomProjectionLSHSuite.scala:74)
````
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Merged build finished. Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/68803/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68625 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68625/consoleFull)** for PR 15874 at commit [`c115ed3`](https://github.com/apache/spark/commit/c115ed3e580d4999c85d02417356e66f8f360bda).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the issue:
https://github.com/apache/spark/pull/15874
I'll take a look
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on the issue:
https://github.com/apache/spark/pull/15874
Thanks @yunni, I can take a look at this today. I would prefer to separate the addition of "AND-amplification" into another PR since the other changes I believe we'd like to get into 2.1, whereas the "AND-amplification" is not as urgent. That will make this easier to review and get merged in a timely manner. I'm open to other arguments, though.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/69020/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on the issue:
https://github.com/apache/spark/pull/15874
@jkbradley Thanks for checking that, that is the conclusion I drew as well.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88753014
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -31,36 +31,40 @@ import org.apache.spark.sql.types.StructType
/**
* :: Experimental ::
*
- * Model produced by [[MinHash]], where multiple hash functions are stored. Each hash function is
- * a perfect hash function:
- * `h_i(x) = (x * k_i mod prime) mod numEntries`
- * where `k_i` is the i-th coefficient, and both `x` and `k_i` are from `Z_prime^*`
+ * Model produced by [[MinHashLSH]], where multiple hash functions are stored. Each hash function is
+ * picked from a hash family for a specific set `S` with cardinality equal to `numEntries`:
+ * `h_i(x) = ((x \cdot a_i + b_i) \mod prime) \mod numEntries`
+ *
+ * This hash family is approximately min-wise independent according to the reference.
*
* Reference:
- * [[https://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia on Perfect Hash Function]]
+ * [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.8215&rep=rep1&type=pdf Min-wise
+ * independent permutations]]
*
* @param numEntries The number of entries of the hash functions.
- * @param randCoefficients An array of random coefficients, each used by one hash function.
+ * @param randCoefficients Pairs of random coefficients. Each pair is used by one hash function.
*/
@Experimental
@Since("2.1.0")
-class MinHashModel private[ml] (
+class MinHashLSHModel private[ml](
override val uid: String,
- @Since("2.1.0") val numEntries: Int,
- @Since("2.1.0") val randCoefficients: Array[Int])
- extends LSHModel[MinHashModel] {
+ private[ml] val numEntries: Int,
+ private[ml] val randCoefficients: Array[(Int, Int)])
+ extends LSHModel[MinHashLSHModel] {
@Since("2.1.0")
- override protected[ml] val hashFunction: Vector => Vector = {
- elems: Vector =>
+ override protected[ml] val hashFunction: Vector => Array[Vector] = {
+ elems: Vector => {
require(elems.numNonzeros > 0, "Must have at least 1 non zero entry.")
val elemsList = elems.toSparse.indices.toList
- val hashValues = randCoefficients.map({ randCoefficient: Int =>
- elemsList.map({elem: Int =>
- (1 + elem) * randCoefficient.toLong % MinHash.prime % numEntries
- }).min.toDouble
+ val hashValues = randCoefficients.map({ case (a: Int, b: Int) =>
+ elemsList.map { elem: Int =>
+ ((1 + elem) * a + b) % MinHashLSH.HASH_PRIME % numEntries
--- End diff --
I'm still looking at it, but I don't think this is correct. Why do we tack on `% numEntries` here. Could you point me to a resource? The paper linked above (and many other references that I've seen) use `(ax + b) mod p` where p is a large prime.
I see the formula listed under the wiki article for [perfect hashing functions](https://en.wikipedia.org/wiki/Perfect_hash_function) lists `(kx mod p) mod n`, but that's not the full picture. They are referencing a paper which simply uses that formula as the first part of multilevel scheme.
If it's helpful - [this](http://cs.brown.edu/courses/cs253/papers/nearduplicate.pdf) seems to be the original paper on MinHash. The author mentions that
````
This is further explored in [5] where it is shown
that random linear transformations are likely to suffice in practice.
````
Reference 5 is [here](http://www.combinatorics.org/ojs/index.php/eljc/article/download/v7i1r26/pdf), which seems to be a more concise version of your reference. In that paper, they describe `(ax + b mod p)`.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/68880/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68689 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68689/consoleFull)** for PR 15874 at commit [`d759875`](https://github.com/apache/spark/commit/d75987591c68aaae5bd007a92f3587193edd7b2a).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/68802/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88349223
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/BucketedRandomProjectionLSH.scala ---
@@ -147,15 +151,17 @@ class RandomProjection(override val uid: String) extends LSH[RandomProjectionMod
def setSeed(value: Long): this.type = set(seed, value)
@Since("2.1.0")
- override protected[this] def createRawLSHModel(inputDim: Int): RandomProjectionModel = {
+ override protected[this] def createRawLSHModel(
+ inputDim: Int
+ ): BucketedRandomProjectionLSHModel = {
--- End diff --
style nit: This should go on the previous line.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88129663
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ---
@@ -179,16 +211,13 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]]
inputName: String,
explodeCols: Seq[String]): Dataset[_] = {
require(explodeCols.size == 2, "explodeCols must be two strings.")
- val vectorToMap = udf((x: Vector) => x.asBreeze.iterator.toMap,
- MapType(DataTypes.IntegerType, DataTypes.DoubleType))
val modelDataset: DataFrame = if (!dataset.columns.contains($(outputCol))) {
transform(dataset)
} else {
dataset.toDF()
}
modelDataset.select(
- struct(col("*")).as(inputName),
- explode(vectorToMap(col($(outputCol)))).as(explodeCols))
+ struct(col("*")).as(inputName), posexplode(col($(outputCol))).as(explodeCols))
--- End diff --
I did not get the same error, could you provide me with the full stack of the Exception?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89175438
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ---
@@ -155,8 +148,30 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]]
}
/**
- * Overloaded method for approxNearestNeighbors. Use Single Probing as default way to search
- * nearest neighbors and "distCol" as default distCol.
+ * Given a large dataset and an item, approximately find at most k items which have the closest
+ * distance to the item. If the [[outputCol]] is missing, the method will transform the data; if
+ * the [[outputCol]] exists, it will use the [[outputCol]]. This allows caching of the
+ * transformed data when necessary.
+ *
+ * NOTE: This method is experimental and will likely change behavior in the next release.
--- End diff --
Done.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89175473
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ---
@@ -155,8 +148,30 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]]
}
/**
- * Overloaded method for approxNearestNeighbors. Use Single Probing as default way to search
- * nearest neighbors and "distCol" as default distCol.
+ * Given a large dataset and an item, approximately find at most k items which have the closest
+ * distance to the item. If the [[outputCol]] is missing, the method will transform the data; if
+ * the [[outputCol]] exists, it will use the [[outputCol]]. This allows caching of the
+ * transformed data when necessary.
+ *
+ * NOTE: This method is experimental and will likely change behavior in the next release.
+ *
+ * @param dataset the dataset to search for nearest neighbors of the key
+ * @param key Feature vector representing the item to search for
+ * @param numNearestNeighbors The maximum number of nearest neighbors
+ * @param distCol Output column for storing the distance between each result row and the key
+ * @return A dataset containing at most k items closest to the key. A distCol is added to show
--- End diff --
Done.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/68825/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #69031 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/69031/consoleFull)** for PR 15874 at commit [`f0ebcb7`](https://github.com/apache/spark/commit/f0ebcb736634c02c59bc50760c53dfcad21fc5d9).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89015206
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -31,36 +31,38 @@ import org.apache.spark.sql.types.StructType
/**
* :: Experimental ::
*
- * Model produced by [[MinHash]], where multiple hash functions are stored. Each hash function is
- * a perfect hash function:
- * `h_i(x) = (x * k_i mod prime) mod numEntries`
- * where `k_i` is the i-th coefficient, and both `x` and `k_i` are from `Z_prime^*`
+ * Model produced by [[MinHashLSH]], where multiple hash functions are stored. Each hash function is
+ * picked from a hash family for a specific set `S` with cardinality equal to `numEntries`:
+ * `h_i(x) = ((x \cdot a_i + b_i) \mod prime) \mod numEntries`
--- End diff --
We should remove the `numEntries` part here if we have removed it from the code. I still haven't gotten around to properly digging into this. For now, I'd like to change the second sentence to: "Each hash function is picked from the following family of hash functions, where `a_i` and `b_i` are randomly chosen integers less than `prime`:"
And I prefer this paper: "http://www.combinatorics.org/ojs/index.php/eljc/article/download/v7i1r26/pdf" as a reference because it is concise and easier to parse. That said, since it's a direct download link we could maybe not put the link in the doc, and just list the reference.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88569315
--- Diff: mllib/src/test/scala/org/apache/spark/ml/feature/BucketedRandomProjectionLSHSuite.scala ---
@@ -115,64 +117,83 @@ class RandomProjectionSuite
val df = spark.createDataFrame(data.map(Tuple1.apply)).toDF("keys")
// Project from 100 dimensional Euclidean Space to 10 dimensions
- val rp = new RandomProjection()
- .setOutputDim(10)
+ val brp = new BucketedRandomProjectionLSH()
+ .setNumHashTables(10)
.setInputCol("keys")
.setOutputCol("values")
.setBucketLength(2.5)
.setSeed(12345)
- val (falsePositive, falseNegative) = LSHTest.calculateLSHProperty(df, rp, 3.0, 2.0)
+ val (falsePositive, falseNegative) = LSHTest.calculateLSHProperty(df, brp, 3.0, 2.0)
assert(falsePositive < 0.3)
assert(falseNegative < 0.3)
}
- test("approxNearestNeighbors for random projection") {
+ test("approxNearestNeighbors for bucketed random projection") {
val key = Vectors.dense(1.2, 3.4)
- val rp = new RandomProjection()
- .setOutputDim(2)
+ val brp = new BucketedRandomProjectionLSH()
+ .setNumHashTables(2)
.setInputCol("keys")
.setOutputCol("values")
.setBucketLength(4.0)
.setSeed(12345)
- val (precision, recall) = LSHTest.calculateApproxNearestNeighbors(rp, dataset, key, 100,
- singleProbing = true)
+ val (precision, recall) = LSHTest.calculateApproxNearestNeighbors(brp, dataset, key, 100,
+ singleProbe = true)
assert(precision >= 0.6)
assert(recall >= 0.6)
}
test("approxNearestNeighbors with multiple probing") {
val key = Vectors.dense(1.2, 3.4)
- val rp = new RandomProjection()
- .setOutputDim(20)
+ val brp = new BucketedRandomProjectionLSH()
+ .setNumHashTables(20)
.setInputCol("keys")
.setOutputCol("values")
.setBucketLength(1.0)
.setSeed(12345)
- val (precision, recall) = LSHTest.calculateApproxNearestNeighbors(rp, dataset, key, 100,
- singleProbing = false)
+ val (precision, recall) = LSHTest.calculateApproxNearestNeighbors(brp, dataset, key, 100,
+ singleProbe = false)
assert(precision >= 0.7)
assert(recall >= 0.7)
}
- test("approxSimilarityJoin for random projection on different dataset") {
+ test("approxNearestNeighbors for numNeighbors <= 0") {
+ val key = Vectors.dense(1.2, 3.4)
+
+ val brp = new BucketedRandomProjectionLSH()
+ .setNumHashTables(20)
--- End diff --
Removed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/68683/
Test FAILed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on the issue:
https://github.com/apache/spark/pull/15874
Hi @jkbradley,
**MinHash**
Yes, I agree that I shouldn't have said it's perfect hashing. Theoretically, it should be Min-wise Independent Permutation Family. What we used here is 2-independent (or 2-universal) hash families, which is approximately min-wise independent.
Reference: http://people.csail.mit.edu/mip/papers/kwise-lb/kwise-lb.pdf
**approxNearestNeighbors**
I still think in the case of OR-amplification, the only way is to scan a number of candidates k times the average bucket size. I would like to understand more about what you proposed. I have left the note in the scaladoc and let us have more discussion in future releases.
**AND-amplification**
I've open a ticket in SPARK-18450 for AND-amplification. I am wondering if we are including it in 2.1.0?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408] API Improvements for LSH
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the issue:
https://github.com/apache/spark/pull/15874
Can you please add "[ML]" to the PR title?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r87908012
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -125,11 +125,11 @@ class MinHash(override val uid: String) extends LSH[MinHashModel] with HasSeed {
@Since("2.1.0")
override protected[ml] def createRawLSHModel(inputDim: Int): MinHashModel = {
- require(inputDim <= MinHash.prime / 2,
- s"The input vector dimension $inputDim exceeds the threshold ${MinHash.prime / 2}.")
+ require(inputDim <= MinHashLSH.prime / 2,
+ s"The input vector dimension $inputDim exceeds the threshold ${MinHashLSH.prime / 2}.")
val rand = new Random($(seed))
val numEntry = inputDim * 2
- val randCoofs: Array[Int] = Array.fill($(outputDim))(1 + rand.nextInt(MinHash.prime - 1))
+ val randCoofs: Array[Int] = Array.fill($(numHashTables))(1 + rand.nextInt(MinHashLSH.prime - 1))
--- End diff --
`randCoefs`
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/68601/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88351861
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -31,36 +31,34 @@ import org.apache.spark.sql.types.StructType
/**
* :: Experimental ::
*
- * Model produced by [[MinHash]], where multiple hash functions are stored. Each hash function is
- * a perfect hash function:
- * `h_i(x) = (x * k_i mod prime) mod numEntries`
- * where `k_i` is the i-th coefficient, and both `x` and `k_i` are from `Z_prime^*`
- *
- * Reference:
- * [[https://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia on Perfect Hash Function]]
+ * Model produced by [[MinHashLSH]], where multiple hash functions are stored. Each hash function is
+ * a perfect hash function for a specific set `S` with cardinality equal to `numEntries`:
--- End diff --
Looking more at the Wikipedia entry, I'm still doubtful about whether this is a perfect hash function. It looks like the first of 2 parts in the construction of a perfect hash function. I also still don't see why mentioning "perfect hash functions" will help users.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on the issue:
https://github.com/apache/spark/pull/15874
LGTM. I think we've made JIRAs for all of the follow-up items. Thanks!
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88129780
--- Diff: mllib/src/test/scala/org/apache/spark/ml/feature/MinHashLSHSuite.scala ---
@@ -24,7 +24,7 @@ import org.apache.spark.ml.util.DefaultReadWriteTest
import org.apache.spark.mllib.util.MLlibTestSparkContext
import org.apache.spark.sql.Dataset
-class MinHashSuite extends SparkFunSuite with MLlibTestSparkContext with DefaultReadWriteTest {
+class MinHashLSHSuite extends SparkFunSuite with MLlibTestSparkContext with DefaultReadWriteTest {
--- End diff --
4 new tests are added.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Merged build finished. Test FAILed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89215142
--- Diff: mllib/src/test/scala/org/apache/spark/ml/feature/MinHashLSHSuite.scala ---
@@ -97,12 +118,31 @@ class MinHashSuite extends SparkFunSuite with MLlibTestSparkContext with Default
(0 until 100).filter(_.toString.contains("1")).map((_, 1.0)))
val (precision, recall) = LSHTest.calculateApproxNearestNeighbors(mh, dataset, key, 20,
- singleProbing = true)
+ singleProbe = true)
assert(precision >= 0.7)
assert(recall >= 0.7)
}
- test("approxSimilarityJoin for minhash on different dataset") {
+ test("approxNearestNeighbors for numNeighbors <= 0") {
+ val mh = new MinHashLSH()
+ .setNumHashTables(20)
+ .setInputCol("keys")
+ .setOutputCol("values")
+ .setSeed(12345)
+
+ val key: Vector = Vectors.sparse(100,
+ (0 until 100).filter(_.toString.contains("1")).map((_, 1.0)))
+
+ val model = mh.fit(dataset)
--- End diff --
Done.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68683 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68683/consoleFull)** for PR 15874 at commit [`c597f4c`](https://github.com/apache/spark/commit/c597f4c83519af38a9749acd71078ac20ef20c14).
* This patch **fails Spark unit tests**.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89215405
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -31,36 +31,38 @@ import org.apache.spark.sql.types.StructType
/**
* :: Experimental ::
*
- * Model produced by [[MinHash]], where multiple hash functions are stored. Each hash function is
- * a perfect hash function:
- * `h_i(x) = (x * k_i mod prime) mod numEntries`
- * where `k_i` is the i-th coefficient, and both `x` and `k_i` are from `Z_prime^*`
+ * Model produced by [[MinHashLSH]], where multiple hash functions are stored. Each hash function is
+ * picked from a hash family for a specific set `S` with cardinality equal to `numEntries`:
+ * `h_i(x) = ((x \cdot a_i + b_i) \mod prime) \mod numEntries`
+ *
+ * This hash family is approximately min-wise independent according to the reference.
*
* Reference:
- * [[https://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia on Perfect Hash Function]]
+ * [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.8215&rep=rep1&type=pdf Min-wise
+ * independent permutations]]
*
- * @param numEntries The number of entries of the hash functions.
- * @param randCoefficients An array of random coefficients, each used by one hash function.
+ * @param randCoefficients Pairs of random coefficients. Each pair is used by one hash function.
*/
@Experimental
@Since("2.1.0")
-class MinHashModel private[ml] (
+class MinHashLSHModel private[ml](
override val uid: String,
- @Since("2.1.0") val numEntries: Int,
- @Since("2.1.0") val randCoefficients: Array[Int])
- extends LSHModel[MinHashModel] {
+ private[ml] val randCoefficients: Array[(Int, Int)])
+ extends LSHModel[MinHashLSHModel] {
@Since("2.1.0")
- override protected[ml] val hashFunction: Vector => Vector = {
- elems: Vector =>
+ override protected[ml] val hashFunction: Vector => Array[Vector] = {
+ elems: Vector => {
require(elems.numNonzeros > 0, "Must have at least 1 non zero entry.")
val elemsList = elems.toSparse.indices.toList
- val hashValues = randCoefficients.map({ randCoefficient: Int =>
- elemsList.map({elem: Int =>
- (1 + elem) * randCoefficient.toLong % MinHash.prime % numEntries
- }).min.toDouble
+ val hashValues = randCoefficients.map({ case (a: Int, b: Int) =>
+ elemsList.map { elem: Int =>
+ ((1 + elem) * a + b) % MinHashLSH.HASH_PRIME
+ }.min.toDouble
})
- Vectors.dense(hashValues)
+ // TODO: Output vectors of dimension numHashFunctions in SPARK-18450
+ hashValues.grouped(1).map(Vectors.dense).toArray
--- End diff --
I see. It's `dense(firstValue: Double, otherValues: Double*)`.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #69012 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/69012/consoleFull)** for PR 15874 at commit [`939e9d5`](https://github.com/apache/spark/commit/939e9d5ca94607604909da0fab6cb5e06865d104).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Merged build finished. Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68803 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68803/consoleFull)** for PR 15874 at commit [`3d0810f`](https://github.com/apache/spark/commit/3d0810f25e22f6b8d64a907ade9cca14de7be763).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #69215 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/69215/consoleFull)** for PR 15874 at commit [`e198080`](https://github.com/apache/spark/commit/e198080557c598286363184855a6f368d60b45e3).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68823 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68823/consoleFull)** for PR 15874 at commit [`257ef19`](https://github.com/apache/spark/commit/257ef1955696b937a0b53feb0ebde136f482dae1).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88569056
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/BucketedRandomProjectionLSH.scala ---
@@ -147,15 +151,17 @@ class RandomProjection(override val uid: String) extends LSH[RandomProjectionMod
def setSeed(value: Long): this.type = set(seed, value)
@Since("2.1.0")
- override protected[this] def createRawLSHModel(inputDim: Int): RandomProjectionModel = {
+ override protected[this] def createRawLSHModel(
+ inputDim: Int
+ ): BucketedRandomProjectionLSHModel = {
--- End diff --
Done.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on the issue:
https://github.com/apache/spark/pull/15874
@sethah PTAL
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r87844941
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ---
@@ -106,22 +123,24 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]]
* transformed data when necessary.
*
* This method implements two ways of fetching k nearest neighbors:
- * - Single Probing: Fast, return at most k elements (Probing only one buckets)
- * - Multiple Probing: Slow, return exact k elements (Probing multiple buckets close to the key)
+ * - Single-probe: Fast, return at most k elements (Probing only one buckets)
--- End diff --
"Probing only one bucket"
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68825 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68825/consoleFull)** for PR 15874 at commit [`2c264b7`](https://github.com/apache/spark/commit/2c264b7660d8be68428f573be67f2720ee9a3c51).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r87874869
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ---
@@ -66,10 +66,10 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]]
self: T =>
/**
- * The hash function of LSH, mapping a predefined KeyType to a Vector
+ * The hash function of LSH, mapping an input feature to multiple vectors
--- End diff --
"mapping an input feature vector to multiple hash vectors."
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r87874663
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ---
@@ -35,26 +35,26 @@ private[ml] trait LSHParams extends HasInputCol with HasOutputCol {
/**
* Param for the dimension of LSH OR-amplification.
*
- * In this implementation, we use LSH OR-amplification to reduce the false negative rate. The
- * higher the dimension is, the lower the false negative rate.
+ * LSH OR-amplification can be used to reduce the false negative rate. The higher the dimension
--- End diff --
We are still using the word "dimension" here. It might also be useful to add that reducing false negatives comes at the cost of added computation. How does this sound?
````
* Param for the number of hash tables used in LSH OR-amplification.
*
* LSH OR-amplification can be used to reduce the false negative rate. Higher values for this
* param lead to a reduced false negative rate, at the expense of added computational complexity.
````
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89013407
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ---
@@ -155,8 +148,30 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]]
}
/**
- * Overloaded method for approxNearestNeighbors. Use Single Probing as default way to search
- * nearest neighbors and "distCol" as default distCol.
+ * Given a large dataset and an item, approximately find at most k items which have the closest
+ * distance to the item. If the [[outputCol]] is missing, the method will transform the data; if
+ * the [[outputCol]] exists, it will use the [[outputCol]]. This allows caching of the
+ * transformed data when necessary.
+ *
+ * NOTE: This method is experimental and will likely change behavior in the next release.
+ *
+ * @param dataset the dataset to search for nearest neighbors of the key
+ * @param key Feature vector representing the item to search for
+ * @param numNearestNeighbors The maximum number of nearest neighbors
+ * @param distCol Output column for storing the distance between each result row and the key
+ * @return A dataset containing at most k items closest to the key. A distCol is added to show
--- End diff --
minor: `A column "distCol" is added ...`
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r87906709
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -46,21 +42,23 @@ import org.apache.spark.sql.types.StructType
@Since("2.1.0")
class MinHashModel private[ml] (
override val uid: String,
- @Since("2.1.0") val numEntries: Int,
- @Since("2.1.0") val randCoefficients: Array[Int])
+ @Since("2.1.0") private[ml] val numEntries: Int,
--- End diff --
no since tags for private values.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/68689/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/69215/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/68625/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68825 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68825/consoleFull)** for PR 15874 at commit [`2c264b7`](https://github.com/apache/spark/commit/2c264b7660d8be68428f573be67f2720ee9a3c51).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by MLnick <gi...@git.apache.org>.
Github user MLnick commented on the issue:
https://github.com/apache/spark/pull/15874
@Yunni I think if we are using this 2-independent hash family we should provide that reference you mention in the Scaladoc, and also mention it approximates min-wise independent.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89015678
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -31,36 +31,38 @@ import org.apache.spark.sql.types.StructType
/**
* :: Experimental ::
*
- * Model produced by [[MinHash]], where multiple hash functions are stored. Each hash function is
- * a perfect hash function:
- * `h_i(x) = (x * k_i mod prime) mod numEntries`
- * where `k_i` is the i-th coefficient, and both `x` and `k_i` are from `Z_prime^*`
+ * Model produced by [[MinHashLSH]], where multiple hash functions are stored. Each hash function is
+ * picked from a hash family for a specific set `S` with cardinality equal to `numEntries`:
+ * `h_i(x) = ((x \cdot a_i + b_i) \mod prime) \mod numEntries`
+ *
+ * This hash family is approximately min-wise independent according to the reference.
*
* Reference:
- * [[https://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia on Perfect Hash Function]]
+ * [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.8215&rep=rep1&type=pdf Min-wise
+ * independent permutations]]
*
- * @param numEntries The number of entries of the hash functions.
- * @param randCoefficients An array of random coefficients, each used by one hash function.
+ * @param randCoefficients Pairs of random coefficients. Each pair is used by one hash function.
*/
@Experimental
@Since("2.1.0")
-class MinHashModel private[ml] (
+class MinHashLSHModel private[ml](
override val uid: String,
- @Since("2.1.0") val numEntries: Int,
- @Since("2.1.0") val randCoefficients: Array[Int])
- extends LSHModel[MinHashModel] {
+ private[ml] val randCoefficients: Array[(Int, Int)])
+ extends LSHModel[MinHashLSHModel] {
@Since("2.1.0")
- override protected[ml] val hashFunction: Vector => Vector = {
- elems: Vector =>
+ override protected[ml] val hashFunction: Vector => Array[Vector] = {
+ elems: Vector => {
require(elems.numNonzeros > 0, "Must have at least 1 non zero entry.")
val elemsList = elems.toSparse.indices.toList
- val hashValues = randCoefficients.map({ randCoefficient: Int =>
- elemsList.map({elem: Int =>
- (1 + elem) * randCoefficient.toLong % MinHash.prime % numEntries
- }).min.toDouble
+ val hashValues = randCoefficients.map({ case (a: Int, b: Int) =>
--- End diff --
minor: the "({" is redundant. Also, I don't think the type annotations are necessary.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89175401
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -31,36 +31,38 @@ import org.apache.spark.sql.types.StructType
/**
* :: Experimental ::
*
- * Model produced by [[MinHash]], where multiple hash functions are stored. Each hash function is
- * a perfect hash function:
- * `h_i(x) = (x * k_i mod prime) mod numEntries`
- * where `k_i` is the i-th coefficient, and both `x` and `k_i` are from `Z_prime^*`
+ * Model produced by [[MinHashLSH]], where multiple hash functions are stored. Each hash function is
+ * picked from a hash family for a specific set `S` with cardinality equal to `numEntries`:
+ * `h_i(x) = ((x \cdot a_i + b_i) \mod prime) \mod numEntries`
+ *
+ * This hash family is approximately min-wise independent according to the reference.
*
* Reference:
- * [[https://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia on Perfect Hash Function]]
+ * [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.8215&rep=rep1&type=pdf Min-wise
+ * independent permutations]]
*
- * @param numEntries The number of entries of the hash functions.
- * @param randCoefficients An array of random coefficients, each used by one hash function.
+ * @param randCoefficients Pairs of random coefficients. Each pair is used by one hash function.
*/
@Experimental
@Since("2.1.0")
-class MinHashModel private[ml] (
+class MinHashLSHModel private[ml](
override val uid: String,
- @Since("2.1.0") val numEntries: Int,
- @Since("2.1.0") val randCoefficients: Array[Int])
- extends LSHModel[MinHashModel] {
+ private[ml] val randCoefficients: Array[(Int, Int)])
+ extends LSHModel[MinHashLSHModel] {
@Since("2.1.0")
- override protected[ml] val hashFunction: Vector => Vector = {
- elems: Vector =>
+ override protected[ml] val hashFunction: Vector => Array[Vector] = {
+ elems: Vector => {
require(elems.numNonzeros > 0, "Must have at least 1 non zero entry.")
val elemsList = elems.toSparse.indices.toList
- val hashValues = randCoefficients.map({ randCoefficient: Int =>
- elemsList.map({elem: Int =>
- (1 + elem) * randCoefficient.toLong % MinHash.prime % numEntries
- }).min.toDouble
+ val hashValues = randCoefficients.map({ case (a: Int, b: Int) =>
+ elemsList.map { elem: Int =>
+ ((1 + elem) * a + b) % MinHashLSH.HASH_PRIME
+ }.min.toDouble
})
- Vectors.dense(hashValues)
+ // TODO: Output vectors of dimension numHashFunctions in SPARK-18450
+ hashValues.grouped(1).map(Vectors.dense).toArray
--- End diff --
Vectors.dense takes an array instead of a single number.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Merged build finished. Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Merged build finished. Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89215190
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -112,25 +116,26 @@ class MinHash(override val uid: String) extends LSH[MinHashModel] with HasSeed {
override def setOutputCol(value: String): this.type = super.setOutputCol(value)
@Since("2.1.0")
- override def setOutputDim(value: Int): this.type = super.setOutputDim(value)
+ override def setNumHashTables(value: Int): this.type = super.setNumHashTables(value)
@Since("2.1.0")
def this() = {
- this(Identifiable.randomUID("min hash"))
+ this(Identifiable.randomUID("mh-lsh"))
}
/** @group setParam */
@Since("2.1.0")
def setSeed(value: Long): this.type = set(seed, value)
@Since("2.1.0")
- override protected[ml] def createRawLSHModel(inputDim: Int): MinHashModel = {
- require(inputDim <= MinHash.prime / 2,
- s"The input vector dimension $inputDim exceeds the threshold ${MinHash.prime / 2}.")
+ override protected[ml] def createRawLSHModel(inputDim: Int): MinHashLSHModel = {
+ require(inputDim <= MinHashLSH.HASH_PRIME,
+ s"The input vector dimension $inputDim exceeds the threshold ${MinHashLSH.HASH_PRIME}.")
val rand = new Random($(seed))
- val numEntry = inputDim * 2
- val randCoofs: Array[Int] = Array.fill($(outputDim))(1 + rand.nextInt(MinHash.prime - 1))
- new MinHashModel(uid, numEntry, randCoofs)
+ val randCoefs: Array[(Int, Int)] = Array.fill(2 * $(numHashTables)) {
--- End diff --
Unit tests added in LSHTest.scala
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88353870
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -92,18 +93,17 @@ class MinHashModel private[ml] (
* LSH class for Jaccard distance.
*
* The input can be dense or sparse vectors, but it is more efficient if it is sparse. For example,
- * `Vectors.sparse(10, Array[(2, 1.0), (3, 1.0), (5, 1.0)])`
- * means there are 10 elements in the space. This set contains elem 2, elem 3 and elem 5.
- * Also, any input vector must have at least 1 non-zero indices, and all non-zero values are treated
- * as binary "1" values.
+ * `Vectors.sparse(10, Array((2, 1.0), (3, 1.0), (5, 1.0)))`
+ * means there are 10 elements in the space. This set contains non-zero values at indices 2, 3, and
--- End diff --
I prefer the old terminology since all non-zero values are treated the same. How about "This set contains elements 2, 3, and 5." ?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Merged build finished. Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68880 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68880/consoleFull)** for PR 15874 at commit [`4508393`](https://github.com/apache/spark/commit/450839303794dec2042167af97fda627fba96bc8).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88569321
--- Diff: mllib/src/test/scala/org/apache/spark/ml/feature/MinHashLSHSuite.scala ---
@@ -86,9 +94,24 @@ class MinHashSuite extends SparkFunSuite with MLlibTestSparkContext with Default
assert(falseNegative < 0.3)
}
+ test("MinHashLSH: test of inputDim > prime") {
+ val mh = new MinHashLSH()
+ .setInputCol("keys")
+ .setOutputCol("values")
+ .setSeed(12344)
+
+ val data = {
+ for (i <- 0 to 95) yield Vectors.sparse(Int.MaxValue, (i until i + 5).map((_, 1.0)))
--- End diff --
Done.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88128756
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -144,12 +152,12 @@ class MinHash(override val uid: String) extends LSH[MinHashModel] with HasSeed {
}
@Since("2.1.0")
-object MinHash extends DefaultParamsReadable[MinHash] {
+object MinHashLSH extends DefaultParamsReadable[MinHashLSH] {
// A large prime smaller than sqrt(2^63 \u2212 1)
private[ml] val prime = 2038074743
--- End diff --
Done.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Merged build finished. Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #69012 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/69012/consoleFull)** for PR 15874 at commit [`939e9d5`](https://github.com/apache/spark/commit/939e9d5ca94607604909da0fab6cb5e06865d104).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the issue:
https://github.com/apache/spark/pull/15874
LGTM
Thanks everyone!
Merging with master and branch-2.1
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #69020 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/69020/consoleFull)** for PR 15874 at commit [`8b9403d`](https://github.com/apache/spark/commit/8b9403d0a27928f945b6142e579a6b60f70c117f).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Merged build finished. Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #69031 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/69031/consoleFull)** for PR 15874 at commit [`f0ebcb7`](https://github.com/apache/spark/commit/f0ebcb736634c02c59bc50760c53dfcad21fc5d9).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89013164
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ---
@@ -155,8 +148,30 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]]
}
/**
- * Overloaded method for approxNearestNeighbors. Use Single Probing as default way to search
- * nearest neighbors and "distCol" as default distCol.
+ * Given a large dataset and an item, approximately find at most k items which have the closest
+ * distance to the item. If the [[outputCol]] is missing, the method will transform the data; if
+ * the [[outputCol]] exists, it will use the [[outputCol]]. This allows caching of the
+ * transformed data when necessary.
+ *
+ * NOTE: This method is experimental and will likely change behavior in the next release.
--- End diff --
minor: use `@note`
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #69215 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/69215/consoleFull)** for PR 15874 at commit [`e198080`](https://github.com/apache/spark/commit/e198080557c598286363184855a6f368d60b45e3).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds the following public classes _(experimental)_:
* `class ClusteringSummary(JavaWrapper):`
* `class GaussianMixtureSummary(ClusteringSummary):`
* `class BisectingKMeansSummary(ClusteringSummary):`
* `trait CollectionGenerator extends Generator `
* `case class Stack(children: Seq[Expression]) extends Generator `
* `abstract class ExplodeBase extends UnaryExpression with CollectionGenerator with Serializable `
* `case class Explode(child: Expression) extends ExplodeBase `
* `case class PosExplode(child: Expression) extends ExplodeBase `
* `case class Inline(child: Expression) extends UnaryExpression with CollectionGenerator `
* `case class OuterReference(e: NamedExpression)`
* `trait InvokeLike extends Expression with NonSQLExpression `
* `case class ColumnStat(`
* `case class UncacheTableCommand(`
* `case class OffsetSeq(offsets: Seq[Option[Offset]], metadata: Option[String] = None) `
* `case class SparkListenerDriverAccumUpdates(`
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68678 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68678/consoleFull)** for PR 15874 at commit [`033ae5d`](https://github.com/apache/spark/commit/033ae5db1092ab2cd426f974c3e8de594461ca20).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r87904353
--- Diff: mllib/src/test/scala/org/apache/spark/ml/feature/MinHashLSHSuite.scala ---
@@ -24,7 +24,7 @@ import org.apache.spark.ml.util.DefaultReadWriteTest
import org.apache.spark.mllib.util.MLlibTestSparkContext
import org.apache.spark.sql.Dataset
-class MinHashSuite extends SparkFunSuite with MLlibTestSparkContext with DefaultReadWriteTest {
+class MinHashLSHSuite extends SparkFunSuite with MLlibTestSparkContext with DefaultReadWriteTest {
--- End diff --
Looking at the code for LSH, I see a few requires on input to some of the public methods, but there aren't tests for these edge cases. Specifically we should add
**MinHash**
* tests for empty vectors (or all zero vectors)
* tests for `inputDim > prime / 2`
**LSH**
* Test for `numNearestNeighbors < 0`
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68678 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68678/consoleFull)** for PR 15874 at commit [`033ae5d`](https://github.com/apache/spark/commit/033ae5db1092ab2cd426f974c3e8de594461ca20).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds the following public classes _(experimental)_:
* `class MinHashLSH(override val uid: String) extends LSH[MinHashLSHModel] with HasSeed `
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68803 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68803/consoleFull)** for PR 15874 at commit [`3d0810f`](https://github.com/apache/spark/commit/3d0810f25e22f6b8d64a907ade9cca14de7be763).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88128687
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -74,9 +72,12 @@ class MinHashModel private[ml] (
}
@Since("2.1.0")
- override protected[ml] def hashDistance(x: Vector, y: Vector): Double = {
+ override protected[ml] def hashDistance(x: Seq[Vector], y: Seq[Vector]): Double = {
// Since it's generated by hashing, it will be a pair of dense vectors.
- x.toDense.values.zip(y.toDense.values).map(pair => math.abs(pair._1 - pair._2)).min
+ // TODO: This hashDistance function is controversial. Requires more discussion.
+ x.zip(y).map(vectorPair =>
--- End diff --
Since it's still under discussion, I am not sure which `hashDistance` to leave in the code. Do you just want me to change to the `hashDistance` @jkbradley suggested?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the issue:
https://github.com/apache/spark/pull/15874
@Yunni Thanks for the updates! I don't think we should include AND-amplification for 2.1 since we're already in QA. But it'd be nice to get it in 2.2. Also, 2.2 will give us plenty of time to discuss distributed approxNearestNeighbors.
FYI: I asked around about the managed memory leak warning/failure. It is usually just a warning, but some test suites are set to fail upon seeing that warning. That was apparently useful for debugging some memory leak bugs but is not cause to worry. I recommend we make tests small enough to avoid them for now. If the warning becomes an issue, we could configure ML suites to ignore the warning, or we could even downgrade the warning to a lower-priority log message for all of Spark.
This LGTM. What does everyone think?
For 2.1, the main thing I'd still like to do is to send a PR to clarify terminology. That could be done in [https://github.com/apache/spark/pull/15795]
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/69012/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88359067
--- Diff: mllib/src/test/scala/org/apache/spark/ml/feature/BucketedRandomProjectionLSHSuite.scala ---
@@ -43,70 +43,72 @@ class RandomProjectionSuite
}
test("params") {
- ParamsSuite.checkParams(new RandomProjection)
- val model = new RandomProjectionModel("rp", randUnitVectors = Array(Vectors.dense(1.0, 0.0)))
+ ParamsSuite.checkParams(new BucketedRandomProjectionLSH)
+ val model = new BucketedRandomProjectionLSHModel(
+ "brp", randUnitVectors = Array(Vectors.dense(1.0, 0.0)))
ParamsSuite.checkParams(model)
}
- test("RandomProjection: default params") {
- val rp = new RandomProjection
- assert(rp.getOutputDim === 1.0)
+ test("BucketedRandomProjectionLSH: default params") {
+ val brp = new BucketedRandomProjectionLSH
+ assert(brp.getNumHashTables === 1.0)
}
test("read/write") {
- def checkModelData(model: RandomProjectionModel, model2: RandomProjectionModel): Unit = {
+ def checkModelData(
+ model: BucketedRandomProjectionLSHModel,
+ model2: BucketedRandomProjectionLSHModel
+ ): Unit = {
model.randUnitVectors.zip(model2.randUnitVectors)
.foreach(pair => assert(pair._1 === pair._2))
}
- val mh = new RandomProjection()
+ val mh = new BucketedRandomProjectionLSH()
val settings = Map("inputCol" -> "keys", "outputCol" -> "values", "bucketLength" -> 1.0)
testEstimatorAndModelReadWrite(mh, dataset, settings, checkModelData)
}
test("hashFunction") {
val randUnitVectors = Array(Vectors.dense(0.0, 1.0), Vectors.dense(1.0, 0.0))
- val model = new RandomProjectionModel("rp", randUnitVectors)
+ val model = new BucketedRandomProjectionLSHModel("brp", randUnitVectors)
model.set(model.bucketLength, 0.5)
val res = model.hashFunction(Vectors.dense(1.23, 4.56))
- assert(res.equals(Vectors.dense(9.0, 2.0)))
+ assert(res(0).equals(Vectors.dense(9.0)))
--- End diff --
also assert res.length == 2
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88129409
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ---
@@ -106,22 +123,24 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]]
* transformed data when necessary.
*
* This method implements two ways of fetching k nearest neighbors:
- * - Single Probing: Fast, return at most k elements (Probing only one buckets)
- * - Multiple Probing: Slow, return exact k elements (Probing multiple buckets close to the key)
+ * - Single-probe: Fast, return at most k elements (Probing only one buckets)
--- End diff --
Done.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the issue:
https://github.com/apache/spark/pull/15874
Other comments:
**MinHash**
Looking yet again at this, I think it's using a technically incorrect hash function. It is *not* a perfect hash function. It can hash 2 input indices to the same hash bucket. (As before, check out the Wikipedia page to see how it's missing the 2nd stage in the construction of a perfect hash function.) If we want to fix this, then we could alternatively precompute a random permutation of indices, which also serves as a perfect hash function.
That said, perhaps it does not matter in practice. If numEntries (inputDim) is large enough, then the current hash function will probably behave similarly to a perfect hash function.
**approxNearestNeighbors**
This is still not what I proposed, even for single-probe queries. It will still have the potential to consider (and sort) a number of candidates much larger than numNearestNeighbors. Since we're running out of time, I'm fine with leaving it as is for now and just changing the behavior for the next release. However, can you please add a note to the method documentation that this method is experimental and will likely change behavior in the next release?
Thanks!
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89017969
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -112,25 +116,26 @@ class MinHash(override val uid: String) extends LSH[MinHashModel] with HasSeed {
override def setOutputCol(value: String): this.type = super.setOutputCol(value)
@Since("2.1.0")
- override def setOutputDim(value: Int): this.type = super.setOutputDim(value)
+ override def setNumHashTables(value: Int): this.type = super.setNumHashTables(value)
@Since("2.1.0")
def this() = {
- this(Identifiable.randomUID("min hash"))
+ this(Identifiable.randomUID("mh-lsh"))
}
/** @group setParam */
@Since("2.1.0")
def setSeed(value: Long): this.type = set(seed, value)
@Since("2.1.0")
- override protected[ml] def createRawLSHModel(inputDim: Int): MinHashModel = {
- require(inputDim <= MinHash.prime / 2,
- s"The input vector dimension $inputDim exceeds the threshold ${MinHash.prime / 2}.")
+ override protected[ml] def createRawLSHModel(inputDim: Int): MinHashLSHModel = {
+ require(inputDim <= MinHashLSH.HASH_PRIME,
+ s"The input vector dimension $inputDim exceeds the threshold ${MinHashLSH.HASH_PRIME}.")
val rand = new Random($(seed))
- val numEntry = inputDim * 2
- val randCoofs: Array[Int] = Array.fill($(outputDim))(1 + rand.nextInt(MinHash.prime - 1))
- new MinHashModel(uid, numEntry, randCoofs)
+ val randCoefs: Array[(Int, Int)] = Array.fill(2 * $(numHashTables)) {
--- End diff --
Why is it `2 * $(numHashTables)` ?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88150618
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ---
@@ -179,16 +211,13 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]]
inputName: String,
explodeCols: Seq[String]): Dataset[_] = {
require(explodeCols.size == 2, "explodeCols must be two strings.")
- val vectorToMap = udf((x: Vector) => x.asBreeze.iterator.toMap,
- MapType(DataTypes.IntegerType, DataTypes.DoubleType))
val modelDataset: DataFrame = if (!dataset.columns.contains($(outputCol))) {
transform(dataset)
} else {
dataset.toDF()
}
modelDataset.select(
- struct(col("*")).as(inputName),
- explode(vectorToMap(col($(outputCol)))).as(explodeCols))
+ struct(col("*")).as(inputName), posexplode(col($(outputCol))).as(explodeCols))
--- End diff --
Yes, I copied your code to `BucketedRandomProjectionLSHSuite.scala` and it runs fine for me with the following output:
```
+--------------------+--------------------+------------------+
| datasetA| datasetB| distCol|
+--------------------+--------------------+------------------+
|[(50,[0],[-2.0]),...|[(50,[0],[-1.0]),...| 1.0|
|[(50,[4],[-1.0]),...|[(50,[23],[-1.0])...|1.4142135623730951|
|[(50,[5],[-1.0]),...|[(50,[32],[-1.0])...|1.4142135623730951|
|[(50,[7],[1.0]),W...|[(50,[47],[1.0]),...|1.4142135623730951|
|[(50,[7],[2.0]),W...|[(50,[26],[-2.0])...|2.8284271247461903|
|[(50,[8],[-2.0]),...|[(50,[1],[-1.0]),...| 2.23606797749979|
|[(50,[8],[-1.0]),...|[(50,[23],[-2.0])...| 2.23606797749979|
|[(50,[10],[-1.0])...|[(50,[7],[2.0]),W...| 2.23606797749979|
|[(50,[10],[-1.0])...|[(50,[13],[2.0]),...| 2.23606797749979|
|[(50,[11],[-1.0])...|[(50,[39],[2.0]),...| 2.23606797749979|
|[(50,[12],[-2.0])...|[(50,[28],[1.0]),...| 2.23606797749979|
|[(50,[12],[-2.0])...|[(50,[29],[-1.0])...| 2.23606797749979|
|[(50,[13],[1.0]),...|[(50,[2],[-2.0]),...| 2.23606797749979|
|[(50,[14],[1.0]),...|[(50,[33],[2.0]),...| 2.23606797749979|
|[(50,[14],[2.0]),...|[(50,[28],[2.0]),...|2.8284271247461903|
|[(50,[15],[-1.0])...|[(50,[38],[-1.0])...|1.4142135623730951|
|[(50,[18],[1.0]),...|[(50,[8],[-1.0]),...|1.4142135623730951|
|[(50,[18],[1.0]),...|[(50,[12],[-2.0])...| 2.23606797749979|
|[(50,[18],[2.0]),...|[(50,[43],[1.0]),...| 2.23606797749979|
|[(50,[20],[1.0]),...|[(50,[25],[-1.0])...|1.4142135623730951|
+--------------------+--------------------+------------------+
only showing top 20 rows
Let me see if the test can pass jenkins or not.
```
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89180705
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -31,36 +31,38 @@ import org.apache.spark.sql.types.StructType
/**
* :: Experimental ::
*
- * Model produced by [[MinHash]], where multiple hash functions are stored. Each hash function is
- * a perfect hash function:
- * `h_i(x) = (x * k_i mod prime) mod numEntries`
- * where `k_i` is the i-th coefficient, and both `x` and `k_i` are from `Z_prime^*`
+ * Model produced by [[MinHashLSH]], where multiple hash functions are stored. Each hash function is
+ * picked from a hash family for a specific set `S` with cardinality equal to `numEntries`:
+ * `h_i(x) = ((x \cdot a_i + b_i) \mod prime) \mod numEntries`
+ *
+ * This hash family is approximately min-wise independent according to the reference.
*
* Reference:
- * [[https://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia on Perfect Hash Function]]
+ * [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.8215&rep=rep1&type=pdf Min-wise
+ * independent permutations]]
*
- * @param numEntries The number of entries of the hash functions.
- * @param randCoefficients An array of random coefficients, each used by one hash function.
+ * @param randCoefficients Pairs of random coefficients. Each pair is used by one hash function.
*/
@Experimental
@Since("2.1.0")
-class MinHashModel private[ml] (
+class MinHashLSHModel private[ml](
override val uid: String,
- @Since("2.1.0") val numEntries: Int,
- @Since("2.1.0") val randCoefficients: Array[Int])
- extends LSHModel[MinHashModel] {
+ private[ml] val randCoefficients: Array[(Int, Int)])
+ extends LSHModel[MinHashLSHModel] {
@Since("2.1.0")
- override protected[ml] val hashFunction: Vector => Vector = {
- elems: Vector =>
+ override protected[ml] val hashFunction: Vector => Array[Vector] = {
+ elems: Vector => {
require(elems.numNonzeros > 0, "Must have at least 1 non zero entry.")
val elemsList = elems.toSparse.indices.toList
- val hashValues = randCoefficients.map({ randCoefficient: Int =>
- elemsList.map({elem: Int =>
- (1 + elem) * randCoefficient.toLong % MinHash.prime % numEntries
- }).min.toDouble
+ val hashValues = randCoefficients.map({ case (a: Int, b: Int) =>
+ elemsList.map { elem: Int =>
+ ((1 + elem) * a + b) % MinHashLSH.HASH_PRIME
+ }.min.toDouble
})
- Vectors.dense(hashValues)
+ // TODO: Output vectors of dimension numHashFunctions in SPARK-18450
+ hashValues.grouped(1).map(Vectors.dense).toArray
--- End diff --
there is an alternate constructor which takes a single (or multiple values). I guess I just think the `grouped(1)` is a bit confusing, not really an efficiency concern.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88569084
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -31,36 +31,34 @@ import org.apache.spark.sql.types.StructType
/**
* :: Experimental ::
*
- * Model produced by [[MinHash]], where multiple hash functions are stored. Each hash function is
- * a perfect hash function:
- * `h_i(x) = (x * k_i mod prime) mod numEntries`
- * where `k_i` is the i-th coefficient, and both `x` and `k_i` are from `Z_prime^*`
- *
- * Reference:
- * [[https://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia on Perfect Hash Function]]
+ * Model produced by [[MinHashLSH]], where multiple hash functions are stored. Each hash function is
+ * a perfect hash function for a specific set `S` with cardinality equal to `numEntries`:
+ * `h_i(x) = ((x \cdot a_i + b_i) \mod prime) \mod numEntries`
*
* @param numEntries The number of entries of the hash functions.
* @param randCoefficients An array of random coefficients, each used by one hash function.
--- End diff --
Updated
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89020384
--- Diff: mllib/src/test/scala/org/apache/spark/ml/feature/BucketedRandomProjectionLSHSuite.scala ---
@@ -43,70 +43,73 @@ class RandomProjectionSuite
}
test("params") {
- ParamsSuite.checkParams(new RandomProjection)
- val model = new RandomProjectionModel("rp", randUnitVectors = Array(Vectors.dense(1.0, 0.0)))
+ ParamsSuite.checkParams(new BucketedRandomProjectionLSH)
+ val model = new BucketedRandomProjectionLSHModel(
+ "brp", randUnitVectors = Array(Vectors.dense(1.0, 0.0)))
ParamsSuite.checkParams(model)
}
- test("RandomProjection: default params") {
- val rp = new RandomProjection
- assert(rp.getOutputDim === 1.0)
+ test("BucketedRandomProjectionLSH: default params") {
+ val brp = new BucketedRandomProjectionLSH
+ assert(brp.getNumHashTables === 1.0)
}
test("read/write") {
- def checkModelData(model: RandomProjectionModel, model2: RandomProjectionModel): Unit = {
+ def checkModelData(
+ model: BucketedRandomProjectionLSHModel,
+ model2: BucketedRandomProjectionLSHModel
+ ): Unit = {
--- End diff --
nit: move this up a line
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on the issue:
https://github.com/apache/spark/pull/15874
I will take a look.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89175604
--- Diff: mllib/src/test/scala/org/apache/spark/ml/feature/BucketedRandomProjectionLSHSuite.scala ---
@@ -43,70 +43,73 @@ class RandomProjectionSuite
}
test("params") {
- ParamsSuite.checkParams(new RandomProjection)
- val model = new RandomProjectionModel("rp", randUnitVectors = Array(Vectors.dense(1.0, 0.0)))
+ ParamsSuite.checkParams(new BucketedRandomProjectionLSH)
+ val model = new BucketedRandomProjectionLSHModel(
+ "brp", randUnitVectors = Array(Vectors.dense(1.0, 0.0)))
ParamsSuite.checkParams(model)
}
- test("RandomProjection: default params") {
- val rp = new RandomProjection
- assert(rp.getOutputDim === 1.0)
+ test("BucketedRandomProjectionLSH: default params") {
+ val brp = new BucketedRandomProjectionLSH
+ assert(brp.getNumHashTables === 1.0)
}
test("read/write") {
- def checkModelData(model: RandomProjectionModel, model2: RandomProjectionModel): Unit = {
+ def checkModelData(
+ model: BucketedRandomProjectionLSHModel,
+ model2: BucketedRandomProjectionLSHModel
+ ): Unit = {
--- End diff --
Done.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Merged build finished. Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r87875995
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -74,9 +72,12 @@ class MinHashModel private[ml] (
}
@Since("2.1.0")
- override protected[ml] def hashDistance(x: Vector, y: Vector): Double = {
+ override protected[ml] def hashDistance(x: Seq[Vector], y: Seq[Vector]): Double = {
// Since it's generated by hashing, it will be a pair of dense vectors.
- x.toDense.values.zip(y.toDense.values).map(pair => math.abs(pair._1 - pair._2)).min
+ // TODO: This hashDistance function is controversial. Requires more discussion.
--- End diff --
This is likely to confuse future developers. Let's just link it to a JIRA and note that it may be changed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on the issue:
https://github.com/apache/spark/pull/15874
@jkbradley Awesome, thanks so much! :) Now that the API is finalized, I will work on the User Doc
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on the issue:
https://github.com/apache/spark/pull/15874
Well, I'm having trouble merging b/c of bad wifi during travel. Ping @yanboliang @MLnick @mengxr would one of you mind merging this with master and branch-2.1? @sethah and I having both given LGTMs. Thanks!
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/68823/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89175448
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ---
@@ -155,8 +148,30 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]]
}
/**
- * Overloaded method for approxNearestNeighbors. Use Single Probing as default way to search
- * nearest neighbors and "distCol" as default distCol.
+ * Given a large dataset and an item, approximately find at most k items which have the closest
+ * distance to the item. If the [[outputCol]] is missing, the method will transform the data; if
+ * the [[outputCol]] exists, it will use the [[outputCol]]. This allows caching of the
+ * transformed data when necessary.
+ *
+ * NOTE: This method is experimental and will likely change behavior in the next release.
+ *
+ * @param dataset the dataset to search for nearest neighbors of the key
--- End diff --
Done.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Merged build finished. Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r87922281
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ---
@@ -179,16 +211,13 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]]
inputName: String,
explodeCols: Seq[String]): Dataset[_] = {
require(explodeCols.size == 2, "explodeCols must be two strings.")
- val vectorToMap = udf((x: Vector) => x.asBreeze.iterator.toMap,
- MapType(DataTypes.IntegerType, DataTypes.DoubleType))
val modelDataset: DataFrame = if (!dataset.columns.contains($(outputCol))) {
transform(dataset)
} else {
dataset.toDF()
}
modelDataset.select(
- struct(col("*")).as(inputName),
- explode(vectorToMap(col($(outputCol)))).as(explodeCols))
+ struct(col("*")).as(inputName), posexplode(col($(outputCol))).as(explodeCols))
--- End diff --
Well here's a fun one. When I run this test:
````scala
test("memory leak test") {
val numDim = 50
val data = {
for (i <- 0 until numDim; j <- Seq(-2, -1, 1, 2))
yield Vectors.sparse(numDim, Seq((i, j.toDouble)))
}
val df = spark.createDataFrame(data.map(Tuple1.apply)).toDF("keys")
// Project from 100 dimensional Euclidean Space to 10 dimensions
val brp = new BucketedRandomProjectionLSH()
.setNumHashTables(10)
.setInputCol("keys")
.setOutputCol("values")
.setBucketLength(2.5)
.setSeed(12345)
val model = brp.fit(df)
val joined = model.approxSimilarityJoin(df, df, Double.MaxValue, "distCol")
joined.show()
}
````
I get the following error:
````
[info] - BucketedRandomProjectionLSH with high dimension data: test of LSH property *** FAILED *** (7 seconds, 568 milliseconds)
[info] org.apache.spark.SparkException: Job aborted due to stage failure: Task 0 in stage 4.0 failed 1 times, most recent failure: Lost task 0.0 in stage 4.0 (TID 205, localhost, executor driver): org.apache.spark.SparkException: Managed memory leak detected; size = 33816576 bytes, TID = 205
[info] at org.apache.spark.executor.Executor$TaskRunner.run(Executor.scala:295)
[info] at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
[info] at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
[info] at java.lang.Thread.run(Thread.java:745)
````
Could you run the same test and see if you get an error?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68601 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68601/consoleFull)** for PR 15874 at commit [`adbbefe`](https://github.com/apache/spark/commit/adbbefe1777db8fb85a0af59c11e5840d3bc91ee).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r87844308
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -144,12 +152,12 @@ class MinHash(override val uid: String) extends LSH[MinHashModel] with HasSeed {
}
@Since("2.1.0")
-object MinHash extends DefaultParamsReadable[MinHash] {
+object MinHashLSH extends DefaultParamsReadable[MinHashLSH] {
// A large prime smaller than sqrt(2^63 \u2212 1)
private[ml] val prime = 2038074743
--- End diff --
We typically use all caps for constants like these. I prefer `MinHashLSH.HASH_PRIME` or `MinHashLSH.PRIME_MODULUS`.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88128732
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -125,11 +125,11 @@ class MinHash(override val uid: String) extends LSH[MinHashModel] with HasSeed {
@Since("2.1.0")
override protected[ml] def createRawLSHModel(inputDim: Int): MinHashModel = {
- require(inputDim <= MinHash.prime / 2,
- s"The input vector dimension $inputDim exceeds the threshold ${MinHash.prime / 2}.")
+ require(inputDim <= MinHashLSH.prime / 2,
+ s"The input vector dimension $inputDim exceeds the threshold ${MinHashLSH.prime / 2}.")
val rand = new Random($(seed))
val numEntry = inputDim * 2
- val randCoofs: Array[Int] = Array.fill($(outputDim))(1 + rand.nextInt(MinHash.prime - 1))
+ val randCoofs: Array[Int] = Array.fill($(numHashTables))(1 + rand.nextInt(MinHashLSH.prime - 1))
--- End diff --
Fixed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on the issue:
https://github.com/apache/spark/pull/15874
Thanks, @sethah. I have reverted "AND-amplification" related changes. PTAL.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89175497
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -31,36 +31,38 @@ import org.apache.spark.sql.types.StructType
/**
* :: Experimental ::
*
- * Model produced by [[MinHash]], where multiple hash functions are stored. Each hash function is
- * a perfect hash function:
- * `h_i(x) = (x * k_i mod prime) mod numEntries`
- * where `k_i` is the i-th coefficient, and both `x` and `k_i` are from `Z_prime^*`
+ * Model produced by [[MinHashLSH]], where multiple hash functions are stored. Each hash function is
+ * picked from a hash family for a specific set `S` with cardinality equal to `numEntries`:
+ * `h_i(x) = ((x \cdot a_i + b_i) \mod prime) \mod numEntries`
--- End diff --
Fixed
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Merged build finished. Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on the issue:
https://github.com/apache/spark/pull/15874
Thanks @sethah ! Your comment was very helpful and detailed :-)
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88128252
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -46,21 +42,23 @@ import org.apache.spark.sql.types.StructType
@Since("2.1.0")
class MinHashModel private[ml] (
override val uid: String,
- @Since("2.1.0") val numEntries: Int,
- @Since("2.1.0") val randCoefficients: Array[Int])
+ @Since("2.1.0") private[ml] val numEntries: Int,
--- End diff --
Removed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r87928721
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/BucketedRandomProjectionLSH.scala ---
@@ -89,23 +90,25 @@ class RandomProjectionModel private[ml] (
}
@Since("2.1.0")
- override protected[ml] def hashDistance(x: Vector, y: Vector): Double = {
+ override protected[ml] def hashDistance(x: Seq[Vector], y: Seq[Vector]): Double = {
// Since it's generated by hashing, it will be a pair of dense vectors.
- x.toDense.values.zip(y.toDense.values).map(pair => math.abs(pair._1 - pair._2)).min
+ x.zip(y).map(vectorPair => Vectors.sqdist(vectorPair._1, vectorPair._2)).min
}
@Since("2.1.0")
override def copy(extra: ParamMap): this.type = defaultCopy(extra)
@Since("2.1.0")
- override def write: MLWriter = new RandomProjectionModel.RandomProjectionModelWriter(this)
+ override def write: MLWriter = {
+ new BucketedRandomProjectionModel.BucketedRandomProjectionModelWriter(this)
+ }
}
/**
* :: Experimental ::
*
- * This [[RandomProjection]] implements Locality Sensitive Hashing functions for Euclidean
- * distance metrics.
+ * This [[BucketedRandomProjectionLSH]] implements Locality Sensitive Hashing functions for
+ * Euclidean distance metrics.
*
* The input is dense or sparse vectors, each of which represents a point in the Euclidean
* distance space. The output will be vectors of configurable dimension. Hash value in the same
--- End diff --
"Hash values in the same dimension are calculated"
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r87878252
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -102,8 +103,7 @@ class MinHashModel private[ml] (
*/
@Experimental
@Since("2.1.0")
-class MinHash(override val uid: String) extends LSH[MinHashModel] with HasSeed {
-
+class MinHashLSH(override val uid: String) extends LSH[MinHashModel] with HasSeed {
--- End diff --
Also, the comment above says:
````
* ... For example,
* `Vectors.sparse(10, Array[(2, 1.0), (3, 1.0), (5, 1.0)])`
* means there are 10 elements in the space. This set contains elem 2, elem 3 and elem 5.
* Also, any input vector must have at least 1 non-zero indices, and all non-zero values are treated
* as binary "1" values.
````
Can we change it to:
````
* ... For example,
* `Vectors.sparse(10, Array((2, 1.0), (3, 1.0), (5, 1.0)))`
* means there are 10 elements in the space. This set contains non-zero values at indices 2, 3, and
* 5. Also, any input vector must have at least 1 non-zero index, and all non-zero values are
* treated as binary "1" values.
````
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Merged build finished. Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r87875688
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -46,21 +42,23 @@ import org.apache.spark.sql.types.StructType
@Since("2.1.0")
class MinHashModel private[ml] (
--- End diff --
Not specifically related to this pr: I checked and the default random uids used in ML library never contain spaces. For more complex uids, it seems more common to use camel case, but I do see some with hyphens. Can we make the default uids: `"mh-lsh"` and `"brp-lsh"` or similar?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88536087
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ---
@@ -179,16 +211,13 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]]
inputName: String,
explodeCols: Seq[String]): Dataset[_] = {
require(explodeCols.size == 2, "explodeCols must be two strings.")
- val vectorToMap = udf((x: Vector) => x.asBreeze.iterator.toMap,
- MapType(DataTypes.IntegerType, DataTypes.DoubleType))
val modelDataset: DataFrame = if (!dataset.columns.contains($(outputCol))) {
transform(dataset)
} else {
dataset.toDF()
}
modelDataset.select(
- struct(col("*")).as(inputName),
- explode(vectorToMap(col($(outputCol)))).as(explodeCols))
+ struct(col("*")).as(inputName), posexplode(col($(outputCol))).as(explodeCols))
--- End diff --
See https://github.com/apache/spark/pull/15916
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r87876322
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -102,8 +103,7 @@ class MinHashModel private[ml] (
*/
@Experimental
@Since("2.1.0")
-class MinHash(override val uid: String) extends LSH[MinHashModel] with HasSeed {
-
+class MinHashLSH(override val uid: String) extends LSH[MinHashModel] with HasSeed {
--- End diff --
change the model names to reflect the new estimator names.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89015981
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -31,36 +31,38 @@ import org.apache.spark.sql.types.StructType
/**
* :: Experimental ::
*
- * Model produced by [[MinHash]], where multiple hash functions are stored. Each hash function is
- * a perfect hash function:
- * `h_i(x) = (x * k_i mod prime) mod numEntries`
- * where `k_i` is the i-th coefficient, and both `x` and `k_i` are from `Z_prime^*`
+ * Model produced by [[MinHashLSH]], where multiple hash functions are stored. Each hash function is
+ * picked from a hash family for a specific set `S` with cardinality equal to `numEntries`:
+ * `h_i(x) = ((x \cdot a_i + b_i) \mod prime) \mod numEntries`
+ *
+ * This hash family is approximately min-wise independent according to the reference.
*
* Reference:
- * [[https://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia on Perfect Hash Function]]
+ * [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.8215&rep=rep1&type=pdf Min-wise
+ * independent permutations]]
*
- * @param numEntries The number of entries of the hash functions.
- * @param randCoefficients An array of random coefficients, each used by one hash function.
+ * @param randCoefficients Pairs of random coefficients. Each pair is used by one hash function.
*/
@Experimental
@Since("2.1.0")
-class MinHashModel private[ml] (
+class MinHashLSHModel private[ml](
override val uid: String,
- @Since("2.1.0") val numEntries: Int,
- @Since("2.1.0") val randCoefficients: Array[Int])
- extends LSHModel[MinHashModel] {
+ private[ml] val randCoefficients: Array[(Int, Int)])
+ extends LSHModel[MinHashLSHModel] {
@Since("2.1.0")
- override protected[ml] val hashFunction: Vector => Vector = {
- elems: Vector =>
+ override protected[ml] val hashFunction: Vector => Array[Vector] = {
+ elems: Vector => {
require(elems.numNonzeros > 0, "Must have at least 1 non zero entry.")
val elemsList = elems.toSparse.indices.toList
- val hashValues = randCoefficients.map({ randCoefficient: Int =>
- elemsList.map({elem: Int =>
- (1 + elem) * randCoefficient.toLong % MinHash.prime % numEntries
- }).min.toDouble
+ val hashValues = randCoefficients.map({ case (a: Int, b: Int) =>
+ elemsList.map { elem: Int =>
+ ((1 + elem) * a + b) % MinHashLSH.HASH_PRIME
+ }.min.toDouble
})
- Vectors.dense(hashValues)
+ // TODO: Output vectors of dimension numHashFunctions in SPARK-18450
+ hashValues.grouped(1).map(Vectors.dense).toArray
--- End diff --
Why not: `hashValues.map(Vectors.dense(_))` ? We can just add the grouping later when it's needed. Same for BRP.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68625 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68625/consoleFull)** for PR 15874 at commit [`c115ed3`](https://github.com/apache/spark/commit/c115ed3e580d4999c85d02417356e66f8f360bda).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r87906133
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -31,13 +31,9 @@ import org.apache.spark.sql.types.StructType
/**
* :: Experimental ::
*
- * Model produced by [[MinHash]], where multiple hash functions are stored. Each hash function is
- * a perfect hash function:
- * `h_i(x) = (x * k_i mod prime) mod numEntries`
- * where `k_i` is the i-th coefficient, and both `x` and `k_i` are from `Z_prime^*`
- *
- * Reference:
- * [[https://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia on Perfect Hash Function]]
+ * Model produced by [[MinHashLSH]], where multiple hash functions are stored. Each hash function is
+ * a perfect hash function for a specific set `S` with cardinality equal to a half of `numEntries`:
--- End diff --
I'm not following exactly why the cardinality of `S` is _half_ of `numEntries`. Actually, why is threshold for feature dimensionality `prime / 2` ?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/68678/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88569303
--- Diff: mllib/src/test/scala/org/apache/spark/ml/feature/BucketedRandomProjectionLSHSuite.scala ---
@@ -43,70 +43,72 @@ class RandomProjectionSuite
}
test("params") {
- ParamsSuite.checkParams(new RandomProjection)
- val model = new RandomProjectionModel("rp", randUnitVectors = Array(Vectors.dense(1.0, 0.0)))
+ ParamsSuite.checkParams(new BucketedRandomProjectionLSH)
+ val model = new BucketedRandomProjectionLSHModel(
+ "brp", randUnitVectors = Array(Vectors.dense(1.0, 0.0)))
ParamsSuite.checkParams(model)
}
- test("RandomProjection: default params") {
- val rp = new RandomProjection
- assert(rp.getOutputDim === 1.0)
+ test("BucketedRandomProjectionLSH: default params") {
+ val brp = new BucketedRandomProjectionLSH
+ assert(brp.getNumHashTables === 1.0)
}
test("read/write") {
- def checkModelData(model: RandomProjectionModel, model2: RandomProjectionModel): Unit = {
+ def checkModelData(
+ model: BucketedRandomProjectionLSHModel,
+ model2: BucketedRandomProjectionLSHModel
+ ): Unit = {
model.randUnitVectors.zip(model2.randUnitVectors)
.foreach(pair => assert(pair._1 === pair._2))
}
- val mh = new RandomProjection()
+ val mh = new BucketedRandomProjectionLSH()
val settings = Map("inputCol" -> "keys", "outputCol" -> "values", "bucketLength" -> 1.0)
testEstimatorAndModelReadWrite(mh, dataset, settings, checkModelData)
}
test("hashFunction") {
val randUnitVectors = Array(Vectors.dense(0.0, 1.0), Vectors.dense(1.0, 0.0))
- val model = new RandomProjectionModel("rp", randUnitVectors)
+ val model = new BucketedRandomProjectionLSHModel("brp", randUnitVectors)
model.set(model.bucketLength, 0.5)
val res = model.hashFunction(Vectors.dense(1.23, 4.56))
- assert(res.equals(Vectors.dense(9.0, 2.0)))
+ assert(res(0).equals(Vectors.dense(9.0)))
--- End diff --
Added.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88359545
--- Diff: mllib/src/test/scala/org/apache/spark/ml/feature/BucketedRandomProjectionLSHSuite.scala ---
@@ -115,64 +117,83 @@ class RandomProjectionSuite
val df = spark.createDataFrame(data.map(Tuple1.apply)).toDF("keys")
// Project from 100 dimensional Euclidean Space to 10 dimensions
- val rp = new RandomProjection()
- .setOutputDim(10)
+ val brp = new BucketedRandomProjectionLSH()
+ .setNumHashTables(10)
.setInputCol("keys")
.setOutputCol("values")
.setBucketLength(2.5)
.setSeed(12345)
- val (falsePositive, falseNegative) = LSHTest.calculateLSHProperty(df, rp, 3.0, 2.0)
+ val (falsePositive, falseNegative) = LSHTest.calculateLSHProperty(df, brp, 3.0, 2.0)
assert(falsePositive < 0.3)
assert(falseNegative < 0.3)
}
- test("approxNearestNeighbors for random projection") {
+ test("approxNearestNeighbors for bucketed random projection") {
val key = Vectors.dense(1.2, 3.4)
- val rp = new RandomProjection()
- .setOutputDim(2)
+ val brp = new BucketedRandomProjectionLSH()
+ .setNumHashTables(2)
.setInputCol("keys")
.setOutputCol("values")
.setBucketLength(4.0)
.setSeed(12345)
- val (precision, recall) = LSHTest.calculateApproxNearestNeighbors(rp, dataset, key, 100,
- singleProbing = true)
+ val (precision, recall) = LSHTest.calculateApproxNearestNeighbors(brp, dataset, key, 100,
+ singleProbe = true)
assert(precision >= 0.6)
assert(recall >= 0.6)
}
test("approxNearestNeighbors with multiple probing") {
val key = Vectors.dense(1.2, 3.4)
- val rp = new RandomProjection()
- .setOutputDim(20)
+ val brp = new BucketedRandomProjectionLSH()
+ .setNumHashTables(20)
.setInputCol("keys")
.setOutputCol("values")
.setBucketLength(1.0)
.setSeed(12345)
- val (precision, recall) = LSHTest.calculateApproxNearestNeighbors(rp, dataset, key, 100,
- singleProbing = false)
+ val (precision, recall) = LSHTest.calculateApproxNearestNeighbors(brp, dataset, key, 100,
+ singleProbe = false)
assert(precision >= 0.7)
assert(recall >= 0.7)
}
- test("approxSimilarityJoin for random projection on different dataset") {
+ test("approxNearestNeighbors for numNeighbors <= 0") {
+ val key = Vectors.dense(1.2, 3.4)
+
+ val brp = new BucketedRandomProjectionLSH()
+ .setNumHashTables(20)
--- End diff --
No need to set some of these Params here
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68802 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68802/consoleFull)** for PR 15874 at commit [`00d08bf`](https://github.com/apache/spark/commit/00d08bf5bad60e405f01f55272911335545cd9b7).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68601 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68601/consoleFull)** for PR 15874 at commit [`adbbefe`](https://github.com/apache/spark/commit/adbbefe1777db8fb85a0af59c11e5840d3bc91ee).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68689 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68689/consoleFull)** for PR 15874 at commit [`d759875`](https://github.com/apache/spark/commit/d75987591c68aaae5bd007a92f3587193edd7b2a).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on the issue:
https://github.com/apache/spark/pull/15874
@jkbradley If you don't have more comments, can we merge this because I need to change the examples in #15795 ?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68823 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68823/consoleFull)** for PR 15874 at commit [`257ef19`](https://github.com/apache/spark/commit/257ef1955696b937a0b53feb0ebde136f482dae1).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r87871105
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ---
@@ -106,22 +106,24 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]]
* transformed data when necessary.
*
* This method implements two ways of fetching k nearest neighbors:
- * - Single Probing: Fast, return at most k elements (Probing only one buckets)
- * - Multiple Probing: Slow, return exact k elements (Probing multiple buckets close to the key)
+ * - Single-probe: Fast, return at most k elements (Probing only one buckets)
+ * - Multi-probe: Slow, return exact k elements (Probing multiple buckets close to the key)
+ *
+ * Currently it is made private since more discussion is needed for Multi-probe
--- End diff --
I don't understand the point here. Are you trying to make the `approxNearestNeighbors` method completely private? There is still a public overload of this method - which now shows up as the only method in the docs and just says "overloaded method for approxNearestNeighbors". This doc above does not show up.
As a general rule, we should always generate and closely inspect the docs to make sure that they are what we intend and that they make sense from an end user's perspective.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89013284
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ---
@@ -155,8 +148,30 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]]
}
/**
- * Overloaded method for approxNearestNeighbors. Use Single Probing as default way to search
- * nearest neighbors and "distCol" as default distCol.
+ * Given a large dataset and an item, approximately find at most k items which have the closest
+ * distance to the item. If the [[outputCol]] is missing, the method will transform the data; if
+ * the [[outputCol]] exists, it will use the [[outputCol]]. This allows caching of the
+ * transformed data when necessary.
+ *
+ * NOTE: This method is experimental and will likely change behavior in the next release.
+ *
+ * @param dataset the dataset to search for nearest neighbors of the key
--- End diff --
nit: Capitalize first words and add periods to all fields
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68683 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68683/consoleFull)** for PR 15874 at commit [`c597f4c`](https://github.com/apache/spark/commit/c597f4c83519af38a9749acd71078ac20ef20c14).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88128287
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -46,21 +42,23 @@ import org.apache.spark.sql.types.StructType
@Since("2.1.0")
class MinHashModel private[ml] (
override val uid: String,
- @Since("2.1.0") val numEntries: Int,
- @Since("2.1.0") val randCoefficients: Array[Int])
+ @Since("2.1.0") private[ml] val numEntries: Int,
+ @Since("2.1.0") private[ml] val randCoefficients: Array[Int])
extends LSHModel[MinHashModel] {
@Since("2.1.0")
- override protected[ml] val hashFunction: Vector => Vector = {
- elems: Vector =>
+ override protected[ml] val hashFunction: Vector => Array[Vector] = {
+ elems: Vector => {
require(elems.numNonzeros > 0, "Must have at least 1 non zero entry.")
val elemsList = elems.toSparse.indices.toList
val hashValues = randCoefficients.map({ randCoefficient: Int =>
- elemsList.map({elem: Int =>
- (1 + elem) * randCoefficient.toLong % MinHash.prime % numEntries
- }).min.toDouble
+ elemsList.map({ elem: Int =>
--- End diff --
Removed brackets.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88569066
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -31,36 +31,34 @@ import org.apache.spark.sql.types.StructType
/**
* :: Experimental ::
*
- * Model produced by [[MinHash]], where multiple hash functions are stored. Each hash function is
- * a perfect hash function:
- * `h_i(x) = (x * k_i mod prime) mod numEntries`
- * where `k_i` is the i-th coefficient, and both `x` and `k_i` are from `Z_prime^*`
- *
- * Reference:
- * [[https://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia on Perfect Hash Function]]
+ * Model produced by [[MinHashLSH]], where multiple hash functions are stored. Each hash function is
+ * a perfect hash function for a specific set `S` with cardinality equal to `numEntries`:
--- End diff --
Yes, removed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #69020 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/69020/consoleFull)** for PR 15874 at commit [`8b9403d`](https://github.com/apache/spark/commit/8b9403d0a27928f945b6142e579a6b60f70c117f).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r87906309
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -46,21 +42,23 @@ import org.apache.spark.sql.types.StructType
@Since("2.1.0")
class MinHashModel private[ml] (
override val uid: String,
- @Since("2.1.0") val numEntries: Int,
- @Since("2.1.0") val randCoefficients: Array[Int])
+ @Since("2.1.0") private[ml] val numEntries: Int,
+ @Since("2.1.0") private[ml] val randCoefficients: Array[Int])
extends LSHModel[MinHashModel] {
@Since("2.1.0")
- override protected[ml] val hashFunction: Vector => Vector = {
- elems: Vector =>
+ override protected[ml] val hashFunction: Vector => Array[Vector] = {
+ elems: Vector => {
require(elems.numNonzeros > 0, "Must have at least 1 non zero entry.")
val elemsList = elems.toSparse.indices.toList
val hashValues = randCoefficients.map({ randCoefficient: Int =>
- elemsList.map({elem: Int =>
- (1 + elem) * randCoefficient.toLong % MinHash.prime % numEntries
- }).min.toDouble
+ elemsList.map({ elem: Int =>
--- End diff --
redundant brackets. Just use `elemsList.map { elem: Int =>`
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r87910679
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/MinHashLSH.scala ---
@@ -74,9 +72,12 @@ class MinHashModel private[ml] (
}
@Since("2.1.0")
- override protected[ml] def hashDistance(x: Vector, y: Vector): Double = {
+ override protected[ml] def hashDistance(x: Seq[Vector], y: Seq[Vector]): Double = {
// Since it's generated by hashing, it will be a pair of dense vectors.
- x.toDense.values.zip(y.toDense.values).map(pair => math.abs(pair._1 - pair._2)).min
+ // TODO: This hashDistance function is controversial. Requires more discussion.
+ x.zip(y).map(vectorPair =>
--- End diff --
At this point, I'm quite unsure, but this does not look to me like what what was discussed [here](https://github.com/apache/spark/pull/15800#event-857283655). @jkbradley Can you confirm this is what you wanted?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Merged build finished. Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by sethah <gi...@git.apache.org>.
Github user sethah commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r89021397
--- Diff: mllib/src/test/scala/org/apache/spark/ml/feature/MinHashLSHSuite.scala ---
@@ -97,12 +118,31 @@ class MinHashSuite extends SparkFunSuite with MLlibTestSparkContext with Default
(0 until 100).filter(_.toString.contains("1")).map((_, 1.0)))
val (precision, recall) = LSHTest.calculateApproxNearestNeighbors(mh, dataset, key, 20,
- singleProbing = true)
+ singleProbe = true)
assert(precision >= 0.7)
assert(recall >= 0.7)
}
- test("approxSimilarityJoin for minhash on different dataset") {
+ test("approxNearestNeighbors for numNeighbors <= 0") {
+ val mh = new MinHashLSH()
+ .setNumHashTables(20)
+ .setInputCol("keys")
+ .setOutputCol("values")
+ .setSeed(12345)
+
+ val key: Vector = Vectors.sparse(100,
+ (0 until 100).filter(_.toString.contains("1")).map((_, 1.0)))
+
+ val model = mh.fit(dataset)
--- End diff --
It would be easier to just create a model artificially, then test the edge case. That will speed up the tests. Same in other places.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by jkbradley <gi...@git.apache.org>.
Github user jkbradley commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88521575
--- Diff: mllib/src/test/scala/org/apache/spark/ml/feature/MinHashLSHSuite.scala ---
@@ -86,9 +94,24 @@ class MinHashSuite extends SparkFunSuite with MLlibTestSparkContext with Default
assert(falseNegative < 0.3)
}
+ test("MinHashLSH: test of inputDim > prime") {
+ val mh = new MinHashLSH()
+ .setInputCol("keys")
+ .setOutputCol("values")
+ .setSeed(12344)
+
+ val data = {
+ for (i <- 0 to 95) yield Vectors.sparse(Int.MaxValue, (i until i + 5).map((_, 1.0)))
--- End diff --
Change to "0 to 2." I like keeping tests minimal.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68802 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68802/consoleFull)** for PR 15874 at commit [`00d08bf`](https://github.com/apache/spark/commit/00d08bf5bad60e405f01f55272911335545cd9b7).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/69031/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by Yunni <gi...@git.apache.org>.
Github user Yunni commented on a diff in the pull request:
https://github.com/apache/spark/pull/15874#discussion_r88169546
--- Diff: mllib/src/main/scala/org/apache/spark/ml/feature/LSH.scala ---
@@ -179,16 +211,13 @@ private[ml] abstract class LSHModel[T <: LSHModel[T]]
inputName: String,
explodeCols: Seq[String]): Dataset[_] = {
require(explodeCols.size == 2, "explodeCols must be two strings.")
- val vectorToMap = udf((x: Vector) => x.asBreeze.iterator.toMap,
- MapType(DataTypes.IntegerType, DataTypes.DoubleType))
val modelDataset: DataFrame = if (!dataset.columns.contains($(outputCol))) {
transform(dataset)
} else {
dataset.toDF()
}
modelDataset.select(
- struct(col("*")).as(inputName),
- explode(vectorToMap(col($(outputCol)))).as(explodeCols))
+ struct(col("*")).as(inputName), posexplode(col($(outputCol))).as(explodeCols))
--- End diff --
If you look at line 292 of `Executor.scala`, it shows this is just a OOM exception of Dataframe. That's the reason why it behaves different on our machines and Jenkins.
`model.approxSimilarityJoin(df, df, Double.MaxValue, "distCol")` returns near 40000 rows when `threshold = Double.MaxValue`
If you reduce the `numDim`, the test will pass.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408] API Improvements for LSH
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15874
Merged build finished. Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15874: [Spark-18408][ML] API Improvements for LSH
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:
https://github.com/apache/spark/pull/15874
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15874: [Spark-18408][ML] API Improvements for LSH
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15874
**[Test build #68880 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68880/consoleFull)** for PR 15874 at commit [`4508393`](https://github.com/apache/spark/commit/450839303794dec2042167af97fda627fba96bc8).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org