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

Motivation

• Quant combines empirical quantiles from dyadic intervals across four representations with a tree ensemble, matching leading interval methods and nearing heterogeneous-ensemble accuracy in under fifteen minutes on 142 UCR datasets (Dempster et al., 2024).The representations are the raw series, smoothed first-order difference, second-order difference, and discrete Fourier-transform magnitude.Source: §1 · p. 2
• The paper identifies a gap in Quant’s complexity analysis: interval quantile computation and inference-time transformation costs were not rigorously analyzed, despite their practical importance.The original discussion treats sorting as an upper bound without proving it and emphasizes classifier-training cost instead.Source: §1 · pp. 2–3
• Quant’s batched torch.quantile implementation is inefficient for short series because dispatch overhead dominates and for long series because exact quantiles require O(l · log(l)) sorting.These limitations arise on a single CPU core, the setting used for Quant’s headline runtime figures.Source: §1 · p. 3

Contributions

• The authors reimplement Quant in NumPy and optimize exact computation by selecting between two loop orderings according to a theoretical cost model and series length.This exact mode preserves the original algorithm while targeting the short-series regime.Source: §1 · p. 3
• The new approximate mode estimates interval quantiles from mean, variance, skewness, and excess kurtosis using the Cornish-Fisher expansion, replacing O(l · log(l)) sorting with an O(l) pass.The method incurs a small, empirically largely controllable approximation error.Source: §1 · pp. 3–4
• The paper contributes proven cost models, machine-calibrated dispatch heuristics for both modes, conditional accuracy-runtime experiments across 142 UCR datasets, and single- versus multithreaded analysis of a previously unevaluated optimization.The experiments assess quantile fidelity, classification accuracy, runtime, and series-length effects.Source: §1 · p. 4

2 Background

• The background is organized around time series classification, interval-based algorithms, and an in-depth presentation of Quant, excluding deep learning from coverage.The section refers readers to Middlehurst, Sch¨afer, & Bagnall (2024) for a recent classification review and to Ismail Fawaz, Forestier, Weber, Idoumghar, & Muller (2019) and Mohammadi Foumani et al. (2024) for deep learning.Source: §2 · p. 4

2.1 Time series classification

• Time series classification methods span distance-, feature-, shapelet-, dictionary-, convolution-, and hybrid-based families, each transforming or comparing series before classification.Examples include DTW, Catch22 and TSFresh, shapelet transforms, SAX/SFA dictionaries, ROCKET variants, and HIVE-COTE ensembles.Source: §2.1 · pp. 4–6

2.2 Interval-based methods

• Interval-based methods extract statistics from subseries defined by intervals, concatenate the resulting features, and commonly use tree-based classifiers; TSF, STSF, RSTSF, RISE, CIF, and DrCIF extend this design in different ways.Extensions add supervised interval selection, alternative representations, spectral features, richer feature sets, or additional randomness.Source: §2.2 · p. 7

2.3 Quant

• Quant (Dempster et al., 2024) uses raw, smoothed first-order-difference, second-order-difference, and Fourier representations with base and shifted fixed dyadic intervals to extract quantile features.The number of quantiles scales with interval length through a quantile divisor, and every other quantile is centered by subtracting the interval mean; extremely randomized trees perform classification.Source: §2.3 · pp. 7–8
• Quant handles unequal representation lengths, smoothing and padding, depth limits imposed by series length, unequal interval sizes, endpoint shifts, and special quantile cases including medians and interpolation.For d = 6, series with l < 32 have fewer than six dyadic levels; quantile computation distinguishes subseries of lengths 1, 1 < m ≤ ν, and larger m.Source: §2.3 · pp. 8, 10

Implementation structure

• Quant’s reference implementation2 computes fixed interval endpoints, invokes torch.quantile once per interval across the full batch, and concatenates the resulting features.The interval loop repeatedly applies f_quantile to each sliced interval before concatenation.Source: §3 · pp. 10–11

CPU limitations

• On CPUs, the fixed number of torch.quantile calls creates inefficiencies because invocation count depends on interval count rather than the numerical work per interval.This structure suits batched, hardware-accelerated execution but is not optimal for CPU processing.Source: §3 · pp. 10–11

Short series

• For short series, per-call PyTorch dispatcher overhead dominates because narrow intervals require little sorting and interpolation work.The overhead is paid once for every interval and is largely unavoidable within PyTorch’s general-purpose tensor-operation model.Source: §3 · p. 11

