CkNN rescaled distance

The Continuous k-Nearest Neighbours construction of Berry & Sauer (2016): a density-rescaled distance

d̃_ij = d_ij / √(ρ_i ρ_j),   where ρ_i = distance to the k-th nearest neighbour.

Try it: why a fixed radius can’t win

A dense and a sparse cluster. In fixed-radius mode, sweep ε — the third card sweeps every radius and reports that none gives the correct two-component answer (the sparse cluster fragments, or the two bridge). Switch to CkNN and a whole band of δ works. Try the organic datasets too.

data dense sparse

radius ε10.0

k (density)3

Components

–

This setting

–

Any value that works?

–

What it means

A fixed connection radius can’t cope with varying density — too small and sparse regions fall apart, too large and dense regions bridge together. Dividing by the local bandwidths √(ρ_iρ_j) normalises density away, so one scale δ works everywhere. Two readouts come from the same matrix:

Topology — threshold d̃ < δ for the (unweighted) CkNN graph; feed d̃ to a Vietoris–Rips persistence engine. Because density is normalised, a single graph captures features at all scales at once (“consistent homology”), and it recovers the correct topology even on non-compact manifolds where no fixed radius can.
Geometry — the self-tuning kernel is just exp(−d̃²); its graph Laplacian is a consistent estimator of the Laplace–de Rham operator.

This is the fuzzy-TDA thread made concrete — with the twist that, for topology, the winning move is to keep the graph unweighted but make its radius density-adaptive, rather than to add a taper.

Try it: the persistence diagram

Feeding d̃ to a Vietoris–Rips persistence reducer gives a consistent diagram. On data with varying sampling density (an unevenly-sampled ring, a dense core inside a sparse ring), the raw-distance diagram smears the real loop because one connection scale can’t serve both densities; the CkNN diagram pins it as a single point far above the diagonal. (Computed in-browser by the same reducer as src/spatial/persistence.ts.)

datak 3 H₀ components H₁ loops

Raw distance

–

CkNN d̃ = d / √(ρᵢρⱼ)

–

Points far above the diagonal are persistent features (real topology); points hugging the diagonal are noise. Axes are each normalised to their own scale.

GPU approach

A composition: k-th neighbour distance (WGSL template) gives ρ; a "use gpu" kernel then builds the N×N rescaled-distance matrix. The persistence reduction itself stays on the CPU (Ripser/GUDHI) — the GPU’s job ends at d̃.

Usage

import {
  cknnRescaledDistanceGpu, cknnGraph, selfTuningWeights,
} from 'intraspatial/gpu/spatial/cknn';

const { rescaled, rho, n } = await cknnRescaledDistanceGpu(xs, ys, { k: 5 });
const graph   = cknnGraph(rescaled, n, /* δ */ 1.2);   // unweighted adjacency (topology)
const weights = selfTuningWeights(rescaled, n);        // exp(−d̃²) (geometry)

Status: ✅ implemented and validated (matches CPU; density-normalisation property holds) · src/gpu/spatial/cknn.ts