Pith. sign in

REVIEW 3 major objections 8 minor 1 cited by

Fast and Exact Similarity Search in less than a Blink of an Eye

T0 review · 3 major / 8 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A learned Fourier-summary index answers exact nearest-neighbor queries on billion-scale data series in tens of milliseconds.

desk verdict Valuable engineering with a real exactness gap: SFA bins learned from a 1% sample are not proven to cover all coefficients, so the 'exact' claim rests on an unproven lower bound. read the letter →

arxiv 2411.17483 v2 pith:SI27JJQY submitted 2024-11-26 cs.DB

Patrick Schäfer , Jakob Brand , Ulf Leser , Botao Peng , Themis Palpanas This is my paper · ORCID
classification cs.DB
keywords dataseriessimilaritysearchexactnearestneighborSymbolicFourierApproximationlowerboundingdistancetreeindexSIMDbillion-scalebenchmark
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that exact similarity search over very large collections of data series can be made dramatically faster by replacing the usual mean-based symbolic summary with a learned summary built on the Fourier transform. The proposed SOFA index combines a parallel tree structure with the Symbolic Fourier Approximation (SFA), in which each series is reduced to a few high-variance Fourier coefficients and each coefficient is quantized into symbols with bins learned from a sample of the data. Because the resulting lower bound to the z-normalized Euclidean distance is tighter than the bound from SAX, especially for high-frequency and non-Gaussian series, more candidates can be pruned without losing exactness. On a benchmark of 17 datasets containing one billion series, the paper reports median exact 1-nearest-neighbor query times of 58 ms, with average speedups of about 2 times over the prior tree-index baseline, 3-4 times over a flat L2 vector index, and up to 10 times over a parallel sequential scan. If correct, this makes exact, interactive search practical on noisy, high-frequency collections where mean-based summaries flatten the signal.

What carries the argument

The load-bearing object is the SFA word: a data series is mapped through the discrete Fourier transform to a short vector of real and imaginary coefficients, the coefficients with highest variance are kept, and each is replaced by a symbol from an alphabet of 256 using learned equi-width quantization intervals. The exactness of the search rests on the lower-bounding identity of Equations (1) and (2): the distance from a query coefficient to the nearest boundary of its assigned symbol, reweighted so the constant term is the mean and imaginary terms are doubled, never exceeds the true z-normalized Euclidean distance. That bound allows the tree index to prune leaves and series without ever missing the true nearest neighbor. The SIMD implementation processes eight or sixteen coefficient comparisons at once, uses bitmaps to handle the three possible positions of a query coefficient relative to a symbol's interval, and abandons a comparison as soon as the accumulated lower bound exceeds the best-so-far distance.

What would settle it

Take a dataset whose distribution has a heavy tail, index it with SOFA, and run queries where one indexed series has a selected Fourier coefficient outside the bins learned from the 1% sample; compute both the symbolic lower bound and the true z-normalized Euclidean distance. If any candidate's lower bound exceeds its true distance, the exactness guarantee is violated. Alternatively, inspect the code for the quantization step and check whether out-of-range coefficients are clamped into the outermost interval rather than handled as distances to the boundary, since clamping would break Equation (2).

Watch

Extended reading notes

Core claim

The central discovery is that variance-based selection of Fourier coefficients, rather than taking the first low-frequency coefficients, is what makes a symbolic Fourier summary suitable for exact indexing. SOFA transforms each data series with the discrete Fourier transform, keeps the real and imaginary coefficients with the largest variance, and quantizes each kept coefficient into one of 256 symbols using equi-width bins learned from a 1% sample of the data. The lower-bounding distance between a query's raw Fourier coefficients and a candidate's symbolic word is computed with masks and early abandoning under SIMD, and the exact-search framework uses that bound to prune candidates. The paper's experimental claim is that on all 17 datasets SOFA answers exact nearest-neighbor queries faster than the baselines, with the largest gains on high-frequency datasets such as seismic records, where the improvement over the mean-based symbolic index reaches 38 times.

Load-bearing premise

The lower-bounding guarantee holds only if every Fourier coefficient that is quantized falls inside the interval assigned to its symbol, yet the bins are learned from a 1% sample and the paper does not state how out-of-range coefficients are handled or prove that the sample covers the full range.

Editorial extensions

If this is right

  • Exact 1-nearest-neighbor queries on collections of 100 million series, each of length 96 to 256, can be answered in tens of milliseconds on a dual-socket server, making interactive exploration of billion-scale series collections practical.
  • For high-frequency or non-Gaussian data, replacing mean-based symbolic summaries with learned Fourier summaries can improve query times by more than an order of magnitude, because the lower bound tracks the variance that averaging flattens.
  • The learned bins and coefficient selection need to be computed only once per dataset; new queries reuse the same transformation, so the index itself stays cheap to maintain while query answering is fast.
  • Exact k-nearest-neighbor results inherit the speedup: the paper reports median times rising only from 58 ms for one neighbor to 98 ms for fifty, keeping ranked retrieval sub-second at scale.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the quantization bins are learned from a 1% sample, a natural extension is to make the bins adaptive: if new series arrive with Fourier coefficients outside the sampled range, an online bin-refinement strategy would be needed to preserve the lower-bounding guarantee, and the paper does not address that case.
  • The reported positive correlation between the mean frequency index of the selected coefficients and speedup suggests that the power spectrum of a dataset could be used to predict whether a Fourier-based index will pay off, before actually building it.
  • The same learned symbolic Fourier representation could serve as a fast approximate candidate generator: skipping the refinement on raw values would yield approximate answers whose error is controlled by the quantization width, an easy testbed for the approximate-search direction the paper flags as future work.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 8 minor