Long series

• For long series, sorting the full series alone costs O(l · log l), excluding the additional sorting required for extracted subseries.Thus, the implementation is dominated by interval-call overhead for short series and total sorting cost for long series, without a trade-off mechanism.Source: §3 · pp. 11–12

Proposed improvements

• The paper proposes two distinct runtime solutions for Quant across short and long series before analyzing the theoretical complexity of processing one time series.These improvements target both failure modes of the fixed implementation structure.Source: §3 · pp. 11–12

4 Complexity of processing a single series

• Quant’s processing of a single representation is decomposed into sorting interval values and extracting interpolated, possibly centered, quantiles from sorted values.For the raw representation, total processing is the sum of total sort cost and total extraction cost.Source: §4 · p. 12, §4.1.4 · p. 15

4.1.1 Preliminary results

• Preliminary theorems characterize Quant’s interval count, total interval width, total quantile count, residual term, and number of width-one intervals.Width-one intervals contribute neither sorting nor interpolation costs, enabling exact extraction-cost expressions rather than small-series approximations.Source: §4.1.1 · pp. 12–13

4.1.2 Total sort

• Under the sort-cost model m · log2(m), total sorting is analyzed first for lengths divisible by 2^k, generalized to arbitrary lengths, and then expressed computationally.The hardware-specific constant c1 converts sort work into seconds.Source: §4.1.2 · p. 14

4.1.3 Total extraction

• Extraction complexity for one raw series is independent of ν and equals Θ(e · l): Θ(d · l) when l ≥2^(d−1), and Θ(l · log(l)) otherwise.The first case is the saturated regime; the second is the unsaturated regime.Source: §4.1.3 · p. 15

4.1.5 Simplified expressions with more assumptions

• With d = 6, ν = 4, and l = 2^b for b ≥5, exact raw-representation cost formulae are obtained for sorting, extraction, and total processing.For b = 5, total processing is 702 · c1 + 80 · c2 + 258 · c3; for b = 6, it is 2046 · c1 + 192 · c2 + 642 · c3.Source: §4.1.5 · pp. 16–17

4.2 Generalizing to the four representations

• Across all four representations, sorting costs Θ(l · e · log(l)), extraction costs Θ(e · l), and total processing costs Θ(l · e · log(l)), unchanged from the raw representation’s complexity classes.Here e = min(d, ⌊log2(l)⌋ + 1), and the result holds for any positive ν.Source: §4.2 · p. 18

5.3 Comparing both approaches

• The comparison assumes hardware-specific empirical constants, while the practical four-representation dispatch rule fits one pooled overhead directly to measured full-call runtimes rather than composing per-representation crossovers.The pooled overhead is fitted for each mode, depth, and divisor configuration and must be refit for differently configured instances.Source: §5 · p. 19, §5.3 · p. 22

5.1 Outer loop over the intervals

• Quant’s interval-outer implementation vectorizes each interval across all series, amortizing per-interval dispatch overhead but paying that setup cost even for small n.Its total cost is affine in n, with an n-independent setup component determined by interval count and hardware-specific overhead.Source: §5 · p. 19, §5.1 · p. 20, §5.2 · p. 21

5.2 Outer loop over the series

• The series-outer implementation processes each series inside one compiled call, eliminating shared setup and making total cost exactly proportional to n.Its dispatch overhead is paid once per series and may depend on series length because data is marshalled across the Python/compiled-code boundary.Source: §5.2 · pp. 20–21

5.3 Comparing both approaches

• For the raw representation, series-outer is at least as fast for every n when its per-series cost is no greater; otherwise it wins below n* and interval-outer above n*.The threshold increases with the number of non-trivial intervals, and series-outer is never worse for sufficiently small data sets.Source: §5.3 · pp. 21–22

Approximate quantiles

• MomentQuant estimates each interval’s quantiles from its first four moments using the Cornish-Fisher expansion, replacing exact order statistics that require sorting.The estimates are computed in a single linear pass with no sorting, trading exactness for asymptotic speed.Source: §6 · p. 22

Motivation

• The approximation targets long series, where the exact method’s total sorting cost is Θ(d · l · log(l)) in the saturated regime and therefore exceeds linear complexity.A single long series is expected to provide enough information for a moment-based approximation to be reasonable; acceptability is evaluated empirically in Sections 7 and 8.Source: §6 · pp. 22–23

