PaperlayerView exact revision on arXiv

Source-linked AI summary

MomentQuant: an even more minimalist interval method with linear time complexity for time series classification

Johann Faouzi

arXiv:2609.05136v1cs.LG

TL;DR

Time series classification seeks accurate predictions without prohibitive computational cost, and Quant offers a fast interval-based baseline. This paper optimizes Quant’s exact implementation and introduces MomentQuant, which estimates quantiles from moments using the Cornish-Fisher expansion. MomentQuant accelerates feature extraction with a small average accuracy cost, while the approximation has validity limitations for some non-normal intervals.

  • Problem

    Time series classification methods face a persistent trade-off between predictive accuracy and computational cost, while Quant’s reference implementation is inefficient at both short- and long-series extremes.

  • Method

    The paper reimplements Quant with cost-guided loop ordering and introduces MomentQuant, which estimates interval quantiles from mean, variance, skewness, and excess kurtosis using the Cornish-Fisher expansion.

  • Results

    MomentQuant provides roughly 1.7× faster feature extraction than the exact mode, with under half a percentage point lower average accuracy and wins on over a third of tested data sets.

  • Takeaways & Limitations

    MomentQuant offers a faster long-series feature-extraction alternative, while its practical end-to-end advantage is most apparent when inference-only cost is isolated.

  • Takeaways & Limitations

    The Cornish-Fisher approximation may be non-monotonic outside its validity domain, particularly for highly non-normal intervals and small samples.

Abstract

from arXiv · show

Time series data is very common in many real-world applications and in numerous domains, with increasing interest for automated information extraction using machine learning. One of these subfields is time series classification, which consists in assigning a label to each new, unseen time series. Many algorithms have been developed over the past decades, with the trade-off between predictive performance and computational cost being consistently discussed. Quant, an interval-based algorithm extracting quantiles from recursive, fixed, dyadic intervals, was shown to achieve high accuracy, while being very fast. We propose two changes to make this algorithm even faster. The first one is a better optimized implementation of the exact same algorithm. The second one is to derive approximate quantiles, using the Cornish-Fisher expansion, instead of exact quantiles. This change removes the necessity to sort the time series, leading to a smaller computational complexity. We call this novel algorithm MomentQuant. We provide evidence that our implementation of Quant is faster than the original one, and that MomentQuant is even faster than our implementation of Quant, at the cost of a tiny decrease in predictive performance. These improvements are especially relevant for real-life applications, where inference is performed much more often than training.

1 Introduction

Time series classification faces a persistent trade-off between predictive accuracy and computational cost. This paper improves Quant for short and long series, introducing a moment-based approximate mode that replaces sorting with linear-time estimation.

  • Motivation: Quant combines interval quantiles across four representations and achieves accuracy close to expensive heterogeneous ensembles with under fifteen minutes of total processing on 142 UCR data sets.The representations are the raw series, smoothed first-order difference, second-order difference, and discrete Fourier magnitude.
  • Motivation: The reference implementation is poorly matched to both short and long series because fixed dispatch overhead dominates short-series processing while sorting costs grow for long series.Exact quantile computation from l values requires O(l · log(l)) sorting.
  • Contributions: The paper reimplements Quant exactly, selects loop orderings using a theoretical cost model, and introduces a Cornish-Fisher mode that estimates quantiles from four moments in one O(l) pass.The approximate mode trades O(l · log(l)) sorting for O(l) moment-based computation.
  • Contributions: The paper develops a precise cost model for Quant’s exact and approximate modes and analyzes two natural loop orderings.The model supports implementation choices that depend on series length.
  • Contributions: The study evaluates quantile fidelity, accuracy, runtime, loop-order dispatch, and implementation optimizations across the 142 univariate UCR data sets.The contributions include empirical comparisons conditioned on series length and analyses of exact and approximate modes.

2 Background

