PaperlayerView exact revision on arXiv

Source-linked AI summary

Conditional Indexing Lower Bounds and Normalization Boundaries for Elastic Subsequence Matching

Zemin Chao, Zitong Li, Xiangyu Gao, Hongzhi Wang

arXiv:2610.12938v1cs.DS

TL;DR

Static exact subsequence matching asks whether any equal-length window of a stored time series meets a query threshold, but the indexing limits for this all-window setting are the question. The paper reduces OnlineOV to specified elastic scores, with separate soundness arguments for unintended windows and alignments. Under the stated SETH assumptions, it excludes polynomial preprocessing paired with polynomially sublinear worst-case query time on covered hard-length domains.

  • Problem

    The paper asks whether preprocessing a target time series can guarantee a polynomial saving over linear query time for exact matching against every legal equal-length window.

    Source: §1 · p. 1

  • Method

    The reductions encode stored vectors in the target and online vectors in queries, using score-specific arguments to ensure that no unintended physical window or alignment is accepted.

    Source: §1 · p. 1

  • Results

    For every fixed β ≥1 and δ ∈(0, 1), deterministic SETH excludes O(N^β) preprocessing with O(N^{1−δ}) worst-case query time on domains covering the reduction’s hard lengths.

    Source: §1.1 · p. 1

  • Takeaways & Limitations

    The lower bounds cover specified elastic scores and independently normalized cases, while normalized DFD also has a feasible-solution approximation barrier below factor two.

    Source: §1.1 · pp. 1–2

    The exclusions apply only to fixed, exactly implementable parameter slices and domains covering the hard lengths, and do not establish an unconditional Ω(N) bound or a result for constant m.

    Source: §1.1 · p. 2

Abstract

from arXiv · show

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.

1 Introduction

The paper studies static indexes for exact subsequence matching over every equal-length window, where preprocessing depends only on the target and queries arrive online. It establishes conditional indexing lower bounds for specified scores, including independently normalized cases, while distinguishing their assumptions and all-window soundness arguments.

1.1 Main results

  • Reductions encode stored vectors in the target and online vectors in queries, then use score-specific arguments to rule out accepted physical windows and unintended alignments.The paper also treats soft-DTW by integer scaling for an exact Word-RAM predicate reduction; exact transcendental primitives require a separate assumption.Source: §1 · p. 1, §1.1 · p. 2
  • For each fixed β ≥1 and δ ∈(0, 1), deterministic SETH excludes O(N^β) preprocessing with O(N^{1−δ}) worst-case query time on domains covering the reduction’s hard lengths.Under randomized SETH, the exclusion also holds for any fixed per-input two-sided error p < 1/2.Source: §1.1 · p. 1
  • Raw and independently normalized DFD constructions exclude feasible-solution approximation within each fixed factor 1 ≤ ρ < 2 under the corresponding deterministic or randomized assumption.The argument uses explicit distance-1 versus distance-2 gaps, up to a common normalization factor.Source: §1.1 · p. 1
  • The lower bounds concern fixed, exactly implementable parameter slices and covered hard-length domains; they do not establish an unconditional Ω(N) bound or hardness for constant m.The shorthand conditional N^{1−o(1)} applies only to a uniform domain covering the hard lengths needed for the exponents in question.Source: §1.1 · p. 2
  • Independent window normalization admits exact lower bounds for squared-cost DTW and DFD using balanced coordinate gadgets and shifted-window moment bounds.The construction also gives finite-word comparisons and a length-dependent dyadic rounding rule that preserves the gap.Source: §1.1 · p. 2

1.2 Related work

  • The all-window, independently normalized setting differs from prior whole-curve or raw subsequence formulations, because discarded prefixes and suffixes can create matches.The paper positions its conditional running-time bounds as distinct from practical search improvements and safe distance bounds.Source: §1.2 · pp. 2, 4

2 Preliminaries