Background: moment-based quantile approximation

• The method computes interval moments and extrema in one pass with constant work per observation, avoiding sorting’s m·log2(m) cost.Running m, mean, M2, M3, M4, minimum, and maximum requires fixed arithmetic and two comparisons per element.Source: §6.1 · p. 23
• Cornish-Fisher estimates interior quantiles from mean, variance, skewness, and excess kurtosis at fixed O(1) cost per quantile.The standard-normal quantile and correction terms each require a fixed number of operations independent of interval size.Source: §6.1 · p. 23
• Exact minimum and maximum replace Cornish-Fisher estimates at q = 0 and q = 1 because the expansion is undefined at those boundaries.The extrema are already available from the same linear pass as the moments.Source: §6.1 · p. 24
• Classical error guarantees rely on distributions approaching normality, while non-asymptotic bounds require regularity conditions not assumed for every interval here.The empirical distribution of arbitrary interval values need not satisfy those conditions.Source: §6.1 · p. 24
• Uncorrected Cornish-Fisher estimates may be non-monotonic outside the expansion’s validity domain, especially with small-sample parameter estimation error.The study does not check validity per interval, instead evaluating approximation error empirically and retaining the lower O(1)-per-quantile cost; corrected variants are left for future work.Source: §6.1 · p. 24

6.2 Complexity of processing a single series

• The approximate method changes only interval-cost computation: it uses a linear moment pass and Cornish-Fisher evaluation instead of sorting and interpolation.The interval structure and requested quantile positions remain unchanged, while approximate-algorithm costs use hardware-specific constants ˜c1, ˜c2, and ˜c3.Source: §6.2 · p. 25

6.2.1 Total moment computation cost

• Moment computation alone costs Θ(d · l) in the saturated regime and Θ(l · log(l)) in the unsaturated regime.The saturated regime is l ≥2d−1; the unsaturated regime is l < 2d−1.Source: §6.2.1 · p. 25

6.2.2 Total extraction cost

• Cornish-Fisher extraction has the same two-regime complexity and does not depend on the quantile divisor ν, even when ν varies with l and d.Boundary quantiles use exact interval minima or maxima, but treating their cost through an average per-quantile constant does not change asymptotic complexity.Source: §6.2.2 · p. 26

6.2.3 Total processing cost

• Approximate processing of one raw series has complexity Θ(d · l) when l ≥2d−1 and Θ(l · log(l)) when l < 2d−1.Total processing is decomposed into moment computation plus Cornish-Fisher extraction.Source: §6.2.3 · pp. 26–27

6.2.4 Generalizing to the four representations

• Across all four representations, approximate processing is Θ(d · l) when l ≥2d−1 and Θ(l · log(l)) when l < 2d−1, preserving the raw-series complexity class.The corresponding total moment, extraction, and processing costs are each Θ(e · l), with e = min(d, ⌊log2(l)⌋+1).Source: §6.2.4 · p. 28
• Across all four representations, moment-based quantiles remove exactly one factor of log(l) relative to the exact algorithm, making this the practically relevant comparison.Quant processes all four representations of every series, and summing them preserves the same asymptotic speedup as for the raw representation.Source: §6.2.4 · p. 29

Implementations

• The approximate algorithm offers a NumPy-vectorized interval-outer implementation and a compiled Numba series-outer implementation.Version (I) processes all n series for each interval, whereas version (S) processes all series and intervals within each representation.Source: §6.3 · p. 29

Cost decomposition

• Both implementations process the four representations independently and sequentially.Their total cost is decomposed into an implementation-specific setup cost independent of n and a marginal cost proportional to n.Source: §6.3 · p. 29
• Only the Cornish-Fisher evaluation excludes trivial intervals from the approximate algorithm’s marginal cost.Moment computation and conversion to variance, skewness, and excess kurtosis cover every interval, including trivial ones.Source: §6.3 · p. 29

Interval-outer cost

• Theorem 31 specifies the total wall-clock cost for processing all four representations with the interval-outer implementation for n ≥1, series length l, depth d, and quantile divisor ν.The interval-outer cost includes a hardware-specific per-interval overhead for the Python loop and NumPy call dispatch.Source: §6.3 · pp. 29–30

Outer loop over the series