Time series classification methods span distance-, feature-, shapelet-, dictionary-, convolution-, hybrid-, and interval-based families. Quant belongs to the interval-based family, using multiple representations, fixed dyadic intervals, quantiles, and extremely randomized trees.

  • Classification literature: Time series classification assigns discrete labels to time-ordered measurements, with applications including health monitoring, industrial control, astronomy, and activity recognition.The broader literature contains multiple algorithmic families organized by computational structure.
  • Classification literature: Distance-based methods compare samples using similarities or distances, including nearest neighbors, support vector machines, and dynamic time warping.Dynamic time warping uses dynamic programming to find an alignment through a pairwise cost matrix.
  • Classification literature: Feature-based, shapelet-based, and dictionary-based methods respectively summarize whole series, discriminate with extracted subseries, or convert subseries into symbolic sequences.Examples include Catch22, Shapelet Transform, SAX, and SFA-based models.
  • Classification literature: Convolution-based methods use kernels to extract features, while hybrid methods combine algorithms from different representation families.ROCKET uses random kernels and aggregate features; HIVE-COTE is a heterogeneous ensemble.
  • Interval-based methods: Interval-based pipelines extract statistics from subseries and may apply them across multiple representations before classification.Examples include TSF, STSF, RSTSF, RISE, and CIF, which differ in interval selection, representations, and extracted features.
  • Quant: Quant uses four representations, fixed dyadic and shifted intervals, length-proportional quantile counts, and extremely randomized trees.Its representations are the raw series, smoothed first-order difference, second-order difference, and discrete Fourier magnitudes.

3 Limitations of Quant’s reference implementation

Quant’s reference implementation uses a fixed interval-by-interval PyTorch structure that is simple but poorly matched to both short and long series on a CPU. It therefore incurs fixed dispatch overhead for short intervals and sorting costs that grow superlinearly with long series, motivating two runtime improvements.

  • Fixed computational structure: The reference implementation computes each interval’s quantiles through a separate batched torch.quantile call inside a loop over intervals.The simplified implementation concatenates the resulting interval features after all calls complete.
  • Fixed computational structure: The fixed number of quantile invocations is independent of how much numerical work each interval performs, creating inefficiencies at both series-length extremes.This shared structure is the root cause of the short- and long-series mismatch.
  • Short series: For short series, PyTorch dispatcher overhead dominates because each interval call performs little sorting and interpolation work.The overhead is paid once per interval regardless of interval width.
  • Long series: For long series, sorting the whole series costs O(l · log l), before accounting for sorting the extracted subseries.The reference design therefore pays substantial sorting cost as series length increases.
  • Motivation for improvements: The paper proposes two runtime solutions: optimizing the exact computation’s dispatch and replacing exact quantiles with an approximate alternative.The two solutions target short and long series, respectively, while addressing the implementation’s fixed trade-off structure.

4 Complexity of processing a single series

The paper analyzes Quant’s single-series processing cost by counting intervals, widths, quantiles, sorting, and extraction across regimes. Exact extraction is linear in series length for fixed depth, while sorting is the dominant superlinear term in the saturated regime and the four representations preserve the resulting complexity class.

  • Cost decomposition: The analysis decomposes processing into sorting values in each interval and extracting interpolated, possibly centered quantiles.It first treats the raw series, then generalizes to all four representations.
  • Interval structure: Quant builds a recursively defined collection of intervals whose counts, total widths, and quantile counts determine processing cost.Preliminary theorems establish these quantities before the sort and extraction analyses.
  • Sorting complexity: In the saturated regime, total sorting costs Θ(d · l · log(l)), making it strictly worse than linear in l.The stated sort-cost accounting assigns an interval of size m a cost of m · log2(m).
  • Extraction complexity: Θ(d · l) extraction applies when l ≥2d−1, while Θ(l · log(l)) applies when l < 2d−1.The extraction complexity is independent of the positive quantile-divisor parameter ν.
  • Default regime: With default d = 6 and ν = 4, the saturated regime begins at l ≥32, and the raw representation uses k = 5.These defaults were used in the main experiments referenced by the analysis.
  • Four representations: Summing the four representations preserves the raw representation’s complexity class for sorting, extraction, and total processing.The closed-form simplifications for the additional representations require divisibility assumptions that generally fail.

