[ https://issues.apache.org/jira/browse/FLINK1745?page=com.atlassian.jira.plugin.system.issuetabpanels:commenttabpanel&focusedCommentId=15049607#comment15049607
]
ASF GitHub Bot commented on FLINK1745:

Github user danielblazevski commented on a diff in the pull request:
https://github.com/apache/flink/pull/1220#discussion_r47168358
 Diff: flinkstaging/flinkml/src/main/scala/org/apache/flink/ml/nn/QuadTree.scala

@@ 0,0 +1,340 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.flink.ml.nn.util
+
+import org.apache.flink.ml.math.{Breeze, Vector}
+import Breeze._
+
+import org.apache.flink.ml.metrics.distances.{SquaredEuclideanDistanceMetric,
+EuclideanDistanceMetric, DistanceMetric}
+
+import scala.collection.mutable.ListBuffer
+import scala.collection.mutable.PriorityQueue
+
+/**
+ * ndimensional QuadTree data structure; partitions
+ * spatial data for faster queries (e.g. KNN query)
+ * The skeleton of the data structure was initially
+ * based off of the 2D Quadtree found here:
+ * http://www.cs.trinity.edu/~mlewis/CSCI1321F11/Code/src/util/Quadtree.scala
+ *
+ * Many additional methods were added to the class both for
+ * efficient KNN queries and generalizing to ndim.
+ *
+ * @param minVec vector of the corner of the bounding box with smallest coordinates
+ * @param maxVec vector of the corner of the bounding box with smallest coordinates
+ * @param distMetric metric, must be Euclidean or squareEuclidean
+ * @param maxPerBox threshold for number of points in each box before slitting a box
+ */
+class QuadTree(minVec: Vector, maxVec: Vector, distMetric: DistanceMetric, maxPerBox:
Int){
+
 End diff 
In case later down the road, someone may want to define a quadtree for some other purpose
and not need minDist, the kNN query only needs to enforce Euclidean/SquaredEuclidean because
of the minDist function that defines the distance between a point and a box
> Add exact knearestneighbours algorithm to machine learning library
> 
>
> Key: FLINK1745
> URL: https://issues.apache.org/jira/browse/FLINK1745
> Project: Flink
> Issue Type: New Feature
> Components: Machine Learning Library
> Reporter: Till Rohrmann
> Assignee: Daniel Blazevski
> Labels: ML, Starter
>
> Even though the knearestneighbours (kNN) [1,2] algorithm is quite trivial it is still
used as a mean to classify data and to do regression. This issue focuses on the implementation
of an exact kNN (HBNLJ, HBRJ) algorithm as proposed in [2].
> Could be a starter task.
> Resources:
> [1] [http://en.wikipedia.org/wiki/Knearest_neighbors_algorithm]
> [2] [https://www.cs.utah.edu/~lifeifei/papers/mrknnj.pdf]

This message was sent by Atlassian JIRA
(v6.3.4#6332)
