My K parameter did nothing

For every one of the ~7,000 detections in an image, I needed a statistic computed over that detection’s ~120 nearest neighbours. Doing it naively means measuring every point against every other point, roughly 49 million distance evaluations per image, with several images running concurrently. So, obviously: build a spatial index.

I built a uniform grid, and it worked. Then I tried tuning K for a different dataset with different features to detect. The result was the same; nothing changed. It felt like somewhere past a few hundred, K simply stopped doing anything, and no error is shown.

The problem

Okay, say you are handed a set of points in a 2D image, say ~7,000 detections. The distribution is roughly uniform, with each point having a feature attached to it. You need to compare each point’s feature to the features of its K nearest neighbours to compute a local statistic.

Seems simple enough, right? Just measure the distance for each point, and compute the statistic. However, that would be too slow because each point has to compare itself to every other point, which is O(n²) in time complexity. Instead, we can use a spatial data structure to speed up the nearest neighbour search.

The query set is the point set — an important point to note. Building the index costs about O(n), while each query is about O(K) distance evaluations, far fewer than the O(n) a brute-force query costs (and O(n²) across all n points).

Spatial Grid to the Rescue

A spatial grid is a simple and effective way to partition the 2D space into cells, allowing us to quickly find nearby points. By dividing the image into a grid of cells, we can limit our search for nearest neighbours to only those points that are in the same cell or nearby cells, widening the search ring by ring around the query’s cell until K neighbours have been found.

You can play with the parameters of the spatial grid and see how it affects the nearest neighbour search in the widget below. Adjust the cell size and K value to see how they impact the number of neighbours found and the performance of the algorithm.

There is a catch, though. The cell size is a critical parameter that determines how many points are in each cell.

1. If the cell size is too small, we may not find enough neighbours (even with ring expansion), which silently limits the maximum K value we can use.
2. If the cell size is too large, we may end up checking too many points, which can slow down the search.

This can be an issue: if the cell size is not chosen correctly, changing the K parameter may have no effect on the results. No crash, no NaN, no error bar screaming at you — just the same number, quietly wrong.

Compressed Sparse Row (CSR)

To store the grid efficiently, we borrow the Compressed Sparse Row idea from sparse matrix formats: all points go into one flat items[] array, grouped contiguously by cell, with a start[] offset table holding one entry per cell (plus one). An empty cell costs a single integer, not a list object. The construction is a counting sort: tally each point into start[b + 1], prefix sum the tallies into offsets, then scatter points through a disposable clone of start. Two linear passes over the points, zero allocation per point.

// Build a uniform grid over the bounding box; [start, items] is the CSR result.
function buildGrid(pts, cell, nx, ny) {
  const nCells = nx * ny;
  const start = new Array(nCells + 1).fill(0); // one entry per cell, plus sentinel
  const items = new Array(pts.length);

  // Pass 1: tally each point into the cell after its own.
  for (const p of pts) {
    const b = cellIndex(p, cell, nx, ny);
    start[b + 1]++;
  }

  // Prefix sum the tallies into offsets.
  for (let i = 0; i < nCells; i++) {
    start[i + 1] += start[i];
  }

  // Pass 2: scatter points through a disposable clone of start.
  const cursor = start.slice();
  for (const p of pts) {
    const b = cellIndex(p, cell, nx, ny);
    items[cursor[b]++] = p.index;
  }
  return [start, items];
}

The widget below demonstrates exactly that construction. Step through it and watch the arrays fill.

To answer a query, locate the point’s cell and collect candidates from it, then widen the search ring by ring until enough neighbours are found or the maximum ring limit is reached. Each ring restarts collection instead of extending the previous one, since the common case exits at ring 1 and rescanning is easier to implement. Distances stay squared throughout (identical ordering, no sqrt in the innermost loop), and selection inserts into a fixed K length sorted array rather than sorting all candidates.

Why not a KD-tree?

Using a KD-tree is another common approach for nearest neighbour search, but it isn’t the right fit here:

1. The distribution is roughly uniform and bounded by the image rectangle. A KD-tree’s adaptive splits pay off on clustered or unbounded data; with nothing to adapt to, its extra structure is wasted.

2. Query set == point set, so we build the index once and run n queries either way. Both builds are amortised over those n queries, so build time is not the differentiator — but the grid allocates just two int[] arrays with zero per-point allocation, whereas a KD-tree builds a node object per point. That matters when several images run concurrently and the allocator is under load.

3. The grid’s query is expected O(K) distance evaluations that walk a contiguous CSR array, while a KD-tree query backtracks through pointer linked nodes. For large K that pointer chasing and poor cache locality dominate, whereas the grid’s flat, sequential access stays fast.

   KD-trees aren’t bad, they’re just not the right tool for this specific problem.

What about Quadtree?

