flink-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From danielblazevski <...@git.apache.org>
Subject [GitHub] flink pull request: [FLINK-1745] Add exact k-nearest-neighbours al...
Date Wed, 14 Oct 2015 16:55:55 GMT
GitHub user danielblazevski reopened a pull request:

    https://github.com/apache/flink/pull/1220

    [FLINK-1745] Add exact k-nearest-neighbours algorithm to machine learning library

    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.
    
    For more details on the quadtree + how I used it for the KNN query, please see another
branch I created that has a README.md:
    https://github.com/danielblazevski/flink/tree/FLINK-1745-devel/flink-staging/flink-ml/src/main/scala/org/apache/flink/ml/nn


You can merge this pull request into a Git repository by running:

    $ git pull https://github.com/danielblazevski/flink FLINK-1745

Alternatively you can review and apply these changes as the patch at:

    https://github.com/apache/flink/pull/1220.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 #1220
    
----
commit c7e5056c6d273f6f0f841f77e0fdd91ca221602d
Author: Chiwan Park <chiwanpark@apache.org>
Date:   2015-06-30T08:41:25Z

    [FLINK-1745] [ml] Add exact k-nearest-neighbor join

commit 9d0c7942c09086324fadb29bdce749683a0d1a7e
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-15T21:49:05Z

    modified kNN test to familiarize with Flink and KNN.scala

commit 611248e57166dc549f86f805b590dd4e45cb3df5
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-15T21:49:17Z

    modified kNN test to familiarize with Flink and KNN.scala

commit 1fd8231ce194b52b5a1bd55bbc5e135b3fa5775b
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-16T01:26:57Z

    nightly commit, minor changes:  got the filter to work, working on mapping the training
set to include box lables

commit 15d7d2cb308b23e24c43d103b85a76b0e665cbd3
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-22T02:02:51Z

    commit before incporporating quadtree

commit 8f2da8a66516565c59df8828de2715b45397cb7f
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-22T15:49:25Z

    did a basic import of QuadTree and Test; to-do:  modify QuadTree to allow KNN.scala to
make use of

commit e1cef2c5aea65c6f204caeff6348e2778231f98d
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-22T21:03:04Z

    transfered ListBuffers for objects in leaf nodes to Vectors

commit c3387ef2ef59734727b56ea652fdb29af957d20b
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-23T00:41:29Z

    basic test on 2D unit box seems to work -- need to generalize, e.g. to include automated
bounding box

commit 48294ff37a5f800e5111280da5a3c03f4375028d
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-23T15:03:06Z

    had to debug quadtree -- back to testing 2D

commit 6403ba14e240ed8d67a296ac789e7e00dece800d
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-23T15:22:46Z

    Testing 2D looks good, strong improvement in run time compared to brute-force method

commit 426466a40bc2625f390fe0d912f56a346e46c8f8
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-23T19:04:52Z

    added automated detection of bounding box based on min/max values of both training and
test sets

commit c35543b828384aa4ce04d56dfcb3d73db46d1e6d
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-24T00:28:56Z

    added automated radius about test point to define localized neighborhood, result runs.
 TO-DO:  Lots of tests

commit 8e2d2e78f8533d4192aebe9b4baa7efbfa5928a5
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-24T00:54:06Z

    Note for future:  previous commit passed test of Chiwan Park had in intial knn implementation

commit d6fd40cb88d6e198e52c368e829bf7d32d432081
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-24T01:56:38Z

    Note for future:  previous commit passed 3D version of the test that Chiwan Park had in
the intial knn implementation

commit 0ec1f4866157ca073341672e7fe9a50871ac0b7c
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-24T14:27:20Z

    changed filename of QuadTreeTest to QuadTreeSuite, about to make test more comprehensive
and similar format to other Flink tests

commit ac81561cad27b65d158ae08fd0fb15bdb51d1c8b
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-24T19:51:32Z

    refactored testing of QuadTree, and added more tests

commit b17f82d5ce0214617c8dbc4a387410057d6f3832
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-24T22:49:10Z

    added KNNBenchmark to check runtimes

commit 530565835d4b5934fcac9e0e51105bb669fec9be
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-24T22:49:17Z

    added KNNBenchmark to check runtimes

commit 1f946cb30450604e92bbd0f5959ce9a60eb4c41b
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-25T01:13:00Z

    fixed bug -- in find siblings, needed to search for minimal bounding boxes

commit 22e4eb7b57795ad1ca4392ca1c1a8bdae76afa8e
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-27T03:34:16Z

    added more thorough benchmark files; about to modify  bounding box to only bound training
set and modify search for the testing set

commit 3723f6b09ec7d45f6444df70a5f699cbf998a4bb
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-27T03:34:21Z

    added more thorough benchmark files; about to modify  bounding box to only bound training
set and modify search for the testing set

commit c41d3e1029bf81a37cf3594f202b904e2d99e3ac
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-28T03:53:12Z

    major simplification in choosing the radius to look at nearby neighbors

commit 7c77ea20fd9e8a0c4a33c81b83187c84b380d6b2
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-28T04:03:59Z

    cleaned up; commit before deleting previous sibling search

commit cf4aa5d75611db19040466040c3d29432cb0e5f7
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-09-28T14:02:51Z

    added new devel branch to push temp changes on github

commit ec6ddb0a57136075b4f77616e6e48eb5bcc50a11
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-10-01T00:17:33Z

    cleaned up; removed comments and a unused method

commit 7ed9926d8207b5f59b4ceb968d7ebd732029f5c3
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-10-01T20:28:31Z

    fixed bug in bFiltVect, and renamed to trainingFiltered

commit 4b3bb2ec92396bf754d0d207ffc6853406ce7c39
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-10-01T21:05:46Z

    fixed bug:  if there are fewer than maxPerBox total training points, do not do heap construction,
just make siblingsQueue = root.objects

commit 1662b38822dfdfbbca272d377fa3b94f8246e9e6
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-10-01T22:03:42Z

    added metric to constructor, and added a flag to test whether it is Euclidean or SquaredEuclidean

commit f654b841cc8d91fa861f188469831404c288b227
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-10-01T22:48:51Z

    changed name of test that uses the Quadtree along with KNN -- modified from CHiwan Park's
test to ensure flag to use Quadtree will pass

commit 7928798281dba5554eeb63df7e67400a42e7a381
Author: danielblazevski <daniel.blazevski@gmail.com>
Date:   2015-10-01T22:54:25Z

    fixed QuadTree test to conform to using a min-heap

----


---
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.
---

Mime
View raw message