Summary. The paper proposes SOFA, an in-memory index for exact similarity search on data series under z-normalized Euclidean distance. SOFA combines a MESSI-style tree index with the Symbolic Fourier Approximation (SFA), selecting Fourier coefficients by highest variance, learning equi-width quantization bins, and using a SIMD-accelerated lower-bound distance. The authors evaluate SOFA on a new benchmark of 17 datasets totaling about 1 billion series and report speedups over MESSI, FAISS IndexFlatL2, and UCR Suite-P, with median 1-NN query times of 58 ms. The paper claims exactness via the GEMINI framework, relying on the SFA lower bound of Eq. (2).

Significance. If the exactness claim can be upheld, this is a valuable contribution: it shows that a learned Fourier-domain symbolic summarization can outperform SAX-based tree indexes on high-frequency data while retaining a lower-bounding guarantee. The proposed benchmark with 17 datasets and 1 billion series is a useful resource for the community. The paper also provides an open-source implementation (currently anonymized) and a detailed ablation study on lower-bound tightness. The main concern is that the exactness guarantee is not established because the quantization bins are learned from a 1% sample without proof that all indexed coefficients fall inside their assigned intervals.

major comments (3)
  1. [IV-E3, Eq. (2), Algorithms 1 and 2] The lower bound d2_SFA(A',B') <= d2_ED(A,B) is valid only if each indexed series coefficient a'_i lies inside the quantization interval I_i assigned to its symbol. Algorithm 1 learns intervals by equi-width binning over a 1% random sample (r=1%, line 10), and Algorithm 2 maps every coefficient into one of these finite intervals. The paper never states that the first and last bins are open-ended, nor proves that the sample range covers the full population. If a coefficient falls outside its interval, the distance-to-interval can exceed the true coefficient difference: for example, a'_i=10, I_i=[0,1], b'_i=9.5 yields dist^2=72.25 while (a'_i-b'_i)^2=0.25, violating the lower bound and hence the GEMINI exactness argument. This is a load-bearing gap: the title and abstract claim exactness, and Section IV-C relies on it.
  2. [V-C, Table IV] The sampling-rate experiment shows the mean query time keeps improving up to 5% sampling, which is an indication that the learned bins depend on the sample. The paper does not report any correctness check (e.g., comparing SOFA's results against exact brute force on a held-out subset) for any sampling rate. Without such a validation, or without a proof of coverage, the empirical speedups cannot be attributed to an exact method. Please add an experiment that verifies that SOFA returns the true nearest neighbors for all 100 queries on all 17 datasets (or on a representative subset) using the default and adversarial settings.
  3. [V-B, Tables II and III] Query times are reported only as means and medians over 17 datasets, with no error bars, confidence intervals, or repeated trials. Figure 10 shows that MESSI and SOFA have high variance across datasets, so the average speedup of '2-3 times faster than MESSI' may not be statistically robust. Please report the per-dataset speedups with dispersion measures (e.g., standard deviation across query sets or bootstrap CIs) and, if feasible, run multiple trials with different query sets to assess variability.
minor comments (8)
  1. [IV-E] The sentence 'SFA is not based on any assumptions' is too strong; the method assumes the 1% sample is representative and that equi-width bins are appropriate. Consider softening that statement.
  2. [V-C] The text says 'an experiment (Section IV-G)' but the sampling experiment is described in Section V-C; the cross-reference appears to be wrong.
  3. [Throughout] There are several typos: 'symblic' in the related work should be 'symbolic', '¿10' in Section V-B should be '>10', and 'structures' in the introduction should be 'structured'.
  4. [Table III] The row for 'UCR suite' lists '557' for 1-NN and then dashes; since the text explains that k-NN was not run for UCR, the dash for 3-NN onward is fine, but consider using '—' consistently for readability.
  5. [Figure 11] The legend shows 'SOFA + ED' and 'SOFA + EW' lines, but the text refers to 'Equi-width' and 'Equi-depth'; the figure legend should match the abbreviations used in the text to avoid confusion.
  6. [References] Reference [28] still uses 'A. Author(s)' and an anonymous repository link; update it to the final repository after acceptance.
  7. [V-D] The Pearson correlation of 0.51 is reported without a p-value or discussion of statistical significance; add the p-value or a confidence interval to support the claimed trend.
  8. [Table I] The benchmark is described as 'novel' but only five of the seventeen datasets are previously used in similarity search benchmarks; clarify that the novelty is in the assembled collection, not in the individual datasets.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: SOFA's speedup claims rest on external benchmark comparisons with held-out queries; SFA and MESSI self-citations are background building blocks, not load-bearing circular steps.

full rationale

The paper's central claim — that SOFA answers exact 1-NN and k-NN queries faster than MESSI, FAISS, and UCR Suite-P — is supported by runtime experiments on 17 externally sourced datasets with distinct held-out query sets (Table I and Section V-B), not by construction from the fitted SFA parameters. The lower-bound equation (2) is the previously published SFA LBD from Schäfer and Högqvist [14]; although that prior work shares an author with this paper, the inequality is a known, independently checkable mathematical statement and does not presuppose the present speedup result. MESSI [15,16] is also cited by the authors, but it is used as a comparative baseline and as an indexing template, not as the source of SOFA's exactness or performance advantage. The paper even reports that MESSI builds the index faster than SOFA, so the comparison is not flattering-by-construction. A genuine correctness gap exists: the learned bins in Algorithm 1 come from a 1% sample, and Eq. (2) is a valid lower bound only if every indexed Fourier coefficient lies inside the interval assigned by its symbol; the paper gives no proof or explicit out-of-range handling rule. However, that is a proof/correctness risk rather than circularity, because the claimed bound could fail rather than being equivalent to its input. The self-citations present are thus minor and non-load-bearing.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The central speedup claims rest on a small set of hyperparameters (word length, alphabet, leaf size, sampling ratio) and on the prior GEMINI/DFT/SFA lower-bounding theory. No new physical or conceptual entities are introduced. The principal unproven input is that bins learned from a 1% sample cover all indexed and query coefficients, which the paper does not establish.

free parameters (5)
  • word length l (number of Fourier values) = 16
    Set to 16 for both SAX and SFA in all experiments. Larger l improves lower-bound tightness but increases memory and time; chosen as a default, with leaf-size and sampling ablations but no full grid search.
  • alphabet size |Σ| = 256
    SAX default from 8-bit chars; SFA uses the same. Larger alphabets increase TLB but memory; used throughout all experiments.
  • leaf size = 20000
    Set 'initial-lbl-size', 'min-leaf-size', and 'leaf-size' to 20000; ablation in Figure 11 shows query times plateau around 10k series, so 20k is a hand-chosen point near the plateau.
  • sampling ratio r for MCB = 0.01
    SFA bins and coefficient indices are learned from 1% of the indexed data; Table IV shows median query times stabilize near 1%, while mean times improve up to 5%. This is a hand-chosen trade-off.
  • number of selected Fourier coefficients = 8 complex (16 real+imag values)
    Tied to word length 16; selected via K-ARGMAX on variance. The choice is not independently justified beyond the word-length default.
assumptions (5)
  • standard math GEMINI framework: if a summarization LBD obeys d' <= d, then searching in summarized space and pruning with the best-so-far distance returns exact nearest neighbors.
    Invoked in Section II-A and Definition 4. Standard, well-established result from Faloutsos et al. [12].
  • standard math DFT Parseval lower bound Eq. (1): d2_DFT(A',B') <= d2_ED(A,B) for the retained Fourier coefficients.
    Equation (1) from Rafiei and Mendelzon [52]; proof relies on Parseval's theorem for the orthogonal DFT basis. The paper uses it without reproving.
  • domain assumption SFA quantization mindist (Eq. 2) lower-bounds the DFT distance because each candidate coefficient lies inside its assigned quantization interval.
    Section IV-E3. This is the load-bearing unproven step: bins are learned from a 1% sample, and the paper does not show that out-of-sample coefficients remain inside their assigned bins. If a coefficient falls outside the learned range, Eq. 2 can exceed the true coefficient difference, violating the LBD and exactness.
  • domain assumption Indexed data and query data are z-normalized and of equal length n, and the query distribution is representative of the indexed distribution.
    Definition 2 and Section V-c. All methods assume z-normalized ED; SFA bins are learned from the indexed set, so queries outside that distribution could also violate the learned bins.
  • domain assumption L2 distance computed by FAISS IndexFlatL2 corresponds to the same z-normalized Euclidean distance used by the data series indices.
    Section V-A competitors. The paper does not state whether z-normalization was applied before FAISS indexing and querying, so the distance optimized by FAISS may differ from the z-ED used by SOFA and MESSI.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast and Exact Similarity Search in less than a Blink of an Eye." pith.science (2026). https://pith.science/paper/SI27JJQY

@misc{pith2026241117483,
  author       = {Pith},
  title        = {Pith review of: Fast and Exact Similarity Search in less than a Blink of an Eye},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SI27JJQY}},
  note         = {Machine review of arXiv:2411.17483}
}
abstract