5 Making Quant faster for short series

This section models Quant’s two loop orderings and uses hardware-specific costs to decide when interval-outer or series-outer processing is faster. The resulting crossover rule explains why series-outer is favored for small data sets, while interval-outer can become advantageous as the number of series grows.

  • Cost model: Quant’s sequential processing can place either the interval loop or the series loop outside, and the preferred ordering depends on series length and sample size.The analysis derives costs for interval-outer version (I) and series-outer version (S), including implementation-specific dispatch overheads.
  • Cost model: The total cost is affine in the number of series, separating shared setup costs from per-series marginal costs.Interval-outer amortizes per-interval dispatch overhead across series, whereas series-outer pays a call-dispatch cost for each series.
  • Crossover rule: When series-outer has the higher marginal cost, it is faster below the crossover sample size n*, while interval-outer is faster above it.The crossover depends on the interval-outer setup cost and the difference between the two marginal costs.
  • Crossover rule: If the series-outer marginal cost is no greater than the interval-outer marginal cost, series-outer is at least as fast for every sample size.This condition is expressed as BS(l, d, ν) ≤ BI(l, d, ν).
  • Practical dispatch: The interval-outer strategy becomes worthwhile only after a threshold that grows with the number of non-trivial intervals, whereas series-outer is never worse for sufficiently small data sets.Because the number of non-trivial intervals grows with series length, the threshold generally increases with l.
  • Practical dispatch: The practical four-representation dispatch rule uses pooled measured runtimes rather than composing representation-specific crossover formulas.The theoretical raw-representation crossover serves as an independent cross-check of the heuristic, whose overhead is fitted per mode, depth, and divisor.

6 Making an approximate version of Quant for long series using moment-based quantiles

The paper introduces an approximate Quant mode for long series that replaces sorting-based exact quantiles with estimates from interval moments. This targets the superlinear sorting cost while leaving approximation quality to empirical evaluation.

  • Approximate mode: MomentQuant replaces each interval’s exact order statistics with quantile estimates from the first four moments using the Cornish-Fisher expansion.Moments are computed in a single linear pass, eliminating sorting from the approximate procedure.
  • Motivation: The approximate mode is intended for long series, where the exact method’s extra log(l) factor is most costly.Whether its approximation error is acceptable is evaluated empirically rather than established by the complexity analysis.

6.1 Background: moment-based quantile approximation

The approximation summarizes each interval with online moments and applies the Cornish-Fisher expansion to estimate interior quantiles. Boundary probabilities use exact extrema, while validity and estimation errors impose important caveats.

  • Moment computation: The Welford-Pebay online update computes the count, mean, and second through fourth central moments in one pass with constant work per observation.The resulting moments support calculation of variance, skewness, and excess kurtosis without sorting.
  • Cornish-Fisher approximation: Cornish-Fisher adjusts the standard-normal quantile using estimates of mean, variance, skewness, and excess kurtosis.For a fixed interval, evaluating an approximated quantile requires a fixed number of arithmetic operations independent of interval size.
  • Boundary handling: The expansion is undefined at q = 0 and q = 1, so the algorithm uses the interval’s exact minimum and maximum at those positions.These extrema are already available from the same linear pass used to compute the moments.
  • Approximation limits: The fourth-moment expansion inherits truncation-error behavior from Edgeworth theory, so its accuracy is not exact.The cited theory characterizes truncation error according to the number of cumulant terms retained.
  • Approximation limits: The approximate quantile is not guaranteed to increase monotonically for all skewness and excess-kurtosis combinations.The study does not check the expansion’s validity domain per interval and instead treats resulting error, including non-monotonicity, empirically.

6.2 Complexity of processing a single series