The preliminaries define the static all-window query interface and the computational assumptions used by the reductions. They derive a parameter-sensitive OnlineOV lower bound from SETH, with amplification for randomized indexes and an explicit restriction on the logarithmic dimension coefficient.

2.1 Static subsequence queries

  • Preprocessing stores an index built from S alone; each query supplies Q, a threshold, and any explicit parameters, and tests all N − m + 1 length-m windows.Legal starts include positions inside encoding blocks and across block boundaries.Source: §2.1 · p. 4
  • A query-length domain prescribes which query lengths an index must support, ranging from all lengths to a single size-dependent slice.The equal-length window definition is relative to the current query and does not require m(N) = O(1).Source: §2.1 · p. 4

2.2 Computation and complexity hypotheses

  • The default model is a uniform Word-RAM with w = Θ(log N), where hard inputs use O(1)-word integers or rationals and required primitives take O(1) operations.Soft-DTW’s separately specified extended Real-RAM is outside this default model.Source: §2.2 · p. 4
  • Deterministic SETH and randomized SETH supply the respective assumptions for deterministic and randomized indexing lower bounds.Randomized correctness is measured jointly over preprocessing and query randomness for each fixed target-query input.Source: §2.2 · p. 4

2.3 The OnlineOV lower bound

  • Under deterministic SETH, for fixed b ≥1 and ϵ ∈(0, 1), sufficiently large fixed c rules out OnlineOV indexes on d = ⌈c log2 n⌉ dimensions with preprocessing O(n^b) and query time O(n^{1−ϵ}).The randomized version holds under randomized SETH for each fixed p ∈[0, 1/2), with c0 also depending on p.Source: §2.3 · p. 5
  • The reduction partitions SAT variables between data and query assignments, representing a clause by whether each partial assignment leaves it unsatisfied; orthogonality then corresponds to a satisfying combined assignment.For randomized indexes, independent copies of the entire index permit majority amplification and a union bound over the fixed query collection.Source: §2.3 · p. 5
  • The dimension coefficient c is chosen after the desired preprocessing exponent and query saving, so the result does not establish hardness for every small fixed c.The source explains that direct lookup of all 2^d Boolean queries can fit within an appropriate polynomial preprocessing budget at small c.Source: §2.3 · p. 5

3 Reduction framework

The framework separates query-independent target construction from query-and-threshold generation, requiring correctness over every physical window and legality in the declared model to transfer reductions to static-indexing lower bounds. It also characterizes when feasible returned costs can distinguish Yes and No promise regions within the query budget, including the limits of logarithmic-gap exclusions for approximation ratios.

3.1 The common encoding

  • Anchored block encodings make canonical-window costs encode orthogonality, while shifted windows require separate soundness arguments because they can combine parts of adjacent vectors.The common anchors encode coordinate positions and bounded data values encode orthogonality; buffered constructions may instead show that an accepted window certifies an orthogonal core.Source: §3.1 · p. 6

3.2 Transfer to static indexing

  • Under the stated SETH assumption, the transfer excludes O(N^β) preprocessing with O(N^(1−δ)) query time, provided the index supports the reduction’s hard query lengths.The randomized transfer preserves any fixed joint per-input error bound p < 1/2. The result does not establish hardness for constant-length queries or an unconditional Ω(N) bound.Source: §3.2 · pp. 6–7

3.3 Block encodings

  • A valid reduction certificate must prove canonical-window completeness and no-instance rejection over every physical offset and legal witness, not merely rely on anchor order.A shifted buffered window may be accepted in a Yes instance if it certifies an orthogonal core; an order obstruction alone does not bound numerical cost.Source: §3.3 · p. 7

3.4 Alignment bounds

  • Four sufficient exclusion tools are dominance, charging, core projection, and an initial barrier; their validity depends on the score’s actual recurrence and witness operations.Dominance applies to sum and maximum aggregation, but averaging and soft-min need not satisfy it; local restarts can bypass an initial barrier.Source: §3.4 · p. 8

