{"action":"created","issue":{"url":"https://api.github.com/repos/apache/spark/issues/15150","repository_url":"https://api.github.com/repos/apache/spark","labels_url":"https://api.github.com/repos/apache/spark/issues/15150/labels{/name}","comments_url":"https://api.github.com/repos/apache/spark/issues/15150/comments","events_url":"https://api.github.com/repos/apache/spark/issues/15150/events","html_url":"https://github.com/apache/spark/pull/15150","id":177803679,"number":15150,"title":"[SPARK-17595] [MLLib] Use a bounded priority queue to find synonyms in Word2VecModel","user":{"login":"willb","id":1161,"avatar_url":"https://avatars.githubusercontent.com/u/1161?v=3","gravatar_id":"","url":"https://api.github.com/users/willb","html_url":"https://github.com/willb","followers_url":"https://api.github.com/users/willb/followers","following_url":"https://api.github.com/users/willb/following{/other_user}","gists_url":"https://api.github.com/users/willb/gists{/gist_id}","starred_url":"https://api.github.com/users/willb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/willb/subscriptions","organizations_url":"https://api.github.com/users/willb/orgs","repos_url":"https://api.github.com/users/willb/repos","events_url":"https://api.github.com/users/willb/events{/privacy}","received_events_url":"https://api.github.com/users/willb/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":8,"created_at":"2016-09-19T14:41:31Z","updated_at":"2016-09-20T16:39:34Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/15150","html_url":"https://github.com/apache/spark/pull/15150","diff_url":"https://github.com/apache/spark/pull/15150.diff","patch_url":"https://github.com/apache/spark/pull/15150.patch"},"body":"## What changes were proposed in this pull request?\r\n\r\nThe code in `Word2VecModel.findSynonyms` to choose the vocabulary elements with the highest similarity to the query vector currently sorts the collection of similarities for every vocabulary element. This involves making multiple copies of the collection of similarities while doing a (relatively) expensive sort. It would be more efficient to find the best matches by maintaining a bounded priority queue and populating it with a single pass over the vocabulary, and that is exactly what this patch does.\r\n\r\n## How was this patch tested?\r\n\r\nThis patch adds no user-visible functionality and its correctness should be exercised by existing tests.  To ensure that this approach is actually faster, I made a microbenchmark for `findSynonyms`:\r\n\r\n```\r\nobject W2VTiming {\r\n  import org.apache.spark.{SparkContext, SparkConf}\r\n  import org.apache.spark.mllib.feature.Word2VecModel\r\n  def run(modelPath: String, scOpt: Option[SparkContext] = None) {\r\n    val sc = scOpt.getOrElse(new SparkContext(new SparkConf(true).setMaster(\"local[*]\").setAppName(\"test\")))\r\n    val model = Word2VecModel.load(sc, modelPath)\r\n    val keys = model.getVectors.keys\r\n    val start = System.currentTimeMillis\r\n    for(key <- keys) {\r\n      model.findSynonyms(key, 5)\r\n      model.findSynonyms(key, 10)\r\n      model.findSynonyms(key, 25)\r\n      model.findSynonyms(key, 50)\r\n    }\r\n    val finish = System.currentTimeMillis\r\n    println(\"run completed in \" + (finish - start) + \"ms\")\r\n  }\r\n}\r\n```\r\n\r\nI ran this test on a model generated from the complete works of Jane Austen and found that the new approach was over 3x faster than the old approach.  (If the `num` argument to `findSynonyms` is very close to the vocabulary size, the new approach will have less of an advantage over the old one.)\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/apache/spark/issues/comments/248358484","html_url":"https://github.com/apache/spark/pull/15150#issuecomment-248358484","issue_url":"https://api.github.com/repos/apache/spark/issues/15150","id":248358484,"user":{"login":"AmplabJenkins","id":4031291,"avatar_url":"https://avatars.githubusercontent.com/u/4031291?v=3","gravatar_id":"","url":"https://api.github.com/users/AmplabJenkins","html_url":"https://github.com/AmplabJenkins","followers_url":"https://api.github.com/users/AmplabJenkins/followers","following_url":"https://api.github.com/users/AmplabJenkins/following{/other_user}","gists_url":"https://api.github.com/users/AmplabJenkins/gists{/gist_id}","starred_url":"https://api.github.com/users/AmplabJenkins/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/AmplabJenkins/subscriptions","organizations_url":"https://api.github.com/users/AmplabJenkins/orgs","repos_url":"https://api.github.com/users/AmplabJenkins/repos","events_url":"https://api.github.com/users/AmplabJenkins/events{/privacy}","received_events_url":"https://api.github.com/users/AmplabJenkins/received_events","type":"User","site_admin":false},"created_at":"2016-09-20T16:39:34Z","updated_at":"2016-09-20T16:39:34Z","body":"Merged build finished. Test PASSed."}}
{"actor":{"display_login":"AmplabJenkins"}}