For a single series, moment computation and Cornish-Fisher extraction have linear-in-series-length costs in the saturated regime and l log(l) costs in the unsaturated regime. Across four representations, the approximate method removes one log(l) factor relative to exact processing.

  • Cost decomposition: The approximate algorithm preserves Quant’s interval structure and quantile positions, changing only how each interval’s contribution is computed.Exact sorting is replaced by a linear moment pass followed by Cornish-Fisher extraction.
  • Moment computation: Moment computation costs Θ(d · l) in the saturated regime and Θ(l · log(l)) in the unsaturated regime.The regime boundary is l ≥ 2^(d−1) for saturation.
  • Quantile extraction: Cornish-Fisher extraction has the same Θ(d · l) saturated and Θ(l · log(l)) unsaturated complexity, independently of the quantile divisor ν.The extraction analysis charges constant work per quantile and per interval-moment conversion.
  • Total processing: The approximate processing cost is Θ(d · l) in the saturated regime and Θ(l · log(l)) in the unsaturated regime.Total cost is the sum of moment computation and extraction costs.
  • Asymptotic speedup: Relative to exact processing, the moment-based method removes exactly one factor of log(l) in both regimes.The speedup grows without bound with l, while its absolute benefit is smaller for short series.
  • Four representations: Summing the costs across Quant’s four representations preserves the same complexity classes and the same single-factor log(l) reduction.The four representations are processed independently and sequentially, but their combined complexity class matches the raw-representation analysis.

6.3 Outer loop over the intervals

The approximate algorithm’s interval-outer implementation processes all series together for each interval and is modeled as setup plus per-series marginal cost.

  • The interval-outer implementation uses a NumPy-vectorized call per interval, processing all n series at once for each representation.
  • Its total cost is decomposed into an implementation-specific setup term and a marginal term proportional to n.The decomposition is applied separately across the four representations.
  • Moment computation covers every interval, whereas only Cornish-Fisher extraction excludes trivial intervals.
  • The interval-outer model includes a hardware-specific per-interval overhead for the Python loop and vectorized extraction-call dispatch.

6.4 Outer loop over the series

The series-outer implementation invokes one compiled kernel per representation and processes each series internally, yielding no amortizable setup term but exposing length-dependent dispatch behavior.

  • The series-outer implementation uses a compiled call per representation, processing all series and intervals internally.
  • The model includes a hardware-specific per-series, per-representation dispatch overhead that is not assumed independent of series length or depth.
  • Its total cost is exactly proportional to n, with no analogue of the interval-outer implementation’s n-independent setup term.
  • Measured runtimes show that the residual dispatch term is not well represented by a single constant and absorbs some unmodeled moment or extraction cost.

6.5 Comparing both approaches

The preferred approximate implementation depends on the relative marginal costs and, when necessary, a crossover sample size; these relationships are resolved empirically for realistic settings.

  • If the series-outer marginal cost is no greater than the interval-outer marginal cost, series-outer processing is faster for every n ≥1.
  • When series-outer marginal cost is larger, a crossover sample size determines which implementation is faster below or above that threshold.
  • The preferred implementation depends on the sign of the marginal-cost difference, which the paper treats as an empirical question.
  • The authors estimate implementation constants empirically and use the cost model to choose between exact versus approximate algorithms and outer-loop variants.

7 Experimental setup

The experiments compare exact and approximate MomentQuant variants with Quant baselines on 142 UCR classification datasets, measuring runtime and predictive performance under standardized settings.

  • Data sets: The evaluation uses 142 univariate UCR time series classification datasets and 30 resamples per dataset.
  • Algorithms: Eight algorithms compare MomentQuant’s exact and approximate modes, three outer-loop choices, and two Quant baselines.
  • Algorithms: Automatic modes select the faster outer-loop implementation without changing transformation outputs or classification performance.
  • Algorithms: Extremely randomized trees use Quant’s classifier and default hyperparameters, with depth d = 6 and quantile divisor ν = 4.
  • Metrics and analysis: Accuracy is the primary metric, supplemented by balanced accuracy, AUROC, NLL, and F1-score.
  • Metrics and analysis: Paired t-tests and Wilcoxon tests compare algorithms across datasets at significance level α = 0.05.

8 Results