• The per-series, per-representation dispatch overhead ˜κ(S)(l) is hardware-specific, positive, and not assumed independent of l or d.Theorem 32 establishes the total-cost expression for all four representations while leaving this overhead as a function that may depend on representation length and dimensionality.Source: §6.4 · p. 30
• The total cost of processing all four representations with the series-outer approximate implementation is exactly proportional to n, with no n-independent setup term amortized across series.By contrast, the interval-outer implementation amortizes per-interval dispatch overhead across all n series at once.Source: §6.4 · p. 30
• ˜κ(S)(l) grows by roughly two orders of magnitude across the fitting grid and follows an empirically validated power law with P ≈0.74, whereas the A −B/l form performs poorly under cross-validation.The power law achieves r2 ≈0.99 both in-sample and under cross-validation, compared with ≈0.18 in-sample and ≈0.10 under cross-validation for A −B/l; the exponent has no theoretical derivation here.Source: §6.4 · p. 30
• The residual length dependence may reflect call marshalling across four representations or moment-computation and Cornish-Fisher costs absorbed into ˜κ(S)(l), but neither explanation is confirmed.The authors therefore state Theorem 32 with ˜κ(S)(l) as a general function rather than asserting convergence to a constant.Source: §6.4 · pp. 30–31

Theorem 33

• When eBS(l, d, ν) ≤ eBI(l, d, ν), the series-outer implementation has eT (S)(n, l, d, ν) ≤ eT (I)(n, l, d, ν) for every n ≥1.This condition makes the series-outer implementation no slower for any sample size.Source: §6.5 · p. 31
• When eBS(l, d, ν) > eBI(l, d, ν), the series-outer implementation is faster for n < ˜n∗(l, d, ν), while the interval-outer implementation is faster beyond that crossover.The crossover sample size ˜n∗(l, d, ν) determines which outer-loop implementation has lower total cost.Source: §6.5 · p. 31

Remark 13

• Which implementation is preferable depends empirically on the sign of eBS(l, d, ν) −eBI(l, d, ν), using estimated algorithm-specific constants for realistic l, n, and ν.The paper estimates these constants in Sections 7 and 8 to decide between exact and approximate algorithms and their outer loops.Source: §6.5 · p. 31

7.1 Data sets and algorithms

• Experiments use 142 UCR univariate datasets and the same 30 resamples per dataset as recent studies for comparable speed and performance results.The datasets comprise 112 equal-length, no-missing-value series and 30 datasets from the “bake off redux” study (Middlehurst, Schäfer, & Bagnall, 2024).Source: §7.1 · p. 31
• The eight evaluated algorithms combine exact or approximate quantiles with series-outer, interval-outer, or automatic loops, alongside QuantFloat64 and QuantNumpy.Automatic modes select the faster loop based on dataset size; loop choice affects runtime but not transformation output or classification performance, while MomentQuant and Quant denote approximate and exact variants respectively.Source: §7.1 · p. 32

7.2 Metrics and comparisons

• Accuracy is the primary metric, supplemented by balanced accuracy, AUROC, NLL, and F1, with paired t-tests and Wilcoxon tests at α = 0.05.Extremely randomized trees are used for classification with Quant’s default hyperparameters, d = 6 and ν = 4, and the corresponding tree settings from (Dempster et al., 2024).Source: §7.2 · p. 33, §7.1 · p. 33

7.3 Experiments, implementation and reproducibility

• Experiments run on a 2020 MacBook Air with 16 GB RAM using Python 3.13.14, publicly available source code, and documented package-based implementations for reproducibility.Implementation uses Numba, NumPy, and scikit-learn, while experiment execution and result generation additionally use aeon, joblib, Matplotlib, pandas, SciPy, seaborn, and PyTorch.Source: §7.3 · pp. 33–34

8.1 The impact of the implementation choice

• The optimized NumPy implementation is around 2× faster than PyTorch, while repeated partitioning makes QuantNumpy’s relative runtime increase non-linear as series length grows.The implementations are theoretically identical; PyTorch sorts values and indices, whereas independent partitions incur Θ(m^2) cost when quantile count scales with subseries length.Source: §8.1 · pp. 34–35, Table 1 · p. 35

8.2.1 Estimating the hardware-specific constants

• Runtime-model constants are estimated from single-threaded calibration sweeps, with separate approximate-mode microbenchmarks used to avoid collinearity between moment and Cornish–Fisher costs.The constants apply only to d = 6, ν = 4 and the measurement machine; holdout validation uses unseen combinations of l and n.Source: §8.2.1 · pp. 36–37, §8.2.2 · p. 37