3.5 Arithmetic and soft minima

  • Soft-min gaps must exceed γ ln M(N), while finite-word legality also requires bounding intermediate rational values and implementing each required primitive in the declared model.An exact Boolean-predicate reduction need not evaluate the score; excluding a model with exact transcendental primitives requires an OnlineOV assumption in that stronger model.Source: §3.5 · pp. 8–9

3.6 Decision and approximation

  • Decision hardness transfers to negated maximization scores, fixed-parameter slices, positive-gap predicates, and sufficiently informative outputs; approximation hardness requires an additional gap argument.Rubinstein’s independent ANN theorem gives a SETH-based result for several distances [43], but transferring it to another score needs an additional reduction.Source: §3.6 · p. 9
  • A comparator at g(N)τq separates Yes costs bD ≤ ρ(N)τq from No costs bD ≥ Dsub and answers OnlineOV within the transfer’s query budget.The transfer preserves unchanged error semantics for algorithms returning a feasible cost.Source: §3.6 · p. 9
  • A Yes threshold Θ(log N) and constant additive No gap κ yield a ratio 1 + Θ(1/log N), excluding suitable high-accuracy ratios but not arbitrary fixed-constant ratios.Choosing a fixed representable η makes the No inequality strict.Source: §3.6 · p. 9

4 DTW and discrete Fréchet

Alternating-anchor blocks yield conditional lower bounds for exact equal-length-window DTW and DFD by making unintended alignments incur costly anchor–data matches. The proof covers every physical window and every legal path, including shifted windows.

4 DTW and discrete Fréchet

  • Exact equal-length-window DTW and DFD have conditional indexing lower bounds at hard lengths m = 4⌈c log n⌉ + 1.The result applies to fixed bands and unrestricted paths under the respective deterministic and randomized SETH assumptions.Source: §4 · p. 10
  • For DTW, an orthogonal pair attains cost d; non-diagonal canonical and shifted-window paths cost at least d+1, while diagonal No paths cost at least d+2.Thus every window and legal path is accounted for without requiring an optimal No-instance path to be diagonal.Source: §4 · p. 11
  • The DTW construction has N = n(4d + 1), query length m = 4d + 1, and polynomial-magnitude symbols and finite local costs.Every Yes witness is diagonal, so fixed nonnegative bands retain it; restricting paths cannot introduce an accepted No witness.Source: §4 · p. 11
  • For DFD, the all-window optimum is 1 in Yes instances and 2 in No instances, because every non-diagonal canonical or shifted-window path has a cell costing at least 2.A canonical diagonal supplies the No-instance upper bound of 2.Source: §4 · p. 11

X DDFD(X, Q),

The DFD distance gap also excludes feasible-solution approximation below two, and the lower bounds extend to specified positive-weight DTW and fixed path restrictions. These extensions require explicit verification guarantees and restrictions on the weights or permitted paths.

X DDFD(X, Q),

  • For every fixed 1 ≤ ρ < 2, the lower bounds exclude an index returning a valid window or feasible coupling with a DFD approximation guarantee.The randomized guarantee must hold jointly with feasibility with probability at least 1 − p for each fixed input; verification adds only polynomial-in-m query work.Source: X DDFD(X, Q) · p. 11
  • At ρ = 2, this construction no longer separates the cases, since a canonical diagonal is already a feasible 2-approximation.This is a limitation of the constructed instances, not a general statement about 2-approximate indexes.Source: X DDFD(X, Q) · p. 11
  • Positive-weight cWDTW inherits the lower bounds when weights are fixed, have ω(0) > 0 and a fixed positive lower bound, and meet exact constant-word arithmetic requirements.The extension also holds for fixed Itakura-style path rules whose paths are subsets of standard monotone paths and include the complete diagonal at sufficiently large hard lengths.Source: X DDFD(X, Q) · p. 11
  • The result does not automatically cover length-dependent modified logistic weights or alternative path constraints without checking the stated weight and path-subset premises.The original WDTW proposal’s weights need not meet the uniform positive lower bound or exact Word-RAM evaluation condition.Source: X DDFD(X, Q) · p. 11

