Conditional Indexing Lower Bounds and Normalization Boundaries for Elastic Subsequence Matching

Abstract

We study static indexes for exact subsequence matching over all equal-length windows of a time series. Under deterministic SETH, for every fixed $\beta\ge1$ and $\delta\in(0,1)$, we exclude $O(N^\beta)$ preprocessing together with $O(N^{1-\delta})$ worst-case query time on domains containing the reduction's polylogarithmic query lengths. The bounded-error counterpart assumes randomized SETH. The results cover specified warping, bottleneck, edit, subsequence, local-alignment, and complexity-adjusted scores. Their reductions share a data-independent query interface but require different arguments for all-window soundness. We give complete representative proofs for the distinct mechanisms and state the changes needed by related scores. For soft-DTW, integer scaling yields an exact Boolean-predicate reduction in Word-RAM; a model with exact transcendental primitives requires a separate assumption. For independent window-wise Z-normalization, balanced coordinate gadgets and shifted-window moment bounds yield exact lower bounds for squared-cost DTW and discrete Fr\'echet distance. We give finite-word comparisons and a specified length-dependent rounding rule preserving these gaps. Raw and normalized discrete Fr\'echet constructions also exclude feasible-solution approximation within any fixed factor below two. Finally, we prove conditional signal-attenuation bounds for normalized anchor constructions and a fast index under the all-window common-mean promise.