Clustering algorithms cannot be fed a subset

TLDR

If a function computes its thresholds from the extent of its own input, calling it with a filtered subset does not give you the subset's part of the full answer. It gives you a different answer. Reconstructing a document table from only the line segments near it produced a two row grid where the whole page produced ten rows, from the exact same 24 segments.

The bug class

Adaptive algorithms are everywhere in parsing, layout and signal work. They look like this:

const gapThreshold = clusterGap(range(input));

The threshold is relative to the data. That is the whole point: it is what lets one function handle a dense table and a sparse one without a magic constant.

It also means the function is not decomposable. f(A ∪ B) restricted to A is not f(A). Filter the input and you have silently changed the algorithm's parameters.

The bug is attractive because filtering feels like an optimisation, and because the wrong answer is structurally valid. You get a grid. It is just the wrong grid.

The concrete instance

A user draws a box around a table and asks for it to be re-extracted as a ruled table. The obvious implementation collects the line segments inside the box and reconstructs a grid from them:

const near = matchSegments(allSegments, region.bbox);
const grid = new GridReconstructor(near, opts).reconstructAll()[0];

On a well-known deep learning paper's architecture table, near held all 24 segments the table is drawn from. Nothing was missing. The reconstruction returned a grid two rows tall and four columns wide, covering only the header strip.

Running the same reconstructor over the page's full segment list returned one candidate: ten rows, six columns, exactly matching the automatic detector. The six extra segments belonged to a completely different table lower down the page.

Those six segments contributed nothing to the grid. They changed the vertical extent of the input, which changed the row clustering threshold, which changed how the header rules grouped.

The fix

Stop filtering the input. Filter the output.

// Reconstruct over everything, exactly as the automatic detector does,
// then let the region pick the candidate it overlaps most.
const candidates = new GridReconstructor(allSegments, opts).reconstructAll();
const grid = pickByOverlap(candidates, region.bbox);
function pickByOverlap(candidates, bbox) {     let best = null, bestArea = -1;     for (const c of candidates) {         const iw = Math.min(bbox.x + bbox.w, c.bbox.x + c.bbox.w) - Math.max(bbox.x, c.bbox.x);         const ih = Math.min(bbox.y + bbox.h, c.bbox.y + c.bbox.h) - Math.max(bbox.y, c.bbox.y);         const area = (iw > 0 && ih > 0) ? iw * ih : 0;         if (area > bestArea) { bestArea = area; best = c; }     }     return best; }

Two things improved at once. The subset problem is gone, and picking by overlap fixed a separate latent bug: the old code took candidates[0], and the reconstructor returns candidates in no meaningful order. Even with correct input it could hand back a nested fragment instead of the grid.

The same fix applied to the borderless case, where a hand-rolled row bander was splitting eight rows into sixteen because it banded on vertical position while the real detector groups bands by an adaptive gap. Calling the real detector on the claimed items and picking by overlap made the override output byte-identical to the automatic output.

Preventing the class

Two habits.

Ask what the function's parameters depend on. If any threshold is derived from the input rather than passed in, the function is global over its input. Write that on the function.

/**
 * NOT DECOMPOSABLE. Row/column clustering thresholds are derived from the
 * extent of the segments passed in, so a subset clusters differently from
 * the page. Pass everything and filter the results.
 */

Prefer selecting over filtering. When you want a piece of an expensive global computation, run the global computation and select from its results. The instinct to narrow the input first is usually about performance, and it usually costs less than the bug does.

The lesson

Filtering an input is a semantic change, not a performance tweak, whenever the function looks at the shape of its input rather than each element in isolation. The tell is any threshold computed from a range, a mean, a standard deviation or a count. Those functions answer a question about the set, and a subset is a different set.