solow_neighbors/lib.rs
1//! # solow-neighbors
2//!
3//! Nearest-neighbor data structures and estimators for the Solow
4//! statistical stack.
5//!
6//! The crate ships a **KDTree** — the balanced k-dimensional binary
7//! space partition tree — for `O(log n)` amortised nearest-neighbour
8//! and radius queries in low-to-moderate dimensions, together with two
9//! estimators that consume it:
10//!
11//! * [`KNeighborsClassifier`] — majority-vote classification over the
12//! `k` nearest labelled neighbours, with optional distance-weighted
13//! voting (uniform vs `1/d`).
14//! * [`KNeighborsRegressor`] — mean of the `k` nearest neighbour target
15//! values (uniform or distance-weighted).
16//!
17//! Every estimator exposes the classical the reference `fit` /
18//! `predict` / `predict_proba` shape. The tree is built once at fit
19//! time; predict on `m` new points is `O(m · k · log n)` in expectation.
20//!
21//! ## Complexity
22//!
23//! * [`KdTree::build`]: `O(n · log n)` time, `O(n)` space, using the
24//! median-split classical construction with an in-place bounding-box
25//! pruning key.
26//! * [`KdTree::k_nearest`]: `O(k · log n)` expected time in low `d`,
27//! degrades to `O(n)` as `d` grows (the classical KD-tree curse of
28//! dimensionality).
29//! * [`KdTree::radius`]: `O(log n + m)` where `m` is the answer size.
30//!
31//! For high-dimensional data (`d ≥ 30`) prefer brute-force scanning —
32//! the KDTree still returns the correct answer but no longer beats an
33//! `O(n · d)` sweep.
34//!
35//! ## Determinism
36//!
37//! Construction is fully deterministic: the median split picks the
38//! lower-index sample on ties, so `KdTree::build` on the same input
39//! always produces the same tree. Queries are deterministic given the
40//! tree.
41//!
42//! ## References
43//!
44//! * Bentley, J. L. (1975). *Multidimensional binary search trees used
45//! for associative searching.* Communications of the ACM, 18(9),
46//! 509-517.
47//! * Friedman, J. H., Bentley, J. L., & Finkel, R. A. (1977). *An
48//! algorithm for finding best matches in logarithmic expected time.*
49//! ACM Transactions on Mathematical Software, 3(3), 209-226.
50
51#![forbid(unsafe_code)]
52#![warn(missing_docs)]
53
54pub mod ball_tree;
55pub mod centroid;
56pub mod kde;
57pub mod kdtree;
58pub mod knn;
59pub mod lof;
60pub mod radius;
61
62pub use ball_tree::BallTree;
63pub use centroid::NearestCentroid;
64pub use kde::{KdeKernel, KernelDensity};
65pub use kdtree::{KdTree, Neighbor};
66pub use knn::{KNeighborsClassifier, KNeighborsRegressor, WeightKind};
67pub use lof::LocalOutlierFactor;
68pub use radius::{RadiusNeighborsClassifier, RadiusNeighborsRegressor};
69
70/// Commonly-used imports.
71pub mod prelude {
72 pub use crate::ball_tree::BallTree;
73 pub use crate::centroid::NearestCentroid;
74 pub use crate::kde::{KdeKernel, KernelDensity};
75 pub use crate::kdtree::{KdTree, Neighbor};
76 pub use crate::knn::{KNeighborsClassifier, KNeighborsRegressor, WeightKind};
77 pub use crate::lof::LocalOutlierFactor;
78 pub use crate::radius::{RadiusNeighborsClassifier, RadiusNeighborsRegressor};
79}