Linear interpolation changes the nearest neighbor in up to one-third of incomplete sensor queries

A missing value can turn nearest-neighbor retrieval into an imputation benchmark without anyone saying so. In a new six-dataset study, linear interpolation returned a different top-1 neighbor from the complete true query on 32.8% of METR-LA, 24.9% of PEMS-BAY and 20.7% of PeMSD7-M tests under L1 distance. At the paper’s full window band, those rates fell to 22.6%, 17.7% and 14.8%. The result is not that interpolation is always bad; it is that the retrieved answer can belong as much to the fill rule as to the observed data. Source

What the benchmark actually tested

The authors used three public traffic-speed collections totaling 760 sensors and 93,165 sensor-days. They split each sensor chronologically: the first 80% of days supplied history and the final 20% supplied test queries. To retain a known complete answer, they took complete test days and transplanted real METR-LA gap patterns onto them, evaluating 1,000 queries per dataset at four band widths. The typical same-sensor galleries contained 82, 144 and 35 historical days, respectively. Source

That protocol matters. These are test-set change rates against the known complete query, not accuracy against a semantic label and not a claim about every missing-data process. The uncertainty box also uses a history-based range for each missing value; the authors explicitly describe that range as a convention rather than a physical limit. The true query fell inside it for 100%, 99.7% and 100% of the evaluated traffic queries. Source

Certification instead of another guess

ExactCert asks whether one candidate remains closer than another for every completion inside the box. Among queries that it certified strictly, the top-1 change rate after linear interpolation was 0% on every dataset and every tested band width. That is a conditional guarantee, not a new imputation score: uncertified queries may still retrieve correctly, while certified answers are stable only if the true values lie inside the chosen box. Source

The computational result is also bounded. On network-scale galleries of 16,455, 46,719 and 7,980 complete history days, ExactCert took median 0.31, 0.71 and 0.15 seconds per query at the full band. On ten queries also run with the dynamic program alone, it produced identical answers while running 82×, 100× and 110× faster. All tests were single-threaded in NumPy and Numba on one Mac M5 laptop. Source

The practical reading

The paper does not prove that its window-minimum distance beats L1 or dynamic time warping. In fact, moving from L1 to the full band increased next-hour forecast error by 11.8%, 23.2% and 6.8% on the three traffic datasets, even as retrieval became less sensitive to imputation. The useful contribution is narrower: when missing values can alter a similarity lookup, report both the nominal result and whether that result is stable across admissible completions. Source

The remaining limits are substantial: the gallery must be complete, time positions are fixed, broad uncertainty boxes reduce certification coverage, and evidence beyond traffic data is limited to three classification benchmarks. ExactCert is therefore a promising audit layer—not a universal replacement for imputation or retrieval evaluation. Source