arXiv preprint ·
Conditional Indexing Lower Bounds and Normalization Boundaries for Elastic Subsequence Matching
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study static indexes for exact subsequence matching over all equal-length windows of a time series. Under deterministic SETH, for every fixed $β\ge1$ and $δ\in(0,1)$, we exclude $O(N^β)$ preprocessing together with $O(N^{1-δ})$ 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échet distance. We give finite-word comparisons and a specified length-dependent rounding rule preserving these gaps. Raw and normalized discrete Fréchet 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Improved classical optimization of fermionic Hamiltonians beyond Gaussian states
Faster Deterministic Approximation for Counting Knapsack
The Matching Number Characterizes the Query Complexity of Edge Counting and Degree Moment Estimation
Subset Sum and Integer Programming Feasibility Test in Near-Optimal Time
Random Fourier Features in Near-Linear Time
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.