8.2.2 Holdout validation

• Held-out cost-model predictions have mean errors within a few percent of zero for four of five estimators, but QuantFloat64 has a +15.4% average bias.MomentQuant("exact", "samples") is tightest, with mean −1.5%, standard deviation 1.8%, and maximum absolute error 5.4%; other MomentQuant variants reach 37–68% worst-case errors at small l or n.Source: §8.2.2 · p. 37, Table 2 · p. 37

8.2.3 Dispatch crossover

• The calibrated dispatch threshold keeps the series-outer kernel active far longer than the theorem predicts, with disagreement reaching 1161× for exact mode at l = 16.The gap shrinks with l but remains roughly 4–5× for exact and 4–6× for approximate mode at l = 8192, because pooled overhead omits strong l-dependence.Source: §8.2.3 · pp. 38–39, Table 3 · p. 38

8.3 Transformation runtimes

• On all 142 UCR datasets, approximate transformation variants cluster between 38 and 39s, roughly 1.7–1.8× faster than exact intervals and 2.7–3.1× faster than QuantFloat64.Exact intervals take 64.80s, versus 117.97s for exact samples and 105.55s for QuantFloat64; eight-thread speedups are 4.42× for exact samples and 1.64× for approximate samples.Source: §8.3 · pp. 39–40, Table 4 · p. 39
• Approximate and exact automatic variants track the fastest manual kernel without being the worst choice, although interval-outer receives no eight-thread speedup because it is not parallelized.At eight threads, exact automatic runtime is 26.56s versus 26.67s for exact samples; approximate automatic mode matches the best manual variant.Source: §8.3 · pp. 39–40

8.4.1 Classification performance

• MomentQuant("approx") has almost the same performance as QuantFloat64 up to four decimals, except negative log-likelihood, and trails MomentQuant("exact") by less than 0.01 on all five metrics.Its mean accuracy is 0.8505, compared with 0.8551 for both MomentQuant("exact") and QuantFloat64.Source: §8.4.1 · p. 40

8.4.2 End-to-end and inference-only runtimes

• End-to-end runtimes are 401s, 436s, and 474s single-threaded, and 156s, 161s, and 200s multithreaded, for approximate, exact, and QuantFloat64 modes respectively.The corresponding improvements over QuantFloat64 are −15% and −8% single-threaded, and −22% and −19% multithreaded; classifier training remains the dominant cost.Source: §8.4.2 · pp. 42–43, Table 6 · p. 43
• In inference-only runtime, transformation is the largest relative cost for MomentQuant("approx"), MomentQuant("exact"), and QuantFloat64, with its share increasing for longer series.The transformation step is proportional to the number of series, whereas extremely randomized trees have an additional series-length factor during training compared with inference.Source: §8.4.2 · pp. 43, 46, Figure 6 · p. 45

8.4.3 Trade-offs

• In the medium-long bin, MomentQuant("approx") has accuracy difference −0.94 and runtime speedup 0.997×; in the other bins, differences range from −0.58 to −0.08 and speedups from 1.06 to 1.21.These comparisons use end-to-end runtimes, including classification, and show no clean monotonic pattern across series lengths.Source: §8.4.3 · p. 46, Table 7 · p. 47, Figure 7 · p. 47

8.5 Fidelity of the moment-based quantile approximation

• Median correlations between true and approximate quantiles range from 0.598 to 0.988, but every data set has a long negative tail with minima from −0.049 to −0.980.For StarLightCurves, median correlation rises with depth from 0.650 at depth 0 to 0.992 at depth 5; the authors suggest this may reflect less extreme approximated quantiles at deeper levels.Source: §8.5 · pp. 48–49, Table 8 · p. 49
• A Pearson correlation near −1 need not harm classification because sign changes do not affect several linear or tree-based classifiers, including the extremely randomized trees used here.Thus, poor quantile correlation does not necessarily imply poor downstream classification performance.Source: §8.5 · p. 49

Optimization

• Replacing separate interval sorts with one global indexed sort could reduce saturated-regime complexity from Θ(d·l·log(l)) to O(l·log(l)+d·l).The optimization reuses globally sorted positions and assigns them to the fixed intervals at each depth using linear-time bucket grouping.Source: §9 · p. 51