5 Edit distances

ERP, TWED, and MSM require distinct locking arguments to rule out unintended alignments and shifted windows. Together, their all-window certificates yield conditional indexing lower bounds under deterministic or randomized SETH.

5.1 ERP

  • ERP’s anchor columns force canonical alignments to match same-name anchors, leaving cost d + 2⟨u, v⟩; reversed anchor order makes every shifted window exceed threshold d.This establishes the all-window equivalence for the gap-0 slice.Source: §5.1 · p. 12

5.2 TWED

  • For the stated unit-timestamp TWED slice, a forced first step and costly later departures make canonical chains diagonal, while shifted windows exceed threshold 2d at their first step.The diagonal cost is 2d + 4⟨u, v⟩, separating orthogonal from nonorthogonal pairs.Source: §5.2 · p. 13

5.3 MSM

  • For MSM with λ > 0, its Split/Merge costs force canonical predecessor chains to be diagonal, and shifted windows exceed threshold d at initialization.The canonical cost is d + 2⟨u, v⟩; the argument concerns DP predecessor chains, not arbitrary edit-operation scripts.Source: §5.3 · p. 13

5.4 Indexing lower bounds

  • For ERP, deterministic SETH rules out O(N^β) preprocessing with O(N^(1−δ)) worst-case queries for the stated gap-0 slice; randomized SETH gives the same bound for fixed error p < 1/2.The bound applies when the query-length domain covers the corresponding hard lengths.Source: §5.4 · p. 13

6 Derivative DTW and CID

The section gives an all-physical-window reduction for endpoint-trimmed derivative DTW and a separate raw CID reduction. Both yield conditional indexing lower bounds, with CID comparisons implementable using finite-word arithmetic.

6.1 Endpoint-trimmed derivative DTW

  • For cDDTW, some length-M window scores at most d exactly when an orthogonal pair exists, yielding conditional indexing bounds for hard lengths M = 4d + 3.Every shifted physical window retains an extreme derivative that forces a local cost above d; the result applies to the specified endpoint-to-endpoint, absolute-local-cost variant.Source: §6.1 · p. 14

6.2 Raw CID

  • For raw squared CID, an orthogonal pair gives a canonical-window score below d + 1, while every window in a No instance scores at least d + 4.The result concerns the raw formula without independent window-wise Z-normalization and excludes zero-complexity inputs without a stated convention.Source: §6.2 · p. 15
  • Raw squared CID threshold comparisons use integer sums and cross multiplication, avoiding a square-root primitive and supporting exact finite-word comparisons.The construction’s coordinates, sums, and cross products have O(log d) bits.Source: §6.2 · p. 15

7 Discrete alignment scores

The section gives all-window reductions for LCSS, EDR, Swale, and a specified Smith–Waterman-type score. Distinct alignment mechanisms require separate soundness arguments, and the resulting conditional indexing bounds apply to specified score slices and parameter settings.

7 Discrete alignment scores

  • The constructions target specified score variants rather than unrestricted alignment settings, and their legality arguments differ across edit operations, skips, warping, and local restarts.For example, the LCSS proof does not establish hardness with an independently fixed finite temporal band.Source: §7 · p. 16, §7.1 · p. 16

7.1 LCSS

  • LCSS uses ordered phase alphabets and repeated anchors to attain τL − ⟨u, v⟩ on canonical blocks and bound every shifted window by τL − 1.Thus an orthogonal stored vector exists exactly when some length-m window has LCSS at least τL; the construction has m = O(d^2) and an O(d)-size alphabet.Source: §7.1 · p. 16

7.2 EDR

  • EDR projects alignments onto complete cores without increasing cost, while partial-core windows have distance at least 2d + 1.An orthogonal canonical window costs d, whereas No-instance full-core windows cost at least d + 1, yielding the all-window threshold certificate.Source: §7.2 · p. 17