The results show that implementation choices substantially affect exact-quantile runtime, while MomentQuant’s approximate mode accelerates transformation with only a small classification-performance decrease. Automatic dispatch generally tracks the fastest manual variant, but theoretical and calibrated crossover thresholds differ substantially.

  • 8.1 The impact of the implementation choice: Around 2× faster single-threaded runtime than PyTorch was achieved by the NumPy implementation for theoretically identical exact-quantile computations.The implementation was also much faster than NumPy’s quantile function.
  • 8.2 Cost-model validation: Mean cost-model error stayed within a few percent of zero for four of five estimators on held-out series-length and sample-count combinations.MomentQuant("exact", "samples") had mean error −1.5%, standard deviation 1.8%, and no error above 5.4%.
  • 8.2 Dispatch crossover: At every tested series length, the calibrated dispatch threshold n_heuristic was much larger than the theorem-derived crossover n*.The gap ranged from 1161× for exact mode at l = 16 to roughly 4–6× at l = 8192, reflecting pooled overhead without l-dependence.
  • 8.2.3 Dispatch crossover: MomentQuant("approx") transformed all 142 UCR data sets in roughly 38–39s, about 1.7–1.8× faster than the best exact-mode variant.Its asymptotic complexity is Θ(d · l), compared with Θ(d · l · log(l)) for exact mode in the saturated regime.
  • 8.3 Transformation runtimes: Automatic variants closely tracked the fastest manual variants without being the worst choice, although exact automatic mode was within 7% of the best single-threaded choice.At 8 threads, exact automatic mode essentially matched the best choice, while approximate automatic mode was within 1% single-threaded and matched it multithreaded.
  • 8.4 Classification performance: MomentQuant("approx") had nearly the same performance as QuantFloat64 and was less than 0.01 behind MomentQuant("exact") on each of five metrics.Its mean accuracy was 0.8505 versus 0.8551 for both exact mode and QuantFloat64, with significant differences (p = 0.002).
  • 8.4.2 End-to-end and inference-only runtimes: Total transformation runtimes were 401s, 436s, and 474s single-threaded for approximate mode, exact mode, and QuantFloat64, respectively.With 8 threads, the corresponding runtimes were 156s, 161s, and 200s; most total runtime came from classifier training.

9 One final experiment

The final experiment evaluates a proposed global-sort optimization and implementation-level explanations for runtime differences across NumPy and PyTorch. The optimization is slower in NumPy but can improve PyTorch performance, while indexed sorting explains much of the remaining gap.

  • Scope: The experiment focuses on optimizing Quant’s transformation even though most runtime is dominated by the classification algorithm rather than transformation.The proposed optimization was therefore investigated despite mixed results across libraries.
  • Optimization: The proposed optimization globally sorts each series once and reuses the resulting order to obtain values for every interval.This replaces separate sorting of each interval, whose saturated-regime cost is Θ(d · l · log(l)).
  • Runtime comparison: NumPy runs the proposed optimization roughly 2.4–2.7× slower, whereas PyTorch is 6–9% faster single-threaded for l ≥16384.With eight PyTorch threads, the optimization is faster at every tested length, from roughly 27% faster at l = 1024 to roughly 2% faster at l = 32768.
  • Implementation mechanism: The optimization requires an indexed global sort because interval assignment needs each sorted value’s original position.This makes the cost of obtaining the permutation central to whether the optimization helps in a given library.
  • Implementation mechanism: PyTorch’s sorting gap is not explained by more comparisons or swaps: keyvalue sorting stays near direct sorting, while indirect sorting is slower.The keyvalue/direct ratio declines to about 1.0–1.1× for l ≥4096, whereas indirect/direct remains roughly 1.25–1.29× across much of the tested range.

10 Conclusion

