Skip to content

fpsample

fpsample is a small Rust library exposing farthest-point sampling to Python. It solves exactly one problem — Euclidean max-min selection — and solves it very fast.

Its interest here is as the speed reference. Where RDKit buys scale through laziness, fpsample buys it through a compiled implementation and spatial indexing: its KD-tree variants avoid scanning every candidate on every pick. That indexing is also its constraint, since tree structures lose their advantage as dimension grows, and the documented practical range stops around \(d \approx 9\).

If your problem is Euclidean, unconstrained, and you want an answer in milliseconds, this is a better tool than max-div.

Problem targeted

Given \(n\) vectors in \(\mathbb{R}^d\) and a target size \(k\), it approximates

\[ \max_{|S| = k} \; \min_{i \ne j \in S} \lVert x_i - x_j \rVert_2 \]

by farthest-point traversal, with the same greedy step RDKit uses but accelerated by a spatial index rather than evaluated lazily.

Guarantee: 2-approximation. Identical to any farthest-point traversal — the implementation changes the speed, not the bound.

Reference

At a glance
Guarantee 2-approximation (farthest-point traversal)
License MIT
Version 1.0.2
Released 2025-12-20
Determinism deterministic
Input vectors
Source https://github.com/leonardodalinky/fpsample
Last verified 2026-07-27

Capabilities

Support: ✔ built in · ◐ reachable, but you supply the model, transform or metric · — not available

Capability Support Notes
distance metrics · L1 (Manhattan) distance —
distance metrics · L2 (Euclidean) distance ✔
distance metrics · cosine distance ◐ 1
distance metrics · caller-supplied distances — 2
diversity objectives · maximize the minimum separation ✔
diversity objectives · maximize the mean nearest-neighbor separation —
diversity objectives · maximize the geometric-mean nearest-neighbor separation —
diversity objectives · maximize the mean pairwise distance —
constraints beyond k · per-group counts over disjoint groups —
constraints beyond k · per-group counts over overlapping groups —
constraints beyond k · minimum and maximum counts per group —
time budget · budget expressed as an iteration count —
time budget · budget expressed as wall-clock time —
time budget · the answer improves when given more budget — 3
largest practical problem size n ≈ 106 4

  1. Reachable by L2-normalizing the vectors first: on the unit sphere, cosine distance is a monotone function of Euclidean distance, so a Euclidean picker returns the same ordering. ↩

  2. Euclidean only. The KD-tree variants depend on it structurally, so this is not a gap waiting to be filled. ↩

  3. A single construction pass, so there is no budget to spend: the answer is whatever one greedy sweep produces, and waiting longer does not change it. ↩

  4. A Rust implementation with KD-tree accelerated variants, so the traversal avoids the O(nk) distance evaluations a naive sweep needs. The tree variants degrade in high dimension and are documented as practical below roughly d ≈ 9; the plain variant has no such limit. ↩