The DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
Fast subsequence matching in time-series databases
Open accessAbstract
We present an efficient indexing method to locate 1-dimensional subsequences within a collection of sequences, such that the subsequences match a given (query) pattern within a specified tolerance. The idea is to map each data sequences into a small set of multidimensional rectangles in feature space. Then, these rectangles can be readily indexed using traditional spatial access methods, like the R*-tree [9]. In more detail, we use a sliding window over the data sequence and extract its features; the result is a trail in feature space. We propose an efficient and effective algorithm to divide such trails into sub-trails, which are subsequently represented by their Minimum Bounding Rectangles (MBRs). We also examine queries of varying lengths, and we show how to handle each case efficiently. We implemented our method and carried out experiments on synthetic and real data (stock price movements). We compared the method to sequential scanning, which is the only obvious competitor. The results were excellent: our method accelerated the search time from 3 times up to 100 times.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Basic local alignment search tool
Altschul, S. F., Gish, W., Miller, W., Myers, E. W., & Lipman, D. J. (1990) · Journal of Molecular Biology · doi:10.1006/jmbi.1990.9999 · Cited by 98,669
Mining association rules between sets of items in large databases
Agrawal, R., Imieliński, T., & Swami, A. (1993) · Proceedings of the 1993 ACM SIGMOD international conference on Management of data · doi:10.1145/170035.170072 · Cited by 14,907
R-trees: a dynamic index structure for spatial searching
Guttman, A. (1984) · Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84 · doi:10.1145/602259.602266 · Cited by 6,580
The R*-tree: an efficient and robust access method for points and rectangles
Beckmann, N., Kriegel, H.-P., Schneider, R., & Seeger, B. (1990) · Proceedings of the 1990 ACM SIGMOD international conference on Management of data · doi:10.1145/93597.98741 · Cited by 4,161
The JPEG still picture compression standard
Wallace, G. K. (1991) · Communications of the ACM · doi:10.1145/103085.103089 · Cited by 3,784
The design and analysis of spatial data structures
Samet, H. (1989) · CERN Document Server (European Organization for Nuclear Research) · Cited by 2,380
Mark, J. W. (1975) · Proceedings of the IEEE · doi:10.1109/proc.1975.9993 · Cited by 1,565
Database mining: a performance perspective
Agrawal, R., Imielinski, T., & Swami, A. (1993) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.250074 · Cited by 1,505
The R*-tree: an efficient and robust access method for points and rectangles
Beckmann, N., Kriegel, H.-P., Schneider, R., & Seeger, B. (1990) · ACM SIGMOD Record · doi:10.1145/93605.98741 · Cited by 1,424
Efficient and effective Querying by Image Content
Faloutsos, C., Barber, R., Flickner, M., Hafner, J., Niblack, W., Petkovic, D., & Equitz, W. (1994) · Journal of Intelligent Information Systems · doi:10.1007/bf00962238 · Cited by 1,249
Self-citationThe Analysis of Time Series: An Introduction
Chatfield, C. (1984) · Springer eBooks · doi:10.1007/978-1-4899-2921-1 · Cited by 516
An Interval Classifier for Database Mining Applications
Agrawal, R., Ghosh, S. P., Imieliński, T., Iyer, B. R., & Swami, A. (1992) · Cited by 264
Cited by
Data mining: an overview from a database perspective
Chen, M.-S., Han, J., & Yu, P. S. (1996) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.553155 · Cited by 2,232
Time-series clustering – A decade review
Aghabozorgi, S., Seyed Shirkhorshidi, A., & Ying Wah, T. (2015) · Information Systems · doi:10.1016/j.is.2015.04.007 · Cited by 1,826
Experiencing SAX: A novel symbolic representation of time series
Lin, J., Keogh, E., Wei, L., & Lonardi, S. (2007) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-007-0064-z · Cited by 1,618
A review on time series data mining
Fu, T.-C. (2011) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2010.09.007 · Cited by 1,500
Esling, P., & Agon, C. (2012) · ACM Computing Surveys · doi:10.1145/2379776.2379788 · Cited by 997
Metadata
- Authors
- Faloutsos, C., Ranganathan, M., & Manolopoulos, Y.
- Venue
- ACM SIGMOD Record
- Published
- 1994-05-24
- Volume
- 23
- Issue
- 2
- Pages
- 419-429
- ISSN
- 0163-5808 (ISSN-L)
- OpenAlex
- W3147178137
- Cited by
- 722
- References
- 12
- FWCI
- 6.18
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.