rust-ml / rust-ml/linfa

Nearest Neighbour algorithms

Open
#119 36 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

enhancement
Dominant language
Rust
Stars
4.7k
Forks
334
Avg merge
39m
Merged PRs (30d)
1

Description

Nearest neighbour algorithms are an item in the roadmap. They're helpful in clustering algorithms, particularly DBSCAN. There are a number of existing implementations of advanced nearest neighbour algorithms in the Rust ecosystem, but they are not compatible with ndarray so they'd need to be modified to be included in Linfa.

Existing algorithms I found:

  • Linear search: The simplest and least efficient method. O(N) time. Already exists in our DBSCAN implementation.
  • K-D tree: O(logN) data structure. The kdtree crate looks pretty solid.
  • BSP tree: O(logN) data structure. This binary_space_partition crate is pretty basic so I'm not sure how useful it is to us. BSP tree is also the nearest neighbour implementation use by SmartCore.
  • Ball tree: O(logN) as well. This ball_tree crate implements the algorithm.
  • R* tree: O(logN) algorithm. The rstar crate is the most well-maintained of the nearest neighbour implementations with existing benchmarks.

We should pick at least one of the O(logN) algorithms to integrate into Linfa, along with linear search due to its simplicity. I'm not sure how many of these algorithms we really need since I don't know the detailed tradeoffs between them.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

The issue names no repository files or tests. Start by reading the existing linear-search logic in the DBSCAN implementation and comparing the linked Rust crates, especially their compatibility with ndarray and their tradeoffs. Done means selecting at least one O(logN) algorithm and linear search for integration into Linfa.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
machine-learning
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.