Implementation

• Both NumPy and PyTorch implementations were first verified to produce numerically identical outputs to naive per-interval computation.The benchmark therefore compares runtime without changing the computed transformation.Source: §9 · p. 51

Runtime mechanisms

• Indexed sorting is costly in NumPy because argsort increasingly trails sort beyond l ≈1024–2048, reaching roughly 2× overhead in double precision and 4–4.5× in single precision at l = 32768.Controlled Numba experiments show that indirection adds cache-driven cost, while NumPy’s SIMD fast path further widens the real argsort/sort gap.Source: §9 · pp. 51–54

Runtime results

• The proposed optimization is 2.4–2.7× slower in NumPy, while PyTorch is 6–9% faster single-threaded for l ≥16384 and faster at every tested l with eight threads.In single-threaded PyTorch, it is slower for l ≤2048 and roughly equivalent around l = 4096–8192; with eight threads, its advantage declines from roughly 27% at l = 1024 to roughly 2% at l = 32768.Source: §9 · p. 51, Table 9 · p. 52

Runtime mechanisms

• PyTorch benefits because the proposed method exposes coarser-grained parallel work: at l = 512, eight threads yield about 1.75× speedup versus only about 1.2× for the naive method.The naive implementation performs many short interval sorts, whereas the optimized version uses one global sort and redistribution passes that parallelize more effectively.Source: §9 · p. 54

Conclusion

• MomentQuant replaces O(l · log(l)) per-interval sorting with O(l) moment-based Cornish–Fisher approximation, while adaptive dispatch selects between loop orderings.The dispatch heuristic does not always choose the faster loop order, and the loop-order choice primarily addresses short-series overhead.Source: §10 · pp. 54–55
• Complete complexity analyses enable comparisons with other classifiers while showing that library and function choices can substantially affect empirical runtime independently of theoretical complexity.This limitation means empirical runtime comparisons should be interpreted alongside implementation details, not theoretical complexity alone.Source: §10 · p. 55
• Roughly 1.7× faster feature extraction than exact mode comes with an average accuracy cost under half a percentage point, while still winning outright on over a third of datasets.Including classifier fitting largely removes the runtime gap, but the advantage re-emerges for inference-only cost and is most relevant when feature extraction is the bottleneck.Source: §10 · p. 55
• The study leaves open domain-validity enforcement, genuinely linear-time counting sort, transfer to other quantile-based extractors, and extension beyond univariate series.Independent multivariate channels would preserve the complexity class but require recalibrating dispatch constants and crossover size; jointly built intervals would require a new cost model.Source: §10 · p. 55
• Overall, a small, principled approximation applied where it helps most can make an already fast time-series classification method faster.The contribution is framed as a practical speed improvement rather than an unrestricted replacement for exact computation.Source: §10 · p. 56

• The publicly available UCR datasets, source code, reproduction instructions, and results support reuse and comparison under the BSD 3-Clause License.Datasets are available through the UCR Time Series Archive and tools such as aeon; the GitHub repository provides detailed reproduction instructions.Source: §11 · p. 56
• Generative artificial intelligence was used to generate code and analyze results, while the authors retain accountability for the manuscript and repository.Source: §11 · p. 56
• The study received no funding, and the authors declare no relevant financial or non-financial interests, conflicts, or affiliations.Source: §11 · p. 56

• Theorem 1 derives the exact number of base and shifted intervals, including the condition l ≥ 1.5·2^k for shifted intervals at the deepest level.The interval count is handled separately depending on whether the deepest-level shifted intervals are constructed.Source: Appendix A · p. 57
• Theorem 2 shows that total interval width has a leading Θ(k·l) term with a negative O(k) correction across the two deepest-level cases.The proof sums widths of base and shifted intervals while accounting for ceiling-rounding errors.Source: Appendix A · p. 57
• Theorem 5 characterizes length-one intervals: they can occur only at level k, with their count determined by the remainder of l after division by 2^k and by whether deepest-level shifted intervals exist.For l = 2^k + ρ, the deepest base intervals contain ρ width-two intervals and 2^(k+1)−l width-one intervals; shifted intervals alter this count when l ≥ 1.5·2^k.Source: Appendix A · p. 59
• Theorems 6–8 derive Quant’s sorting-cost bounds by summing base and shifted interval costs, then bounding deviations caused by non-dyadic interval lengths.The analysis uses convexity of f(m)=m·log2(m), treats saturated and unsaturated regimes separately, and shows rounding corrections are lower-order terms.Source: Appendix A · pp. 59–61
• Theorem 9 decomposes extraction cost for intervals wider than one into quantile-extraction cost proportional to the quantile count and mean-computation cost proportional to interval width.Width-one intervals require only direct copying and incur no sorting, interpolation, or mean-computation cost.Source: Appendix A · p. 63