7.3 Swale

  • Swale reuses EDR cores and buffers, with a Swale–LCSS identity bounding full-core scores and a separate bound for partial-core windows.An orthogonal canonical window scores 4dr, while every No-instance window scores at most (4d−3)r; other reward/gap ratios, extra mismatch transitions, and time bands are outside this certificate.Source: §7.3 · p. 18

7.4 TS-SW

  • The specified Smith–Waterman-type score uses full-consumption rigidity: reaching mB − 1 requires exactly m diagonal events and no gaps.Canonical orthogonal windows reach τT; every No-instance window is at most τT − 2/d. The positive gap supports exact rational comparison but gives no fixed positive additive-error or fixed-factor approximation lower bound.Source: §7.4 · pp. 18–19
  • For each fixed β ≥ 1 and δ ∈ (0, 1), deterministic SETH excludes O(N^β) preprocessing with O(N^(1−δ)) worst-case queries for these four score slices.Under randomized SETH, the same holds for fixed per-query two-sided error p < 1/2; query-length domains must cover the generated hard family.Source: §7.4 · p. 19

8 Soft-DTW

The section turns soft-DTW into an exact Boolean decision predicate using integer scaling and a strict Yes/No gap, then derives conditional indexing lower bounds in Word-RAM. A separate extended-Real-RAM conclusion requires its own OnlineOV assumption.

Entropy bound

  • Soft aggregation can shift a minimum witness cost by at most γ ln H; a length-m path family has at most 32^m paths.Scaling witness costs strengthens the sufficient separation condition to s(B − A) > γ ln H.Source: §8 · p. 19

Exact soft-DTW predicates in Word-RAM

  • Integer scaling preserves a strict soft-DTW Yes/No gap, yielding exact Word-RAM indexing exclusions under deterministic SETH and bounded-error exclusions under Randomized SETH.The query-length domain must contain the hard lengths selected after the lower-bound parameters.Source: §8 · pp. 19–20
  • The reduction uses integer inputs and thresholds and never evaluates exp, ln, or the soft score itself.It invokes the hypothetical Word-RAM Boolean predicate once, so the theorem does not supply exact transcendental primitives or an evaluator for Fγ.Source: §8 · p. 20

Extended Real-RAM statement

  • The extended-Real-RAM lower bound follows only under a separately stated OnlineOV hardness assumption for that model.Rejecting that assumption removes this extended-model conclusion, not the Word-RAM Boolean-predicate theorem.Source: §8 · p. 20

Finite-precision scores

  • A uniform score error of at most κ/2 preserves the stated soft-DTW decision gap, but the paper does not certify a particular floating-point implementation.The numerical transfer is conditional on an error guarantee and the complexity assumption for the implementation's machine model.Source: §8 · p. 20

9 Effects of normalization

This section separates normalization’s effects: shared anchor skeletons yield conditional signal-attenuation bounds, while requiring equal means across all windows imposes periodicity and admits a fast index on that promise.

Affine invariance and scope

  • Z-normalization is invariant under a common positive affine transformation, but canonical-block moment agreement does not establish common moments for every sliding window.The perturbation bounds are conditional on the compared sequences and an unchanged path family; TWED and MSM require separate analysis.Source: §9 · pp. 20–22

Common-mean promise

  • When every length-m window has the same mean, the target is periodic and every window repeats one of the first min{m, N − m + 1} windows.The common-mean promise admits O(N^2) preprocessing, O(N) space, and polylogarithmic query time when m and the single-window scoring time are polylogarithmic in N.Source: §9 · p. 21

Conditional attenuation

  • Under shared-skeleton moment-stability and Lipschitz assumptions, the normalized score difference is at most O(L(d)m(d)/A(d)); if it tends to zero, bounded data perturbations alone cannot create a fixed positive gap.For evenly spaced arithmetic anchors with m = Θ(d), A = Θ(dC), and pointwise ℓ(d) = O(1), the signal is at most O(1/C).Source: §9 · p. 21