Similarity search is a fundamental operation for analyzing data series (DS), which are ordered sequences of real values. To enhance efficiency, summarization techniques are employed that reduce the dimensionality of DS. SAX-based approaches are the state-of-the-art for exact similarity queries, but their performance degrades for high-frequency signals, such as noisy data, or for high-frequency DS. In this work, we present the SymbOlic Fourier Approximation index (SOFA), which implements fast, exact similarity queries. SOFA is based on two building blocks: a tree index (inspired by MESSI) and the SFA symbolic summarization. It makes use of a learned summarization method called Symbolic Fourier Approximation (SFA), which is based on the Fourier transform and utilizes a data-adaptive quantization of the frequency domain. To better capture relevant information in high-frequency signals, SFA selects the Fourier coefficients by highest variance, resulting in a larger value range, thus larger quantization bins. The tree index solution employed by SOFA makes use of the GEMINI-approach to answer exact similarity search queries using lower bounding distance measures, and an efficient SIMD implementation. We further propose a novel benchmark comprising $17$ diverse datasets, encompassing 1 billion DS. Our experimental results demonstrate that SOFA outperforms existing methods on exact similarity queries: it is up to 10 times faster than a parallel sequential scan, 3-4 times faster than FAISS, and 2 times faster on average than MESSI. For high-frequency datasets, we observe a remarkable 38-fold performance improvement.