Quadtree is another spatial data structure that can be used for nearest neighbour search. However, it has similar issues to KD-trees in this case. The uniform distribution of points and the bounded nature of the image leave the quadtree’s adaptive subdivision with nothing to adapt to, all these extra gymnastics are wasted.

If the points were clustered or had varying density, a quadtree might be a better choice. But in this case, the spatial grid is the most appropriate data structure for the problem at hand.

The failure mode: my first guess is capped K

The typical gap between points, the pitch, can be estimated from the bounding box alone (the derivation is coming), so make each cell two pitches wide. It looks fine where there are roughly four points per cell, and most queries finish within ring 1.

But a ring-limited search has a hard ceiling that you can write down. A search that gives up after maxRing rings can reach at most:

With maxRing = 4 and cell = 2 · pitch: K_max = 81 * 4 = 324. Now replay what happens:

1. Ask for K ≤ 324: everything works, and the results look reasonable.
2. Ask for K = 500: the rings exhaust themselves, the loop exits at maxRing, and the search returns the 324 neighbours it managed to gather. No error, no warning.
3. The statistics are computed from 324 neighbours whether you asked for 400 or 4,000.

And the not-judgeable gate does not catch this — it only fires below minNeighbours (I set 8), a threshold that sits far below K, so 324 neighbours sails straight through. The guardrail was measuring the wrong quantity: it was built for voids and edges, not for a shortfall against K.

The parameter did not fail. It was capped by the geometry of the index, and the number I typed only agreed with reality by coincidence.

The cell size must be computed backwards from K.

The solution: compute the cell size based on K

Everything we need is already in the data. Start with the bounding box, the largest and smallest coordinates:

Assuming the points are uniformly distributed across that area, every point owns roughly the same amount of real estate: a patch of $\frac{w \cdot h}{n}$. Note what is not happening here; no distance between points is ever measured. We take the side length of that patch as an estimate of the typical gap between neighbouring points, and call it the pitch:

For detections laid out on a regular pattern, dots on a grid, LEDs on a panel, that patch is close to a literal square, and its side really is the centre to centre spacing, so the estimate lands almost exact. For noisier layouts the number drifts away from any true pairwise distance; treat it as a scale, not a measurement. Either way, it is precisely the quantity the cell size rule needs.

Now, how many points does a cell of side length $\text{cell}$ hold? A cell spans $\left(\frac{\text{cell}}{\text{pitch}}\right)^2$ pitch sized squares worth of area, so on average:

A search that expands out to ring $r$ scans a $(2r+1)^2$ block of cells, so the number of points reachable at ring $r$ is:

Here is the requirement that drives everything: ring 1 alone - the $3 \times 3$ block of 9 cells, should comfortably hold $K$. We target $2K$ rather than $K$ for slack against local density variation:

Solve for the ratio, then scale it by the pitch to get the actual cell dimension:

Sanity check with $K = 120$: $\sqrt{2 \cdot 120 / 9} \approx 5.16$, so the cell is about five pitches wide, and ring-1 capacity is $9 \cdot 5.16^2 \approx 240 = 2K$. ✓

When I wrote it out this way the fix felt obvious, but getting here took longer than I’d like to admit. The entire derivation is just algebra — but the hard part was realizing that the cell size was my problem to solve, not a free parameter I could set once and forget.

One clarification worth pinning down: $2K$ is the size of the candidate pool that ring 1 is sized to hold, not the amount returned. Every candidate in the pool competes by distance, and the search keeps exactly the best $K$ of them (or fewer, plus the not judgeable sentinel). The doubling exists purely so that this cut usually happens while still inside ring 1.

This fixes the K-does-nothing failure. Under the fixed rule, ring-1 capacity was some constant the cell size happened to imply, and $K$ was silently capped by it. Under this rule, ring-1 capacity is $2K$ for any $K$, so the search is never ring-limited and $K$ always means what it says.

Two practical floors are applied on top:

1. $\frac{\text{cell}}{\text{pitch}} \geq 2.0$, binds below $K = 18$, preventing tiny values of $K$ from producing absurdly small cells and a huge grid array.
2. $\text{cell} \geq 4\,\text{px}$, guards against degenerate bounding boxes and sub-pixel pitches.

And yes - the uniformity assumption is doing work here. That is precisely what the factor of two is insurance against.

The ring cap is what “local” means

The cell-size rule fixes the count problem, but maxRing is for another purpose and that it is the only place the algorithm says what “local” means. And it is expressed in the wrong units.

Re-read the ceiling from the failure mode:

That is a count, but every other quantity in the algorithm is a distance. maxRing · cell is a distance too — it is just measured in cells, so it silently moves when the cell size moves. Hold maxRing = 4 and compare:

Same parameter, 2.6x different physical reach. That coupling is the bug, restated more intuitively than “324”: the K-th neighbour of a uniform field sits at $\sqrt{K/\pi}$ pitches, so at K = 500 it needs 12.6 pitches of reach, but a fixed 2·pitch cell only ever reaches 9. It can never reach there.