Signal bounds for normalized scores

  • For shared anchor skeletons, normalized absolute-cost DTW and raw soft-DTW change by O(m/A), while the DFD bottleneck changes by O(1/A).With m = Θ(d) and A = Θ(dC), these bounds become O(1/C) and O(1/(dC)), respectively.Source: §9 · p. 22

10 Normalized DTW and DFD

Independent window-wise normalization requires a construction that controls both canonical-block moments and shifted windows. The section supplies exact lower bounds for squared-cost DTW and discrete Fréchet distance using balanced gadgets, finite-word comparisons, and a specified rounding rule.

10.1 Balanced encoding

  • Balanced gadgets give canonical blocks and queries common moments, while explicit bounds control shifted-window moment changes and keep their first-cell costs above canonical candidates.This is a squared-local-loss DTW construction; it does not substitute squared loss for the paper's absolute loss elsewhere.Source: §10 · p. 22, §10.1 · p. 23
  • For every canonical block, the exact identities reduce normalized squared DTW and DFD scores to orthogonality, with thresholds 4d/v and 1/v, respectively.The canonical diagonal realizes the score, while the first-cell barrier excludes shifted windows.Source: §10.1 · p. 23

10.2 Exact comparisons and indexing

  • The quadratic-root comparisons use finite-word arithmetic and evaluate one window in O(m^2) Word-RAM operations on the hard family.The construction generates raw integers and rational thresholds without first evaluating normalized coordinates.Source: §10.2 · p. 24
  • The construction establishes exact indexing lower bounds for independently normalized squared-cost DTW and discrete Fréchet distance under the stated SETH assumptions and hard-length coverage.Deterministic and randomized branches use their respective assumptions; the query-length domain must cover the selected hard family.Source: §10.2 · p. 24, Z , DsqDFD · p. 24

Z , DsqDFD

  • For raw and normalized DFD, the construction excludes every fixed feasible approximation factor 1 ≤ ρ < 2 under the corresponding assumption.The verification argument relies on the explicit distance-1 versus distance-2 gap and requires feasibility and the guarantee to hold jointly in the randomized case.Source: Z , DsqDFD · p. 24

10.3 Dyadic rounding

  • Length-dependent dyadic rounding preserves the squared-DTW and squared-DFD gaps when local costs are rounded down at precision R(m), the least power of two at least 8m^5.The stated precision is O(log m) fractional bits; the guarantee does not cover fixed IEEE precision or fresh rounding at each DP update.Source: §10.3 · p. 25

11 Discussion

The discussion consolidates the conditional indexing results, their score-specific proof mechanisms, and the boundary of the normalization claims. It also distinguishes exact hardness from feasible approximation hardness and notes the limits of the verification and arithmetic guarantees.

11 Discussion

  • The indexing exclusions cover specified score and parameter slices, not constant query lengths or every prescribed small coefficient in logarithmic query lengths.The dimension coefficient is selected after the preprocessing and query exponents.Source: §11 · p. 25
  • All-window soundness is score-specific: edit, derivative, subsequence, local-alignment, complexity-adjusted, and soft scores require distinct alignment or cost arguments.The paper gives complete representative proofs and states changes for related scores.Source: §11 · p. 25
  • Independent normalization supports exact lower bounds when canonical moments agree and shifted moments are controlled; a common mean for every adjacent window instead imposes periodicity.The common-mean promise also admits an explicit quadratic-preprocessing, linear-space index.Source: §11 · p. 25
  • Raw and normalized DFD exclude each fixed feasible approximation factor below two, whereas the squared-DTW and TS-SW results establish exact hardness only.The endpoint two is a limit of these constructions, not a general approximation upper bound.Source: §11 · p. 25
  • The arithmetic guarantees concern exact quadratic-field comparisons and the prescribed dyadic rule, not arbitrary IEEE arithmetic or other local losses.The paper also does not claim an end-to-end machine-checked formalization; several proof and resource obligations remain.Source: §11 · p. 26

Related papers

Loading 2610.12938v1…