Multiple representations

• Across all four representations, each representation has length Θ(l), so Quant’s total sort and extraction costs retain the single-representation orders Θ(l · e · log(l)) and Θ(e · l).The representation lengths are l, l−1, l−2, and ⌊l/2⌋+1, with l ≥ 3 required for all representations to be non-empty.Source: Appendix A · pp. 66–67

Quant complexity

• Quant’s exact processing cost is Θ(l · e · log(l)), with extraction asymptotically negligible relative to sorting in both saturated and unsaturated regimes.The resulting case split is Θ(d · l) when l ≥ 2^d−1 and Θ(l · log(l)) when l < 2^d−1.Source: Appendix A · pp. 64, 67

Implementation costs

• The interval-outer implementation’s cost is affine in the number of series with setup overhead, whereas the series-outer implementation processes each series independently with one compiled-call dispatch.The two costs are compared through a crossover n* = AI/(BS − BI) when the series-outer slope exceeds the interval-outer slope.Source: Appendix A · p. 68

MomentQuant complexity

• For MomentQuant, computing interval moments requires one Welford/Pebay pass, giving total moment cost Θ(e · l) and requiring no dependence on d beyond the interval structure.The four representation lengths remain those established for Quant, and the per-representation moment costs are each Θ(e · l).Source: Appendix A · pp. 68, 70

MomentQuant extraction

• MomentQuant’s extraction cost is also Θ(e · l), because moment-to-statistic conversion applies to every interval while Cornish–Fisher evaluation applies only to requested positions in non-trivial intervals.The exact per-interval extraction accounting separates the fixed conversion cost from Cornish–Fisher evaluations and bounds their combined total by Θ(W(l, d)).Source: Appendix A · pp. 68–69

MomentQuant complexity

• Unlike exact Quant, MomentQuant has moment-computation and extraction terms of the same order, so its total cost is Θ(e · l) in both saturated and unsaturated regimes.The proof explicitly contrasts this balanced cost with Quant’s sort-dominated exact algorithm.Source: Appendix A · pp. 69–70

• Theorem 29 shows that eT(l, d, ν) is Θ(e · l), with two cases obtained by splitting according to which term wins, as in Theorems 23 and 25.Source: Appendix A · p. 70
• Theorem 31 derives interval-outer cost from one batched moment computation, non-trivial-interval Cornish-Fisher calls, and marginal per-series extraction cost, summed over four sequential representations.Trivial intervals copy their known means at negligible cost; non-trivial intervals require genuine Cornish-Fisher evaluations.Source: Appendix A · p. 70
• Theorem 32 derives series-outer cost by summing n per-series overheads and compiled-kernel costs for each representation, with the four representations processed independently and sequentially.Source: Appendix A · pp. 70–71
• Theorem 33 follows the exact-algorithm proof after substituting approximate-algorithm costs, relying on affine dependence on n and a non-negative interval-outer intercept.Source: Appendix A · p. 71

Additional dataset results

• Figures B1–B5 show Pearson-correlation histograms between exact and approximated moment-based quantiles across depth levels for five additional datasets.Each panel reports the number of genuinely approximated columns and their median correlation; the datasets are ECG200, GunPoint, ItalyPowerDemand, Wafer, and Yoga.Source: Appendix B · p. 71, Figure B1 · p. 72, Figure B2 · p. 73
• The appendix provides depth-wise correlation distributions for ECG200, GunPoint, Wafer, and Yoga, whose series lengths are l = 96, 150, 152, and 426, respectively.Figures B1, B2, B4, and B5 each contain one histogram per depth level from 0 to 5.Source: Figure B1 · p. 72, Figure B2 · p. 73, Figure B4 · p. 75
• ItalyPowerDemand has no depth-5 histogram because its series length l = 24 makes the depth cap bind before the configured d = 6 is reached.Its populated depth levels are 0 through 4.Source: Appendix B · p. 71, Figure B3 · p. 74