[Sad Catapella B6][Performance] Pixel-size single-linkage grouping can perform quadratic unique-calibration comparisons #95

Scope and classification

Sad Catapella Batch 6 at d7a538e56d41ac1093ba79adcad397c21b3dfd32. Confirmed worst-case O(U²) pairwise work, where U is the number of distinct, valid pixel-size vectors; no benchmarks run.

Evidence

• pixel_size_groups(), lines 354–382 deduplicates exact values and loops over sorted distinct sizes with a nested for j in range(i+1,...).
• The break condition tests only the first axis (X) lines 369–375; when many distinct X sizes differ by less than 0.1% but Y differs widely, nearly every pair is tested even though groups are unconnected.
• Called from metadata._check_pixel_sizes(), lines 795–805 whenever the experiment has calibration heterogeneity. Existing tests exercise only small sets.

Worst-case fixture / benchmarks

Generate U=100/1k/10k distinct (X,Y) physical sizes with X in [1.0000,1.0009] µm and Y spread over a broad range with no neighboring Y within the tolerance. The algorithm performs about U(U−1)/2 comparisons. Benchmark as a function of unique calibrations, separate from total image count; account for repeated exact calibrations being efficiently deduplicated already.

Fix / acceptance

Use a bounded sorted-X sweep window with indexed Y ranges (for 2D), or suitable spatial hash / interval tree to enumerate candidate edges efficiently; union-find preserves the existing deliberate single-linkage semantics and stable group ordering. Preserve the relative tolerance (not absolute binning), mixed units, unknown values, and deliberate non-transitivity. Consider a Numba njit kernel only for remaining numeric candidate-pair comparisons after indexing, comparing warm/cold cost and validating deterministic output; do not Numba-wrap the existing quadratic algorithm as the primary fix.