Fast Subsequence Matching in Time-Series Databases

Summary: Maps 1D time-series subsequences to a compact feature-space MBR set; sliding windows yield trails partitioned into sub-trails. Indexing with an R*-tree yields fast, length-agnostic subsequence queries, with 3×–100× speedups over scans (real and synthetic data). (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2807
Venue: SIGMOD
Year: 1994
Pagerank: 0.00046675394
Overall Rank: 41 | 99.73%
DOI: 10.1145/191839.191925

Incoming Non-self Citations Over Time

Authors

1. Christos Faloutsos (University of Maryland)
2. M. Ranganathan (IBM; University of Maryland)
3. Yannis Manolopoulos (Aristotle University of Thessaloniki; University of Maryland)

BibTeX Citation

@inproceedings{faloutsos_sigmod94,
        title = {{Fast Subsequence Matching in Time-Series Databases}},
        author = {Faloutsos, Christos and Ranganathan, M. and Manolopoulos, Yannis},
        series = {{SIGMOD} '94},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/191839.191925},
        url = {https://dl.acm.org/doi/10.1145/191839.191925},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 106 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,538	Scalable Time Series Compound Infrastructure	2022	SIGMOD	5.093636e-05
11,992	Scaling Locally Linear Embedding	2017	SIGMOD	5.093636e-05
12,009	Computing Longest Increasing Subsequences over Sequential Data Streams	2017	VLDB	5.093636e-05
12,120	SMiLer: A Semi-Lazy Time Series Prediction System for Sensors	2015	SIGMOD	5.093636e-05
12,471	Parsimonious Linear Fingerprinting for Time Series	2010	VLDB	5.093636e-05
12,777	Fast Algorithms for Time Series with applications to Finance, Physics, Music, Biology, and other Suspects	2004	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
13	Mining Association Rules between Sets of Items in Large Databases	1993	SIGMOD	0.0006567919
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00034590762
350	A Retrieval Technique for Similar Shapes	1991	SIGMOD	0.00020425134
440	An Interval Classifier for Database Mining Applications	1992	VLDB	0.00018409145

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	468	Fast Time Sequence Indexing for Arbitrary Lp Norms	2000	VLDB
2	1,084	A Data-adaptive and Dynamic Segmentation Index for Whole Matching on Time Series	2013	VLDB
3	8,780	The Inherent Time Complexity and An Efficient Algorithm for Subsequence Matching Problem	2022	VLDB
4	810	Similarity-Based Queries for Time Series Data	1997	SIGMOD
5	3,440	Approximate Embedding-Based Subsequence Matching of Time Series	2008	SIGMOD
6	5,162	Online Event-driven Subsequence Matching over Financial Data Streams	2004	SIGMOD
7	3,252	Fast Time-Series Searching with Scaling and Shifting	1999	PODS
8	6,858	A Generic Framework for Efficient and Effective Subsequence Retrieval	2012	VLDB
9	371	Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases	1995	VLDB
10	5,592	Ranked Subsequence Matching in Time-Series Databases	2007	VLDB