{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T09:19:32Z","timestamp":1773825572580,"version":"3.50.1"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,8,26]]},"abstract":"<jats:p>Similarity search on time series is an essential operation in many applications. In the state-of-the-art methods, such as the R-tree based methods, SAX and iSAX, time series are by default divided into equi-length segments globally, that is, all time series are segmented in the same way. Those methods then focus on how to approximate or symbolize the segments and construct indexes. In this paper, we make an important observation: global segmentation of all time series may incur unnecessary cost in space and time for indexing time series. We develop DSTree, a data adaptive and dynamic segmentation index on time series. In addition to savings in space and time, our new index can provide tight upper and lower bounds on distances between time series. An extensive empirical study shows that our new index DSTree supports time series similarity search effectively and efficiently.<\/jats:p>","DOI":"10.14778\/2536206.2536208","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"793-804","source":"Crossref","is-referenced-by-count":73,"title":["A data-adaptive and dynamic segmentation index for whole matching on time series"],"prefix":"10.14778","volume":"6","author":[{"given":"Yang","family":"Wang","sequence":"first","affiliation":[{"name":"School of Computer Science, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peng","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jian","family":"Pei","sequence":"additional","affiliation":[{"name":"School of Computing Science, Simon Fraser University, Burnaby, BC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sheng","family":"Huang","sequence":"additional","affiliation":[{"name":"IBM Research China, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,8]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"69","volume-title":"FODO","author":"Agrawal R.","year":"1993","unstructured":"R. Agrawal , C. Faloutsos , and A. N. Swami . Efficient similarity search in sequence databases . In FODO , pages 69 - 84 , 1993 . R. Agrawal, C. Faloutsos, and A. N. Swami. Efficient similarity search in sequence databases. In FODO, pages 69-84, 1993."},{"key":"e_1_2_1_2_1","first-page":"599","volume-title":"SIGMOD","author":"Cai Y.","year":"2004","unstructured":"Y. Cai and R. Ng . Indexing spatio-temporal trajectories with chebyshev polynomials . In SIGMOD , pages 599 - 610 , 2004 . Y. Cai and R. Ng. Indexing spatio-temporal trajectories with chebyshev polynomials. In SIGMOD, pages 599-610, 2004."},{"key":"e_1_2_1_3_1","first-page":"58","volume-title":"ICDM","author":"Camerra A.","year":"2010","unstructured":"A. Camerra , T. Palpanas , J. Shieh , and E. Keogh . isax 2.0: Indexing and mining one billion time series . In ICDM , pages 58 - 67 , 2010 . A. Camerra, T. Palpanas, J. Shieh, and E. Keogh. isax 2.0: Indexing and mining one billion time series. In ICDM, pages 58-67, 2010."},{"key":"e_1_2_1_4_1","first-page":"126","volume-title":"ICDE","author":"Chan K.","year":"1999","unstructured":"K. Chan and A. Fu . Efficient time series matching by wavelets . In ICDE , pages 126 - 133 , 1999 . K. Chan and A. Fu. Efficient time series matching by wavelets. In ICDE, pages 126-133, 1999."},{"key":"e_1_2_1_5_1","first-page":"435","volume-title":"VLDB","author":"Chen Q.","year":"2007","unstructured":"Q. Chen , L. Chen , X. Lian , Y. Liu , and J. Yu . Indexable pla for efficient similarity search . In VLDB , pages 435 - 446 , 2007 . Q. Chen, L. Chen, X. Lian, Y. Liu, and J. Yu. Indexable pla for efficient similarity search. In VLDB, pages 435-446, 2007."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1145\/191839.191925","volume-title":"SIGMOD","author":"Faloutsos C.","year":"1994","unstructured":"C. Faloutsos , M. Ranganathan , and Y. Manolopoulos . Fast subsequence matching in time-series databases . In SIGMOD , pages 419 - 429 , 1994 . C. Faloutsos, M. Ranganathan, and Y. Manolopoulos. Fast subsequence matching in time-series databases. In SIGMOD, pages 419-429, 1994."},{"key":"e_1_2_1_7_1","volume-title":"SIGMOD","author":"Guttman A.","year":"1984","unstructured":"A. Guttman . R-trees : a dynamic index structure for spatial searching . In SIGMOD , 1984 . A. Guttman. R-trees: a dynamic index structure for spatial searching. In SIGMOD, 1984."},{"key":"e_1_2_1_8_1","first-page":"166","volume-title":"SIGMOD","author":"Kanth K.","year":"1998","unstructured":"K. Kanth , D. Agrawal , and A. Singh . Dimensionality reduction for similarity searching in dynamic databases . In SIGMOD , pages 166 - 176 , 1998 . K. Kanth, D. Agrawal, and A. Singh. Dimensionality reduction for similarity searching in dynamic databases. In SIGMOD, pages 166-176, 1998."},{"key":"e_1_2_1_9_1","first-page":"490","volume-title":"CSIE","author":"Karamitopoulos L.","year":"2009","unstructured":"L. Karamitopoulos and G. Evangelidis . A dispersion-based paa representation for time series . In CSIE , pages 490 - 494 , 2009 . L. Karamitopoulos and G. Evangelidis. A dispersion-based paa representation for time series. In CSIE, pages 490-494, 2009."},{"key":"e_1_2_1_10_1","volume-title":"VLDB, page 1268","author":"Keogh E.","year":"2006","unstructured":"E. Keogh . A decade of progress in indexing and mining large time series databases . In VLDB, page 1268 , 2006 . E. Keogh. A decade of progress in indexing and mining large time series databases. In VLDB, page 1268, 2006."},{"key":"e_1_2_1_11_1","first-page":"263","volume-title":"KAIS","author":"Keogh E.","year":"2000","unstructured":"E. Keogh , K. Chakrabarti , M. Pazzani , and S. Mehrotra . Dimensionality reduction for fast similarity search in large time series databases . In KAIS , pages 263 - 286 , 2000 . E. Keogh, K. Chakrabarti, M. Pazzani, and S. Mehrotra. Dimensionality reduction for fast similarity search in large time series databases. In KAIS, pages 263-286, 2000."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1145\/375663.375680","volume-title":"SIGMOD","author":"Keogh E.","year":"2001","unstructured":"E. Keogh , K. Chakrabarti , M. Pazzani , and S. Mehrotra . Locally adaptive dimensionality reduction for indexing large time series databases . In SIGMOD , pages 151 - 162 , 2001 . E. Keogh, K. Chakrabarti, M. Pazzani, and S. Mehrotra. Locally adaptive dimensionality reduction for indexing large time series databases. In SIGMOD, pages 151-162, 2001."},{"key":"e_1_2_1_13_1","first-page":"102","volume-title":"SIGKDD","author":"Keogh E.","year":"2002","unstructured":"E. Keogh and S. Kasetty . On the need for time series data mining benchmarks: a survey and empirical demonstration . In SIGKDD , pages 102 - 111 , 2002 . E. Keogh and S. Kasetty. On the need for time series data mining benchmarks: a survey and empirical demonstration. In SIGKDD, pages 102-111, 2002."},{"key":"e_1_2_1_14_1","volume-title":"SIGKDD","author":"Keogh E.","year":"1998","unstructured":"E. Keogh and M. Pazzani . An enhanced representation of time series which allows fast and accurate classification, clustering and relevance feedback . In SIGKDD , 1998 . E. Keogh and M. Pazzani. An enhanced representation of time series which allows fast and accurate classification, clustering and relevance feedback. In SIGKDD, 1998."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/882082.882086","volume-title":"DMKD","author":"Lin J.","year":"2003","unstructured":"J. Lin , E. Keogh , S. Lonardi , and B. Chiu . A symbolic representation of time series, with implications for streaming algorithms . In DMKD , pages 2 - 11 , 2003 . J. Lin, E. Keogh, S. Lonardi, and B. Chiu. A symbolic representation of time series, with implications for streaming algorithms. In DMKD, pages 2-11, 2003."},{"key":"e_1_2_1_16_1","first-page":"623","volume-title":"SIGKDD","author":"Shieh J.","year":"2008","unstructured":"J. Shieh and E. Keogh . isax: Indexing and mining terabyte sized time series . In SIGKDD , pages 623 - 631 , 2008 . J. Shieh and E. Keogh. isax: Indexing and mining terabyte sized time series. In SIGKDD, pages 623-631, 2008."},{"key":"e_1_2_1_17_1","first-page":"109","volume-title":"SDM","author":"Vlachos M.","year":"2009","unstructured":"M. Vlachos , S. S. Kozat , and P. S. Yu . Optimal distance bounds on time-series data . In SDM , pages 109 - 120 , 2009 . M. Vlachos, S. S. Kozat, and P. S. Yu. Optimal distance bounds on time-series data. In SDM, pages 109-120, 2009."},{"key":"e_1_2_1_18_1","first-page":"748","volume-title":"SIGKDD","author":"Wei L.","year":"2006","unstructured":"L. Wei and E. Keogh . Semi-supervised time series classification . In SIGKDD , pages 748 - 753 , 2006 . L. Wei and E. Keogh. Semi-supervised time series classification. In SIGKDD, pages 748-753, 2006."},{"key":"e_1_2_1_19_1","first-page":"490","volume-title":"ICDM","author":"Wei L.","year":"2005","unstructured":"L. Wei , E. Keogh , H. Van Herle , and A. Mafra-Neto . Atomic wedgie: Efficient query filtering for streaming time series . In ICDM , pages 490 - 497 , 2005 . L. Wei, E. Keogh, H. Van Herle, and A. Mafra-Neto. Atomic wedgie: Efficient query filtering for streaming time series. In ICDM, pages 490-497, 2005."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"1033","DOI":"10.1145\/1143844.1143974","volume-title":"ICML","author":"Xi X.","year":"2006","unstructured":"X. Xi , E. Keogh , C. Shelton , L. Wei , and C. Ratanamahatana . Fast time series classification using numerosity reduction . In ICML , pages 1033 - 1040 , 2006 . X. Xi, E. Keogh, C. Shelton, L. Wei, and C. Ratanamahatana. Fast time series classification using numerosity reduction. In ICML, pages 1033-1040, 2006."},{"key":"e_1_2_1_21_1","first-page":"385","volume-title":"VLDB","author":"Yi B.","year":"2000","unstructured":"B. Yi and C. Faloutsos . Fast time sequence indexing for arbitrary lp norms . In VLDB , pages 385 - 394 , 2000 . B. Yi and C. Faloutsos. Fast time sequence indexing for arbitrary lp norms. In VLDB, pages 385-394, 2000."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2536206.2536208","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,28]],"date-time":"2024-05-28T00:01:58Z","timestamp":1716854518000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2536206.2536208"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8]]},"references-count":21,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2013,8,26]]}},"alternative-id":["10.14778\/2536206.2536208"],"URL":"https:\/\/doi.org\/10.14778\/2536206.2536208","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,8]]}}}