Figures

Figures reproduced from arXiv: 2411.17483 by the authors.

Figure 1
Figure 1. TOP: PAA (orange) fails to approximate a data series (in gray) with high frequency, resulting in a flat line. Meanwhile FFT (in blue) closely mimics [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. The figure illustrates the summarization of a DS using SAX (top) [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. The figure illustrates the two summarization techniques iSAX (left) and SFA (right). SAX aggregates the DS over intervals using PAA, and quantizes [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: A comparison of the iSAX (left) and SFA (right) Euclidean LBD. [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]
Figure 5
Figure 5. Figure 5: Workflow of SOFA for exact similarity search. First, a fraction of the [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]
Figure 6
Figure 6. Figure 6: SIMD lower bound distance calculation illustration using bitmaps [PITH_FULL_IMAGE:figures/full_fig_p007_6.png]
Figure 7
Figure 7. Figure 7: presents the mean runtime results for index creation across three systems: SOFA using SFA, MESSI using SAX for summarization, and FAISS (IndexFlatL2, CPU) using all 17 datasets. The measurements exclude I/O times for reading datasets from disk. On average, index creati…
Figure 8
Figure 8. Figure 8: Index properties between MESSI and SOFA. [PITH_FULL_IMAGE:figures/full_fig_p010_8.png]
Figure 9
Figure 9. Figure 9: A comparison of median query times with an increasing number [PITH_FULL_IMAGE:figures/full_fig_p010_9.png]
Figure 10
Figure 10. Figure 10: A comparison of 1-NN query times with an increasing number [PITH_FULL_IMAGE:figures/full_fig_p011_10.png]
Figure 11
Figure 11. Figure 11: A comparison of 1-NN query times with an increasing leaf size. [PITH_FULL_IMAGE:figures/full_fig_p011_11.png]
Figure 14
Figure 14. Figure 14: A comparison of the tightness of lower bound (TLB) on [PITH_FULL_IMAGE:figures/full_fig_p012_14.png]
Figure 15
Figure 15. Figure 15: Critical Difference plot on the average ranks of the TLB on 120 [PITH_FULL_IMAGE:figures/full_fig_p012_15.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. BBC: Improving Large-k Approximate Nearest Neighbor Search with a Bucket-based Result Collector

    cs.DB 2026-04 unverdicted novelty 7.0 of 10

    BBC improves large-k ANN efficiency via bucketed candidate buffers and optimized re-ranking, delivering up to 3.8x speedup at recall@k=0.95.

Reference graph

Works this paper leans on

69 extracted references · 67 canonical work pages · cited by 1 Pith paper

  1. [1]

    Data series management: The road to big sequence analytics,

    T. Palpanas, “Data series management: The road to big sequence analytics,” SIGMOD Record, 2015

    work page 2015

  2. [2]

    Report on the first and second interdisciplinary time series analysis workshop (ITISA),

    T. Palpanas and V . Beckmann, “Report on the first and second interdisciplinary time series analysis workshop (ITISA),” SIGREC, 48(3), 2019

    work page 2019

  3. [3]

    Data series management (dagstuhl seminar 19282),

    A. J. Bagnall, R. L. Cole, T. Palpanas, and K. Zoumpa- tianos, “Data series management (dagstuhl seminar 19282),” Dagstuhl Reports, 9(7), 2019

    work page 2019

  4. [4]

    Scal- able machine learning on high-dimensional vectors: From data series to deep network embeddings,

    K. Echihabi, K. Zoumpatianos, and T. Palpanas, “Scal- able machine learning on high-dimensional vectors: From data series to deep network embeddings,” in Proceedings of the 10th International Conference on Web Intelligence, Mining and Semantics . New York; NY; United States: Association for Computing Machinery, 2020

    work page 2020

  5. [5]

    The ucr time series archive,

    H. A. Dau, A. Bagnall, K. Kamgar, C.-C. M. Yeh, Y . Zhu, S. Gharghabi, C. A. Ratanamahatana, and E. Keogh, “The ucr time series archive,” IEEE/CAA Journal of Automatica Sinica, vol. 6, no. 6, pp. 1293–1305, 2019

    2019

  6. [6]

    The lernaean hydra of data series similarity search: an experimental evaluation of the state of the art,

    K. Echihabi, K. Zoumpatianos, T. Palpanas, and H. Ben- brahim, “The lernaean hydra of data series similarity search: an experimental evaluation of the state of the art,” Proceedings of the VLDB Endowment, vol. 12, no. 2, pp. 112–127, 2018

    work page 2018

  7. [7]

    Bake off redux: a review and experimental evaluation of recent time series classification algorithms,

    M. Middlehurst, P. Sch ¨afer, and A. Bagnall, “Bake off redux: a review and experimental evaluation of recent time series classification algorithms,” Data Mining and Knowledge Discovery, vol. -, no. -, pp. 1–74, 2024

    work page 2024

  8. [8]

    A review and evaluation of elastic distance functions for time series clustering,

    C. Holder, M. Middlehurst, and A. Bagnall, “A review and evaluation of elastic distance functions for time series clustering,” Knowledge and Information Systems, vol. 66, no. 2, pp. 765–809, 2024

    work page 2024

Show all 69 references
  1. [9]

    Timeeval: A benchmarking toolkit for time series anomaly detec- tion algorithms,

    P. Wenig, S. Schmidl, and T. Papenbrock, “Timeeval: A benchmarking toolkit for time series anomaly detec- tion algorithms,” Proceedings of the VLDB Endowment , vol. 15, no. 12, pp. 3678–3681, 2022

    2022

  2. [10]

    isax: indexing and mining terabyte sized time series,

    J. Shieh and E. Keogh, “isax: indexing and mining terabyte sized time series,” in Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining . New York, USA: ACM, 2008, pp. 623–631

    2008

  3. [11]

    Evolution of a data series index: The isax family of data series indexes,

    T. Palpanas, “Evolution of a data series index: The isax family of data series indexes,” in Information Search, Integration, and Personalization (ISIP) . Heraklion, Greece: Springer, 2019, pp. 68–83

    2019

  4. [12]

    Fast subsequence matching in time-series databases,

    C. Faloutsos, M. Ranganathan, and Y . Manolopoulos, “Fast subsequence matching in time-series databases,” in SIGMOD. Minneapolis, Minnesota, USA: ACM, 1994, pp. 419–429

    1994

  5. [13]

    Efficient similarity search in sequence databases,

    R. Agrawal, C. Faloutsos, and A. Swami, “Efficient similarity search in sequence databases,” in Foundations of Data Organization and Algorithms: 4th International Conference, FODO’93 Chicago, Illinois, USA, October 13–15, 1993 Proceedings 4 . Chicago, Illinois, USA: Springer, ...

    1993

  6. [14]

    Sfa: a symbolic fourier approximation and index for similarity search in high dimensional datasets,

    P. Sch ¨afer and M. H ¨ogqvist, “Sfa: a symbolic fourier approximation and index for similarity search in high dimensional datasets,” in EDBT. Berlin, Germany: OpenProceedings, 2012, pp. 516–527

    2012

  7. [15]

    Messi: In- memory data series indexing,

    B. Peng, P. Fatourou, and T. Palpanas, “Messi: In- memory data series indexing,” in 2020 IEEE 36th Inter- national Conference on Data Engineering (ICDE), IEEE. Dallas, Texas: IEEE, 2020, pp. 337–348

    2020

  8. [16]

    Fast data series indexing for in-memory data,

    ——, “Fast data series indexing for in-memory data,” The VLDB Journal, vol. 30, no. 6, pp. 1041–1067, 2021

    2021

  9. [17]

    Search- ing and mining trillions of time series subsequences under dynamic time warping,

    T. Rakthanmanon, B. Campana, A. Mueen, G. Batista, B. Westover, Q. Zhu, J. Zakaria, and E. Keogh, “Search- ing and mining trillions of time series subsequences under dynamic time warping,” in Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery an...

    2012

  10. [18]

    Billion-scale similarity search with gpus,

    J. Johnson, M. Douze, and H. J ´egou, “Billion-scale similarity search with gpus,” IEEE Transactions on Big Data, vol. 7, no. 3, pp. 535–547, 2019

    2019

  11. [19]

    Dimensionality reduction for fast similarity search in large time series databases,

    E. Keogh, K. Chakrabarti, M. Pazzani, and S. Mehrotra, “Dimensionality reduction for fast similarity search in large time series databases,” Knowledge and information Systems, vol. 3, pp. 263–286, 2001

    2001

  12. [20]

    The input/output com- plexity of sorting and related problems,

    A. Aggarwal and J. S. Vitter, “The input/output com- plexity of sorting and related problems,” Commun. ACM, vol. 31, no. 9, pp. 1116–1127, 1988

    1988

  13. [21]

    On adaptive control pro- cesses,

    R. Bellman and R. Kalaba, “On adaptive control pro- cesses,” Automatic Control, IRE Transactions on , vol. 4, no. 2, pp. 1–9, 1959

    1959

  14. [22]

    Multidimensional range queries on modern hardware,

    S. Sprenger, P. Sch ¨afer, and U. Leser, “Multidimensional range queries on modern hardware,” in Proceedings of the 30th International Conference on Scientific and Statistical Database Management. Bozen-Bolzano Italy: ACM, 2018, pp. 1–12

    2018

  15. [23]

    A sym- bolic representation of time series, with implications for streaming algorithms,

    J. Lin, E. Keogh, S. Lonardi, and B. Chiu, “A sym- bolic representation of time series, with implications for streaming algorithms,” in Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery. New York, USA: ACM, 2003, pp. 2–11

    2003

  16. [24]

    Introduction to intel advanced vector exten- sions,

    C. Lomont, “Introduction to intel advanced vector exten- sions,” Intel White Paper, 2011

    2011

  17. [25]

    Exploit every cycle: Vectorized time series algorithms on modern commodity cpus,

    B. Tang, M. L. Yiu, Y . Li et al. , “Exploit every cycle: Vectorized time series algorithms on modern commodity cpus,” in IMDM, 2016

    2016

  18. [26]

    Paris+: Data series indexing on multi-core architectures,

    B. Peng, P. Fatourou, and T. Palpanas, “Paris+: Data series indexing on multi-core architectures,” IEEE Trans- actions on Knowledge and Data Engineering , vol. 33, no. 5, pp. 2151–2164, 2020

    2020

  19. [27]

    Paris: The next destination for fast data series in- dexing and query answering,

    ——, “Paris: The next destination for fast data series in- dexing and query answering,” in2018 IEEE International Conference on Big Data (Big Data), IEEE. Seattle, W A, USA: IEEE, 2018, pp. 791–800

    2018

  20. [28]

    Sofa repository,

    A. Author(s), “Sofa repository,” https://anonymous. 4open.science/r/MESSI-SFA-C4D3/, 2024

    2024

  21. [29]

    Locally adaptive dimensionality reduction for indexing large time series databases,

    K. Chakrabarti, E. J. Keogh, S. Mehrotra, and M. J. Pazzani, “Locally adaptive dimensionality reduction for indexing large time series databases,” ACM Trans. Database Syst., vol. 27, no. 2, pp. 188–228, 2002

    2002

  22. [30]

    Index- able pla for efficient similarity search,

    Q. Chen, L. Chen, X. Lian, Y . Liu, and J. X. Yu, “Index- able pla for efficient similarity search,” in Proceedings of the 33rd international conference on Very large data bases. Vienna, Austria: VLDB, 2007, pp. 435–446

    2007

  23. [31]

    Indexing spatio-temporal trajectories with chebyshev polynomials,

    Y . Cai and R. Ng, “Indexing spatio-temporal trajectories with chebyshev polynomials,” in Proceedings of the 2004 ACM SIGMOD international conference on Management of data. Paris, France: ACM, 2004, pp. 599–610

    2004

  24. [32]

    Similarity search over time-series data using wavelets,

    I. Popivanov and R. J. Miller, “Similarity search over time-series data using wavelets,” in Proceedings 18th in- ternational conference on data engineering , IEEE. San Jose, CA, USA: IEEE, 2002, pp. 212–221

    2002

  25. [33]

    isax: disk-aware mining and indexing of massive time series datasets,

    J. Shieh and E. Keogh, “isax: disk-aware mining and indexing of massive time series datasets,” Data Mining and Knowledge Discovery , vol. 19, pp. 24–57, 2009

    2009

  26. [34]

    isax 2.0: Indexing and mining one billion time series,

    A. Camerra, T. Palpanas, J. Shieh, and E. J. Keogh, “isax 2.0: Indexing and mining one billion time series,” in ICDM. Sydney, Australia: IEEE, 2010, pp. 58–67

    2010

  27. [35]

    Beyond one billion time series: indexing and mining very large time series collections with sax2+,

    A. Camerra, J. Shieh, T. Palpanas, T. Rakthanmanon, and E. Keogh, “Beyond one billion time series: indexing and mining very large time series collections with sax2+,” Knowledge and information systems , vol. 39, no. 1, pp. 123–151, 2014

    2014

  28. [36]

    Ads: the adaptive data series index,

    K. Zoumpatianos, S. Idreos, and T. Palpanas, “Ads: the adaptive data series index,” The VLDB Journal , vol. 25, pp. 843–866, 2016

    2016

  29. [37]

    Dpisax: Massively distributed partitioned isax,

    D. E. Yagoubi, R. Akbarinia, F. Masseglia, and T. Pal- panas, “Dpisax: Massively distributed partitioned isax,” in ICDM. New Orleans, LA, USA: IEEE, 2017

    2017

  30. [38]

    Massively distributed time series indexing and querying,

    ——, “Massively distributed time series indexing and querying,” TKDE, vol. 32, no. 1, pp. 108–120, 2020

    2020

  31. [39]

    ULISSE: ULtra compact Index for Variable-Length Similarity SEarch in Data Series,

    M. Linardi and T. Palpanas, “ULISSE: ULtra compact Index for Variable-Length Similarity SEarch in Data Series,” in ICDE. VLDB Endowment, 2018

    2018

  32. [40]

    Scalable data series subsequence matching with ulisse,

    ——, “Scalable data series subsequence matching with ulisse,” VLDBJ, 2020

    2020

  33. [41]

    Coconut: A scalable bottom-up approach for building data series indexes,

    H. Kondylakis, N. Dayan, K. Zoumpatianos, and T. Pal- panas, “Coconut: A scalable bottom-up approach for building data series indexes,” PVLDB, 2018

    2018

  34. [42]

    Coconut: sortable summarizations for scalable indexes over static and streaming data series,

    ——, “Coconut: sortable summarizations for scalable indexes over static and streaming data series,” The VLDB Journal, vol. 28, pp. 847–869, 2019

    2019

  35. [43]

    Hercules against data series similarity search,

    K. Echihabi, P. Fatourou, K. Zoumpatianos, T. Palpanas, and H. Benbrahim, “Hercules against data series similarity search,” Proc. VLDB Endow. , vol. 15, no. 10, pp. 2005–2018, 2022. [Online]. Available: https://www.vldb.org/pvldb/vol15/p2005-echihabi.pdf

    2005

  36. [44]

    Dumpy: A compact and adaptive index for large data series collections,

    Z. Wang, Q. Wang, P. Wang, T. Palpanas, and W. Wang, “Dumpy: A compact and adaptive index for large data series collections,” Proc. ACM Manag. Data , vol. 1, no. 1, pp. 111:1–111:27, 2023. [Online]. Available: https://doi.org/10.1145/3588965

    2023 doi

  37. [45]

    Elastic similarity and distance measures for multivari- ate time series,

    A. Shifaz, C. Pelletier, F. Petitjean, and G. I. Webb, “Elastic similarity and distance measures for multivari- ate time series,” Knowledge and Information Systems , vol. 65, no. 6, pp. 2665–2698, 2023

    2023

  38. [46]

    iSAX: indexing and mining terabyte sized time series,

    J. Shieh and E. Keogh, “iSAX: indexing and mining terabyte sized time series,” in KDD, 2008

    2008

  39. [47]

    Evolution of a Data Series Index,

    T. Palpanas, “Evolution of a Data Series Index,” CCIS, vol. 1197, 2020

    2020

  40. [48]

    A brief survey of vector databases,

    X. Xie, H. Liu, W. Hou, and H. Huang, “A brief survey of vector databases,” in 2023 9th International Conference on Big Data and Information Analytics (BigDIA) , IEEE. Budapest, Hungary: IEEE, 2023, pp. 364–371

    2023

  41. [49]

    Approximate nearest neighbor search in high dimensional vector databases: Current research and fu- ture directions

    Y . Tian, Z. Yue, R. Zhang, X. Zhao, B. Zheng, and X. Zhou, “Approximate nearest neighbor search in high dimensional vector databases: Current research and fu- ture directions.” IEEE Data Eng. Bull. , vol. 46, no. 3, pp. 39–54, 2023

    2023

  42. [50]

    Mass: distance profile of a query over a time series,

    S. Zhong and A. Mueen, “Mass: distance profile of a query over a time series,” Data Mining and Knowledge Discovery, pp. 1–27, 2024

    2024

  43. [51]

    Return of the Lernaean Hydra: Experimen- tal Evaluation of Data Series Approximate Similarity Search,

    K. Echihabi, K. Zoumpatianos, T. Palpanas, and H. Ben- brahim, “Return of the Lernaean Hydra: Experimen- tal Evaluation of Data Series Approximate Similarity Search,” PVLDB, 2019

    2019

  44. [52]

    Efficient retrieval of simi- lar time sequences using DFT,

    D. Rafiei and A. Mendelzon, “Efficient retrieval of simi- lar time sequences using DFT,” in FODO. Kobe, Japan: Springer, 1998, pp. 249–257

    1998

  45. [53]

    Intel 64 and ia-32 architectures opti- mization reference manual,

    I. Coorporation, “Intel 64 and ia-32 architectures opti- mization reference manual,” 2016

    2016

  46. [54]

    Seisbench—a toolbox for machine learning in seismology,

    J. Woollam, J. M ¨unchmeyer, F. Tilmann, A. Riet- brock, D. Lange, T. Bornstein, T. Diehl, C. Giunchi, F. Haslinger, D. Jozinovi ´c et al., “Seisbench—a toolbox for machine learning in seismology,” Seismological So- ciety of America , vol. 93, no. 3, pp. 1695–1709, 2022

    2022

  47. [55]

    Long-term variability of agn at hard x-rays,

    S. Soldi, V . Beckmann, W. H. Baumgartner, G. Ponti, C. R. Shrader, P. Lubi ´nski, H. Krimm, F. Mattana, and J. Tueller, “Long-term variability of agn at hard x-rays,” Astronomy & Astrophysics, vol. 563, p. A57, 2014

    2014

  48. [56]

    Results of the neurips’21 challenge on billion-scale approximate nearest neighbor search,

    H. V . Simhadri, G. Williams, M. Aum ¨uller, M. Douze, A. Babenko, D. Baranchuk, Q. Chen, L. Hosseini, R. Krishnaswamny, G. Srinivasa et al. , “Results of the neurips’21 challenge on billion-scale approximate nearest neighbor search,” in NeurIPS 2021 Competitions and Demonstra...

    2021

  49. [57]

    Efficient indexing of billion-scale datasets of deep descriptors,

    A. Babenko and V . Lempitsky, “Efficient indexing of billion-scale datasets of deep descriptors,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Las Vegas, NV , USA: IEEE, 2016, pp. 2055–2063

    2016

  50. [58]

    Convolutional neural network for seismic phase clas- sification, performance demonstration over a local seis- mic network,

    J. Woollam, A. Rietbrock, A. Bueno, and S. De Angelis, “Convolutional neural network for seismic phase clas- sification, performance demonstration over a local seis- mic network,” Seismological Research Letters , vol. 90, no. 2A, pp. 491–502, 2019

    2019

  51. [59]

    Learning the deep and the shallow: Deep-learning-based depth phase picking and earthquake depth estimation,

    J. M ¨unchmeyer, J. Saul, and F. Tilmann, “Learning the deep and the shallow: Deep-learning-based depth phase picking and earthquake depth estimation,” Seismological Research Letters, vol. 95, no. 3, pp. 1543–1557, 2024

    2024

  52. [60]

    Local earthquakes detection: A benchmark dataset of 3-component seismograms built on a global scale,

    F. Magrini, D. Jozinovi ´c, F. Cammarano, A. Miche- lini, and L. Boschi, “Local earthquakes detection: A benchmark dataset of 3-component seismograms built on a global scale,” Artificial Intelligence in Geosciences , vol. 1, pp. 1–10, 2020

    2020

  53. [61]

    Leveraging deep learning in global 24/7 real- time earthquake monitoring at the national earthquake information center,

    W. L. Yeck, J. M. Patton, Z. E. Ross, G. P. Hayes, M. R. Guy, N. B. Ambruz, D. R. Shelly, H. M. Benz, and P. S. Earle, “Leveraging deep learning in global 24/7 real- time earthquake monitoring at the national earthquake information center,” Seismological Society of America , v...

    2021

  54. [62]

    Pickblue: Seismic phase picking for ocean bottom seismometers with deep learning,

    T. Bornstein, D. Lange, J. M ¨unchmeyer, J. Wool- lam, A. Rietbrock, G. Barcheck, I. Grevemeyer, and F. Tilmann, “Pickblue: Seismic phase picking for ocean bottom seismometers with deep learning,” Earth and Space Science, vol. 11, no. 1, p. e2023EA003332, 2024

    2024

  55. [63]

    Obstransformer: a deep- learning seismic phase picker for obs data using au- tomated labelling and transfer learning,

    A. Niksejel and M. Zhang, “Obstransformer: a deep- learning seismic phase picker for obs data using au- tomated labelling and transfer learning,” Geophysical Journal International, vol. 237, no. 1, pp. 485–505, 2024

    2024

  56. [64]

    Curated pacific northwest ai-ready seismic dataset,

    Y . Ni, A. Hutko, F. Skene, M. Denolle, S. Malone, P. Bodin, R. Hartog, and A. Wright, “Curated pacific northwest ai-ready seismic dataset,” Seismica, vol. 2, no. 1, pp. –, May 2023. [Online]. Available: https://seismica.library.mcgill.ca/article/view/368

    2023

  57. [65]

    Southwest university adult lifespan dataset (sald),

    S. University, “Southwest university adult lifespan dataset (sald),” http://fcon 1000.projects.nitrc.org/indi/ retro/sald.html, 2018

    2018

  58. [66]

    Southern california earthquake center (scedc),

    E. Center, “Southern california earthquake center (scedc),” Caltech. Dataset, vol. -, no. -, pp. –, 2013

    2013

  59. [67]

    Searching in one billion vectors: re-rank with source coding,

    H. J ´egou, R. Tavenard, M. Douze, and L. Amsaleg, “Searching in one billion vectors: re-rank with source coding,” in 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , IEEE. Prague, Czech Republic: IEEE, 2011, pp. 861– 864

    2011

  60. [68]

    Stanford earthquake dataset (stead): A global data set of seismic signals for ai,

    S. M. Mousavi, Y . Sheng, W. Zhu, and G. C. Beroza, “Stanford earthquake dataset (stead): A global data set of seismic signals for ai,” IEEE Access, vol. 7, pp. 179 464– 179 476, 2019

    2019

  61. [69]

    Txed: The texas earthquake dataset for ai,

    Y . Chen, A. Savvaidis, O. M. Saad, G.-C. Dino Huang, D. Siervo, V . O’Sullivan, C. McCabe, B. Uku, P. Fleck, G. Burke et al., “Txed: The texas earthquake dataset for ai,” Seismological Research Letters , vol. 95, no. 3, pp. 2013–2022, 2024

    2013

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.