README-work

Algorithm::KDimensionalTree

Raku package with implementations of the K-Dimensional Tree (K-D Tree) algorithm.

Remark: This package should not be confused with "Algorithm::KdTree", [ITp1], which provides Raku bindings to a C-implementation of the K-D Tree algorithm. (A primary motivation for making this package, "Algorithm::KDimensionalTree", was to have a pure-Raku implementation.)

Remark: The versions "ver<0.1.0+>" with the API "api<1>" of this package are better utilized via the package "Math::Nearest".

Compared to the simple scanning algorithm this implementation of the K-D Tree algorithm is often 2÷15 times faster for randomly generated low dimensional data. (Say. less than 6D.) It can be 200+ times faster for "real life" data, like, Geo-locations of USA cities.

The implementation is tested for correctness against Mathematica's Nearest. (See the resource files.)

Features

Finds both top-k Nearest Neighbors (NNs).
- See the method k-nearest.
Finds NNs within a ball with a given radius.
- See the method nearest-within-ball.
Can return indexes and distances for the found NNs.
- The result shape is controlled with the adverb :values.
Works with arrays of numbers, arrays of arrays of numbers, and arrays of pairs.
Utilizes distance functions from "Math::DistanceFunctions".
- Which can be specified by their string names, like, "bray-curtis" or "cosine-distance".
Allows custom distance functions to be used.

Installation

From Zef ecosystem:

zef install Algorithm::KDimensionalTree

From GitHub:

zef install https://github.com/antononcube/Raku-Algorithm-KDimensionalTree.git

Usage examples

Setup

use Algorithm::KDimensionalTree;
use Data::TypeSystem;
use Text::Plot;

Set of points

Make a random set of points:

my @points = ([(^100).rand, (^100).rand] xx 30).unique;
deduce-type(@points);

Create the K-dimensional tree object

my $kdTree = Algorithm::KDimensionalTree.new(@points);

say $kdTree;

Nearest k-neighbors

Use as a search point one from the points set:

my @searchPoint = |@points.head;

Find 6 nearest neighbors:

my @res = $kdTree.k-nearest(@searchPoint, 6);
.say for @res;

Plot

Plot the points, the found nearest neighbors, and the search point:

my @point-char =  <* ⏺ ▲>;
say <data nns search> Z=> @point-char;
say text-list-plot(
[@points, @res, [@searchPoint,]],
:@point-char,
x-limit => (0, 100),
y-limit => (0, 100),
width => 60,
height => 20);