thesamet/kdtree-scala

KDTree and KDTreeMap implementation in Scala

KDTree-Scala

A simple in-memory immutable KDTree and KDTreeMap implementations in Scala.

Currently the only operation supported is n-nearest neighbors lookup.

Using with SBT

Add the following to your build.sbt:

resolvers += "Sonatype OSS Releases" at "http://oss.sonatype.org/content/repositories/releases/"

libraryDependencies += "com.thesamet" %% "kdtree" % "1.0.4"

Examples

See src/test/scala/ for examples.

kdtree-scala's Issues

regionQuery supported but README states that only neighbours lookup supported

Nice implementation. I need a KD-Tree implementation with region query support and I was initially put off by the statement in the README that

Currently the only operation supported is n-nearest neighbors lookup

But looking at the code, it seems that region queries are supported.

So, is it true that I should be able to use this to find all nodes within a “region”. eg. within a rectangular area for a 2D dataset?

findNearest request maxDistance

requesting findNearest to have two arguments, number of neighbors, and max distance.
either of which can be zero (ie, unused), but not both. (0 nearest neighbors or max distance of 0 has no meaning) so that I can find as many neighbors all the neighbors within a distance.

Please add WithinHypersphere and OutsideHypersphere to Region.scala

Requesting hypersphere regions

Please cut a new release

Hi Nadav.

Please would you cut a new release of kdtree-scala incoporating the changes you merged?

Thanks, David

KDTree for a N dimension point

Trying to create the KDTree to apply points with N dimension (i.e a point with seq of dimensions e.g Point(x:Array[Int]) ) it seems like the challenge is with the denominational ordering. if you have any idea please share it ([email protected])

Support approximating medians when building kd-tree

When building a kd-tree, you are sorting the data at every level of the recursive call to buildTreeNode. I believe this leads to at least a quadratic runtime performance.

The wikipedia entry for KD Trees mentions that

a popular practice is to sort a fixed number of randomly selected points, and use the median of those points to serve as the splitting plane

It would be nice to have this option. For my particular application, I need to build a tree of N nodes and then perform up to N range queries before discarding the tree. If building the tree is an N^2 operation, then I think I would be better off avoiding using a tree and just use a brute force approach.

KDTree for a N dimension point

Trying to create the KDTree to apply points with N dimension (i.e a point with seq of dimensions e.g Point(x:Array[Int]) ) it seems like the challenge is with the denominational ordering. if you have any idea please share it ([email protected])