oxvox neighbour search benchmark

Headline: the fastest exact method per dataset family

Each cell names the exact method that won the most grid points in that column, how many of them it won, and the median factor by which it beat scipy's cKDTree there.

Query time against cloud size

One panel per dataset, log-log. Pick the neighbour count, the density and the query batch; switch the metric to see the same measurements as a speed-up over scipy, where the dotted line at 1.0 is scipy itself. A missing point is a configuration the harness skipped as projected too slow — the skip table at the bottom says which.

Where the index build stops paying for itself

Build time plus query time against the number of queries answered, for one cloud. A method with a cheaper build wins the left of the chart however fast its queries are; the crossing point is the batch size above which the better query time takes over.

Counting neighbours

The count_neighbours workload: how many search points lie within the radius of each query, with no k bound at all. Open3D is absent because it exposes no count query. Log-log, one panel per dataset.

How much the approximate backend misses

Recall of the graph backend against scipy's answers, on the 2048-query correctness subsample: the fraction of the true neighbours it returned. It never returns a point outside the radius, so what recall measures is omission, not error.

Over 276 checks its kNN recall has a median of 1.0000, a minimum of 0.9853, and is at least 0.99 on 98% of them. Counting is the workload it cannot do: its exact-count agreement falls as low as 2.3% of query points on the dense clouds, because a flood that stops at the k-th best neighbour has no reason to visit every point in the radius.

Correctness

Every exact implementation has to reproduce scipy's distances. Index sets are only compared where the distances are all distinct, since a tie lets any implementation return either point.

The exact backends reproduce scipy's neighbour counts on every check but 25 of 552, and there they differ by one neighbour in 0.2% of query points, only on real scan A, real scan B, scene at 0.05 m, 0.2 m, 0.422419 m. That is the radius boundary, not a bug: scipy counts a point at exactly the radius, oxvox does not (d² < r²), and a real scan's quantised coordinates put points exactly there.

Fastest exact method at every grid point

What was not measured

35 configurations were skipped, each because the harness projected it past a time or memory limit (see the run's options in the results JSON).