The paper improves Quant at both ends of the series-length spectrum: optimized loop ordering helps short series, while MomentQuant replaces exact sorting with Cornish-Fisher approximation for long series. Across the UCR archive, this yields faster feature extraction with a small accuracy cost, especially when extraction rather than classifier fitting is the bottleneck.

  • Short-series optimization: For short series, choosing between two loop orderings using a theoretical cost model removes avoidable dispatch overhead.The calibrated heuristic selects the faster ordering for each mode, although it does not always succeed.
  • MomentQuant: For long series, MomentQuant replaces exact per-interval sorting with Cornish-Fisher quantile approximation, changing the sorting cost from O(l · log(l)) to O(l).The approximation targets the same quantiles without sorting each interval.
  • Complexity analysis: The paper derives complete computational-complexity analyses for Quant and MomentQuant and shows that runtime comparisons depend substantially on library and function choices.These implementation effects can matter independently of theoretical complexity.
  • Empirical results: At full UCR scale, MomentQuant extracts features roughly 1.7× faster than exact mode, with an average accuracy cost under half a percentage point.It still outperforms exact mode on over a third of the tested data sets.
  • Practical relevance: The runtime advantage largely disappears when downstream classifier fitting dominates end-to-end cost, but re-emerges for inference-only workloads and sufficiently long series.The series-length pattern is real but non-monotonic rather than uniformly widening.
  • Scope and open questions: The study is restricted to univariate series, and multivariate extension would require recalibrating dispatch constants or developing a new joint-channel cost model.Independent per-channel processing would preserve the complexity class in series length but alter overheads and crossover behavior.

11 Declarations

The authors disclose the study’s data, software, generative-AI use, funding status, and conflicts of interest. The data and supporting source code are publicly available.

  • Data and code: The study uses publicly available data sets from the UCR Time Series Archive.The authors also acknowledge contributors to the archive.
  • Data and code: The source code supporting the study is publicly available in a GitHub repository.
  • AI disclosure: Generative artificial intelligence was used for code generation and result analysis, with the authors accepting responsibility for the manuscript and repository materials.
  • Funding and conflicts: The authors report no funding, relevant interests, or conflicts of interest.

Appendix A Proofs

The appendix supplies proofs for the paper’s interval-count, cost, representation-length, and implementation analyses. It establishes exact interval and asymptotic results while distinguishing simplifying divisibility assumptions from arbitrary series lengths.

  • Appendix scope: The appendix contains proofs of every theorem and lemma stated in Sections 4, 5, and 6.
  • Interval construction: Quant builds base and shifted intervals across dyadic depth levels, with exact interval counts determined by the series length and configured depth.At level r, there are 2^r base intervals and, for r>0, 2^r−1 shifted intervals.
  • Assumptions: Some closed-form theorems assume l is exactly divisible by powers of two, whereas the exact extraction results hold for arbitrary l.The divisibility assumption generally fails for the transformed representations.
  • Interval construction: The proofs account for unequal interval widths when l is not divisible by 2^r and for the conditions governing shifted intervals at the deepest level.These conditions include the threshold l ≥ 1.5 · 2^k.
  • Cost analysis: The appendix derives total sort and extraction costs by summing contributions across interval levels, including width-one intervals that require no sorting or interpolation.Width-one intervals are copied directly, enabling exact small-series cost formulas.
  • Representations: The four Quant representations have lengths l, l−1, l−2, and ⌊l/2⌋+1, respectively, subject to l ≥ 3.These are the raw series, smoothed first difference, second difference, and one-sided real Fourier magnitude spectrum.
  • Approximate-mode complexity: The approximate-mode total cost is Θ(e · l), because its moment and extraction terms have the same asymptotic order.The proof then separates cases according to which term determines the constant.

Appendix B Additional results

Appendix B extends the exact-versus-approximate quantile-correlation visualizations across five additional UCR data sets. Each figure shows correlation distributions by depth, while ItalyPowerDemand lacks a depth-5 panel because its depth cap binds.

  • Correlation distributions: Figures B1–B5 plot Pearson-correlation histograms between exact and approximated moment-based quantiles across depth levels for ECG200, GunPoint, ItalyPowerDemand, Wafer, and Yoga.Each panel title reports the number of genuinely approximated columns and their median correlation.
  • ItalyPowerDemand: ItalyPowerDemand has no depth-5 data because its short series length l = 24 triggers the depth cap before the configured depth of 6.Its populated panels therefore stop at depth 4.
Loading 2609.05136v1…