That bug is caused by that two factor. It needs both a fixed cell size and a ring cap. We could remove the cap and let rings expand until the block covers the whole grid: K would then be bounded only by n - 1, the true limit, and the saturation disappears. However, the cell size doesn’t just “stop mattering” once you do that, it just shift from being a correctness parameter to becomes a performance one.

Unbounded expansion needs to recompute every ring it passed through (the query loop rescans the whole block each ring, not just the new shell), and worse, on a point in a void it keeps expanding until neighbours arrive from halfway across the image: a confident wrong answer that looks valid, and the not-judgeable sentinel never fires again. The cap is the feature that avoid the search to become global.

it is needed because under the auto rule, the cap goes K-independent. Substitute cell = √(2K)/3 · pitch into the reach:

The K cancels. At maxRing = 4 the reach is 3.76x the expected K-th distance, for any K. maxRing stops being a grid detail and becomes a clean statement of policy: I accept a neighbourhood up to ~3.8x more spread out than the global density predicts; past that the region isn’t comparable and I return not judgeable. (Area scales as radius², so equivalently: give up when local density falls below about 1/14th of global.) Contrast the fixed cell, where the same ratio is 4.5 · 2 / √(K/π) — it shrinks with K, from 1.5x at K = 120 to 0.7x at K = 500, silently tightening the locality tolerance exactly as you ask for more neighbours.

The numbers

Operation counts, not wall clock; At these sizes wall clock is dominated by whatever else the pipeline is doing.

One non obvious consequence of the sizing rule: expected points per cell is $2K/9$, so the offset table holds only $n / (2K/9)$ cells, about $n/27$ at $K = 120$. In bytes the whole index is small — two int[] arrays come to ~4.2 B/point against the 16 B/point of float64 coordinates — and it shrinks further as K grows.

Boundaries

Ring expansion is limited by the image boundaries, and by maxRing. If a point is near the edge of the image, the search may not be able to expand fully in all directions; it expands in the directions available until it reaches either K neighbours or the cap.

If the search hits the cap without finding enough neighbours, it returns a sentinel meaning the point is not judgeable. But “enough” here is gated by minNeighbours (about 8), not by K — a threshold that sits far below K on purpose. It exists for voids and edges where almost no points exist, not for the K = 500 shortfall in the failure mode, where 324 neighbours is plenty by its standard. The cap and the not-judgeable sentinel are the same mechanism viewed two ways: the cap fires exactly where the uniformity assumption behind the cell-size rule fails, so the sentinel is really a uniformity-assumption detector — it is the only signal that the density estimate rested on a false premise.

Yes, it is only an approximation

The scanned region is a square of cells, but the true K-nearest set is a disc. The ring-1 margin we computed earlier — $\sqrt{2\pi}/2 \approx 1.25$ at the cell centre, shrinking to $\sqrt{2\pi}/3 \approx 0.84$ at a corner — is the same geometry as the locality cap above, just evaluated at a smaller radius. Multiply the reach in cells by $\sqrt{2\pi}/3 \approx 0.836$ and you get the ratio to the expected K-th distance: the cap sits at 4.5 cells (3.76x), ring 1 at 1.5 cells (1.25x) or 1.0 cell (0.84x).

So “strict containment always holds” is false: the mean margin works out to about 0.98 — a query uniform in its cell sits $1 + \mathbb{E}[\min(a,b)] \approx 1.167$ cells from the nearest ring-1 edge, times 0.836 — so containment fails for roughly half of query positions. But containment failure is not a wrong answer: it only opens the door to a swap, and the sliver of disc lying outside the square block is a small fraction of its area, only sometimes occupied by a point that would displace an insider. The approximation is sound because the occasional miss is a rounding error on the statistic, not a systematic bias.

Exactness would require an “expand until the ring’s inscribed circle exceeds the current K-th distance” test, which is more work than this application justifies. Occasional swaps are acceptable noise — the alternative is exact KNN with a heavier query loop, not the sentinel, which exists for a different failure entirely.

Wrap up

This approach computes K nearest neighbours over large point sets with predictable behaviour: the cell size derives from the data, ring capacity tracks K by construction, and the index declines to answer when it genuinely cannot.

When a knob does nothing, the problem isn’t the knob, it’s likely the infrastructure around it silently eating your input. Some parameters shouldn’t be exposed to the user at all. The cell size is one of them in this case: it should be computed from K and the data, not set arbitrarily to randomly hit the correct value.

A parameter expressed in units of an implementation detail will silently change meaning when that detail changes. maxRing looked like a simple grid constant until the cell size moved under it and the locality tolerance swung from 1.5x to 0.7x. Cap the neighbourhood by distance in pitch units — “a neighbour must lie within some multiple of $\sqrt{K/\pi} \cdot \text{pitch}$” — and the locality guarantee stops depending on grid geometry altogether. Cell size becomes purely a throughput knob; the cap becomes purely a statement about what counts as local.