Mailing-List: contact issues-help@flink.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@flink.apache.org
Date: Wed, 18 May 2016 13:42:13 +0000 (UTC)
From: "ASF GitHub Bot (JIRA)" <jira@apache.org>
To: issues@flink.apache.org
Message-ID: <JIRA.12783173.1426760190000.223648.1463578933020@Atlassian.JIRA>
In-Reply-To: <JIRA.12783173.1426760190000@Atlassian.JIRA>
References: <JIRA.12783173.1426760190000@Atlassian.JIRA> <JIRA.12783173.1426760190413@arcas>
Subject: [jira] [Commented] (FLINK-1745) Add exact k-nearest-neighbours
 algorithm to machine learning library
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
archived-at: Wed, 18 May 2016 13:42:14 -0000


    [ https://issues.apache.org/jira/browse/FLINK-1745?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15288970#comment-15288970 ] 

ASF GitHub Bot commented on FLINK-1745:
---------------------------------------

Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/1220#discussion_r63703823
  
    --- Diff: flink-libraries/flink-ml/src/main/scala/org/apache/flink/ml/nn/QuadTree.scala ---
    @@ -0,0 +1,352 @@
    +/*
    + * 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/LICENSE-2.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
    +
    +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
    +
    +/**
    + * n-dimensional 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/CSCI1321-F11/Code/src/util/Quadtree.scala
    + *
    + * Many additional methods were added to the class both for
    + * efficient KNN queries and generalizing to n-dim.
    + *
    + * @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) {
    +
    +  class Node(
    +    center: Vector,
    +    width: Vector,
    +    var children: Seq[Node]) {
    +
    +    val nodeElements = new ListBuffer[Vector]
    +
    +    /** for testing purposes only; used in QuadTreeSuite.scala
    +      *
    +      * @return center and width of the box
    +      */
    +    def getCenterWidth(): (Vector, Vector) = {
    +      (center, width)
    +    }
    +
    +    /** Tests whether the queryPoint is in the node, or a child of that node
    +      *
    +      * @param queryPoint
    +      * @return
    +      */
    +    def contains(queryPoint: Vector): Boolean = {
    +      overlap(queryPoint, 0.0)
    +    }
    +
    +    /** Tests if queryPoint is within a radius of the node
    +      *
    +      * @param queryPoint
    +      * @param radius
    +      * @return
    +      */
    +    def overlap(
    +      queryPoint: Vector,
    +      radius: Double): Boolean = {
    +      val count = (0 until queryPoint.size).filter { i =>
    +        (queryPoint(i) - radius < center(i) + width(i) / 2) &&
    +          (queryPoint(i) + radius > center(i) - width(i) / 2)
    +      }.size
    +
    +      count == queryPoint.size
    --- End diff --
    
    this condition could written more succinctly via `(0 until queryPoint.size).forall{...}`


> Add exact k-nearest-neighbours algorithm to machine learning library
> --------------------------------------------------------------------
>
>                 Key: FLINK-1745
>                 URL: https://issues.apache.org/jira/browse/FLINK-1745
>             Project: Flink
>          Issue Type: New Feature
>          Components: Machine Learning Library
>            Reporter: Till Rohrmann
>            Assignee: Daniel Blazevski
>              Labels: ML, Starter
>
> Even though the k-nearest-neighbours (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 (H-BNLJ, H-BRJ) algorithm as proposed in [2].
> Could be a starter task.
> Resources:
> [1] [http://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm]
> [2] [https://www.cs.utah.edu/~lifeifei/papers/mrknnj.pdf]


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