Nearest Neighbour algorithms
Nobody has claimed this yet.
- 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
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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