{"action":"created","issue":{"url":"https://api.github.com/repos/apache/flink/issues/1220","labels_url":"https://api.github.com/repos/apache/flink/issues/1220/labels{/name}","comments_url":"https://api.github.com/repos/apache/flink/issues/1220/comments","events_url":"https://api.github.com/repos/apache/flink/issues/1220/events","html_url":"https://github.com/apache/flink/pull/1220","id":109639790,"number":1220,"title":"Flink 1745","user":{"login":"danielblazevski","id":10012612,"avatar_url":"https://avatars.githubusercontent.com/u/10012612?v=3","gravatar_id":"","url":"https://api.github.com/users/danielblazevski","html_url":"https://github.com/danielblazevski","followers_url":"https://api.github.com/users/danielblazevski/followers","following_url":"https://api.github.com/users/danielblazevski/following{/other_user}","gists_url":"https://api.github.com/users/danielblazevski/gists{/gist_id}","starred_url":"https://api.github.com/users/danielblazevski/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/danielblazevski/subscriptions","organizations_url":"https://api.github.com/users/danielblazevski/orgs","repos_url":"https://api.github.com/users/danielblazevski/repos","events_url":"https://api.github.com/users/danielblazevski/events{/privacy}","received_events_url":"https://api.github.com/users/danielblazevski/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":7,"created_at":"2015-10-03T19:03:13Z","updated_at":"2015-10-04T14:16:28Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/apache/flink/pulls/1220","html_url":"https://github.com/apache/flink/pull/1220","diff_url":"https://github.com/apache/flink/pull/1220.diff","patch_url":"https://github.com/apache/flink/pull/1220.patch"},"body":"I added a quadtree data structure for the knn algorithm.  @chiwanpark made originally made a pull request for a kNN algorithm, and we coordinated so that I incorporate a tree structure. The quadtree scales very well with the number of training + test points, but scales poorly with the dimension (even the R-tree scales poorly with the dimension). I added a flag that is automatically determines whether or not to use the quadtree. My implementation needed to use the Euclidean or SquaredEuclidean distance since I needed a specific notion of the distance between a test point and a box in the quadtree. I added another test KNNQuadTreeSuite in addition to Chiwan Park's KNNITSuite, since C. Park's parameters will automatically choose the brute-force non-quadtree method.\r\n\r\nFor more details on the quadtree + how I used it for the KNN query, please see another branch I created that has a README.md:\r\nhttps://github.com/danielblazevski/flink/tree/FLINK-1745-devel/flink-staging/flink-ml/src/main/scala/org/apache/flink/ml/nn\r\n"},"comment":{"url":"https://api.github.com/repos/apache/flink/issues/comments/145353515","html_url":"https://github.com/apache/flink/pull/1220#issuecomment-145353515","issue_url":"https://api.github.com/repos/apache/flink/issues/1220","id":145353515,"user":{"login":"chiwanpark","id":1941681,"avatar_url":"https://avatars.githubusercontent.com/u/1941681?v=3","gravatar_id":"","url":"https://api.github.com/users/chiwanpark","html_url":"https://github.com/chiwanpark","followers_url":"https://api.github.com/users/chiwanpark/followers","following_url":"https://api.github.com/users/chiwanpark/following{/other_user}","gists_url":"https://api.github.com/users/chiwanpark/gists{/gist_id}","starred_url":"https://api.github.com/users/chiwanpark/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/chiwanpark/subscriptions","organizations_url":"https://api.github.com/users/chiwanpark/orgs","repos_url":"https://api.github.com/users/chiwanpark/repos","events_url":"https://api.github.com/users/chiwanpark/events{/privacy}","received_events_url":"https://api.github.com/users/chiwanpark/received_events","type":"User","site_admin":false},"created_at":"2015-10-04T14:16:28Z","updated_at":"2015-10-04T14:16:28Z","body":"I just reviewed quickly. I have some comments for this pull request.\r\n\r\n1. This pull request cannot pass checking Scala code style. The Scala code should not exceed 100 characters in each line. I also found some wrong indentations such as line 200-211 in `KNN.scala` file. Please reformat your code.\r\n2. The meaning of `BruteOrQuad` is ambiguous. From my understand, if `BruteOrQuad` is true, we use quadtree implementation, right? So the other name such as `useQuadTree` would be better.\r\n3. Please remove blank line after Scala doc comments.\r\n4. Your implementation assumes that the type of given `Vector` is `DenseVector`. But basically, there is no guarantee of the type of `Vector`. We should generalize the implementation.\r\n5. We should be able to configure the use of quadtree implementation. Please add configure parameter into `KNN` object.\r\n6. Currently, `predictDataSet` is too big and complex because of large code in `mapPartition` operation. How about split the operation into `mapPartition` for raw and quadtree?\r\n7. Please avoid calculation of `BigDecimal`. Maybe we can check whether we use quadtree or not without `BigDecimal` like following:\r\n  * `(4 ^ dim) * Ntest * log(Ntrain) < Ntest * Ntrain` is same as `dim + log_4(log(Ntrain)) < log_4(Ntrain)`\r\n\r\nThis is great start! If you have some question about my comments, please feel free to reply.\r\n\r\nP.S.: How about create training quadtree before cross operation? Is there any intention to create quadtree after cross operation?"}}