{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:14:12Z","timestamp":1779174852924,"version":"3.51.4"},"reference-count":91,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,10]]},"abstract":"<jats:p>Increasingly large data series collections are becoming commonplace across many different domains and applications. A key operation in the analysis of data series collections is similarity search, which has attracted lots of attention and effort over the past two decades. Even though several relevant approaches have been proposed in the literature, none of the existing studies provides a detailed evaluation against the available alternatives. The lack of comparative results is further exacerbated by the non-standard use of terminology, which has led to confusion and misconceptions. In this paper, we provide definitions for the different flavors of similarity search that have been studied in the past, and present the first systematic experimental evaluation of the efficiency of data series similarity search techniques. Based on the experimental results, we describe the strengths and weaknesses of each approach and give recommendations for the best approach to use under typical use cases. Finally, by identifying the shortcomings of each method, our findings lay the ground for solid further developments in the field.<\/jats:p>","DOI":"10.14778\/3282495.3282498","type":"journal-article","created":{"date-parts":[[2019,1,4]],"date-time":"2019-01-04T13:35:28Z","timestamp":1546608928000},"page":"112-127","source":"Crossref","is-referenced-by-count":56,"title":["The lernaean hydra of data series similarity search"],"prefix":"10.14778","volume":"12","author":[{"given":"Karima","family":"Echihabi","sequence":"first","affiliation":[{"name":"Mohammed V Univ."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kostas","family":"Zoumpatianos","sequence":"additional","affiliation":[{"name":"Harvard Univ."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Themis","family":"Palpanas","sequence":"additional","affiliation":[{"name":"Paris Descartes Univ."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Houda","family":"Benbrahim","sequence":"additional","affiliation":[{"name":"Mohammed V Univ."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,10]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Adhd-200. http:\/\/fcon_1000.projects.nitrc.org\/indi\/adhd200\/ 2018.  Adhd-200. http:\/\/fcon_1000.projects.nitrc.org\/indi\/adhd200\/ 2018."},{"key":"e_1_2_1_2_1","volume-title":"https:\/\/www.sdss3.org\/dr10\/data_access\/volume.php","author":"Sloan","year":"2018","unstructured":"Sloan digital sky survey. https:\/\/www.sdss3.org\/dr10\/data_access\/volume.php , 2018 . Sloan digital sky survey. https:\/\/www.sdss3.org\/dr10\/data_access\/volume.php, 2018."},{"key":"e_1_2_1_3_1","first-page":"69","volume-title":"Efficient similarity search in sequence databases","author":"Agrawal R.","year":"1993","unstructured":"R. Agrawal , C. Faloutsos , and A. Swami . Efficient similarity search in sequence databases . pages 69 -- 84 , 1993 . R. Agrawal, C. Faloutsos, and A. Swami. Efficient similarity search in sequence databases. pages 69--84, 1993."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDSP.1997.628089"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293348"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_19"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02279-1_31"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/we.2057"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0483-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_11_1","first-page":"359","volume-title":"AAAIWS","author":"Berndt D. J.","year":"1994","unstructured":"D. J. Berndt and J. Clifford . Using dynamic time warping to find patterns in time series . In AAAIWS , pages 359 -- 370 , 1994 . D. J. Berndt and J. Clifford. Using dynamic time warping to find patterns in time series. In AAAIWS, pages 359--370, 1994."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/253262.253345"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.124"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-012-0606-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/568518.568520"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/846218.847201"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1541880.1541882"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1577069.1577096"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367924"},{"key":"e_1_2_1_20_1","first-page":"15","volume-title":"Bulk loading the M-tree","author":"Ciaccia P.","year":"1998","unstructured":"P. Ciaccia and M. Patella . Bulk loading the M-tree . pages 15 -- 26 , Feb. 1998 . P. Ciaccia and M. Patella. Bulk loading the M-tree. pages 15--26, Feb. 1998."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/846219.847295"},{"key":"e_1_2_1_22_1","first-page":"426","volume-title":"Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB'97)","author":"Ciaccia P.","year":"1997","unstructured":"P. Ciaccia , M. Patella , and P. Zezula . M-tree: An efficient access method for similarity search in metric spaces. In M. Jarke, M. Carey, K. R. Dittrich, F. Lochovsky, P. Loucopoulos, and M. A. Jeusfeld, editors , Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB'97) , pages 426 -- 435 , Athens, Greece , Aug. 1997 . Morgan Kaufmann Publishers, Inc. P. Ciaccia, M. Patella, and P. Zezula. M-tree: An efficient access method for similarity search in metric spaces. In M. Jarke, M. Carey, K. R. Dittrich, F. Lochovsky, P. Loucopoulos, and M. A. Jeusfeld, editors, Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB'97), pages 426--435, Athens, Greece, Aug. 1997. Morgan Kaufmann Publishers, Inc."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081966"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350278"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735463"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/645801.669017"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454226"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3282495.3282498"},{"key":"e_1_2_1_29_1","volume-title":"SENTINEL-2 mission","author":"ESA.","year":"2018","unstructured":"ESA. SENTINEL-2 mission , 2018 . ESA. SENTINEL-2 mission, 2018."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191925"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/354756.354820"},{"key":"e_1_2_1_32_1","unstructured":"I. R. I. for Seismology with Artificial Intelligence. Seismic Data Access. http:\/\/ds.iris.edu\/data\/access\/ 2018.  I. R. I. for Seismology with Artificial Intelligence. Seismic Data Access. http:\/\/ds.iris.edu\/data\/access\/ 2018."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.240"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/645925.671516"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/mrm.1910400211"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_37_1","unstructured":"M. Hadjieleftheriou. The libspatialindex api January 2014. http:\/\/libspatialindex.github.io\/.  M. Hadjieleftheriou. The libspatialindex api January 2014. http:\/\/libspatialindex.github.io\/."},{"key":"e_1_2_1_38_1","first-page":"87","volume-title":"Practical data mining in a large utility company","author":"H\u00e9brail G.","year":"2000","unstructured":"G. H\u00e9brail . Practical data mining in a large utility company , pages 87 -- 95 . Physica-Verlag HD , Heidelberg , 2000 . G. H\u00e9brail. Practical data mining in a large utility company, pages 87--95. Physica-Verlag HD, Heidelberg, 2000."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCI.2014.2326100"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1998.10474114"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.1999.757470"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020607"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00011669"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1024988512476"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/3000292.3000335"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-004-0154-9"},{"key":"e_1_2_1_47_1","first-page":"42","article-title":"An online adaptive screening procedure for selective neuronal responses","author":"Knieling S.","year":"2017","unstructured":"S. Knieling , J. Niediek , E. Kutter , J. Bostroem , C. Elger , and F. Mormann . An online adaptive screening procedure for selective neuronal responses . Journal of Neuroscience Methods, 291(Supplement C):36 -- 42 , 2017 . S. Knieling, J. Niediek, E. Kutter, J. Bostroem, C. Elger, and F. Mormann. An online adaptive screening procedure for selective neuronal responses. Journal of Neuroscience Methods, 291(Supplement C):36 -- 42, 2017.","journal-title":"Journal of Neuroscience Methods, 291(Supplement C):36 --"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01889706"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775129"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/882082.882086"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3275366.3284968"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00149"},{"key":"e_1_2_1_53_1","volume-title":"Matrix profile X: Valmod - scalable discovery of variable-length motifs in data series","author":"Linardi M.","year":"2018","unstructured":"M. Linardi , Y. Zhu , T. Palpanas , and E. J. Keogh . Matrix profile X: Valmod - scalable discovery of variable-length motifs in data series . 2018 . M. Linardi, Y. Zhu, T. Palpanas, and E. J. Keogh. Matrix profile X: Valmod - scalable discovery of variable-length motifs in data series. 2018."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.actaastro.2006.08.015"},{"key":"e_1_2_1_55_1","volume-title":"Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. CoRR, abs\/1603.09320","author":"Malkov Y. A.","year":"2016","unstructured":"Y. A. Malkov and D. A. Yashunin . Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. CoRR, abs\/1603.09320 , 2016 . Y. A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. CoRR, abs\/1603.09320, 2016."},{"key":"e_1_2_1_56_1","first-page":"551","volume-title":"EDBT","author":"Mirylenka K.","year":"2016","unstructured":"K. Mirylenka , V. Christophides , T. Palpanas , I. Pefkianakis , and M. May . Characterizing home device usage from wireless traffic time series . In EDBT , pages 551 -- 562 , 2016 . K. Mirylenka, V. Christophides, T. Palpanas, I. Pefkianakis, and M. May. Characterizing home device usage from wireless traffic time series. In EDBT, pages 551--562, 2016."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3085504.3085515"},{"key":"e_1_2_1_58_1","volume-title":"August","author":"Mueen A.","year":"2017","unstructured":"A. Mueen , Y. Zhu , M. Yeh , K. Kamgar , K. Viswanathan , C. Gupta , and E. Keogh . The fastest similarity search algorithm for time series subsequences under euclidean distance , August 2017 . http:\/\/www.cs.unm.edu\/~mueen\/FastestSimilaritySearch.html. A. Mueen, Y. Zhu, M. Yeh, K. Kamgar, K. Viswanathan, C. Gupta, and E. Keogh. The fastest similarity search algorithm for time series subsequences under euclidean distance, August 2017. http:\/\/www.cs.unm.edu\/~mueen\/FastestSimilaritySearch.html."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814710.2814719"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49192-8_6"},{"key":"e_1_2_1_61_1","volume-title":"D4D Challenge session","author":"Paraskevopoulos P.","year":"2013","unstructured":"P. Paraskevopoulos , T.-C. Dinh , Z. Dashdorj , T. Pal-panas, and L. Serafini . Identification and characterization of human behavior patterns from mobile phone data . In D4D Challenge session , NetMob , 2013 . P. Paraskevopoulos, T.-C. Dinh, Z. Dashdorj, T. Pal-panas, and L. Serafini. Identification and characterization of human behavior patterns from mobile phone data. In D4D Challenge session, NetMob, 2013."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2018.8622293"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.5555\/846218.847198"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/253262.253264"},{"key":"e_1_2_1_65_1","volume-title":"Efficient retrieval of similar time sequences using DFT. CoRR, cs.DB\/9809033","author":"Rafiei D.","year":"1998","unstructured":"D. Rafiei and A. O. Mendelzon . Efficient retrieval of similar time sequences using DFT. CoRR, cs.DB\/9809033 , 1998 . D. Rafiei and A. O. Mendelzon. Efficient retrieval of similar time sequences using DFT. CoRR, cs.DB\/9809033, 1998."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339576"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.146"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2411594"},{"key":"e_1_2_1_69_1","first-page":"499","volume-title":"Odac: Hierarchical clustering of time series data streams","author":"Rodrigues P. P.","year":"2006","unstructured":"P. P. Rodrigues , J. Gama , and J. P. Pedroso . Odac: Hierarchical clustering of time series data streams . In J. Ghosh, D. Lambert, D. B. Skillicorn, and J. Srivastava, editors, SDM, pages 499 -- 503 . SIAM , 2006 . P. P. Rodrigues, J. Gama, and J. P. Pedroso. Odac: Hierarchical clustering of time series data streams. In J. Ghosh, D. Lambert, D. B. Skillicorn, and J. Srivastava, editors, SDM, pages 499--503. SIAM, 2006."},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835854"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247656"},{"issue":"2","key":"e_1_2_1_72_1","first-page":"40","article-title":"Tuning time series queries in finance: Case studies and recommendations","volume":"22","author":"Shasha D.","year":"1999","unstructured":"D. Shasha . Tuning time series queries in finance: Case studies and recommendations . IEEE Data Eng. Bull. , 22 ( 2 ): 40 -- 46 , 1999 . D. Shasha. Tuning time series queries in finance: Case studies and recommendations. IEEE Data Eng. Bull., 22(2):40--46, 1999.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401966"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401966"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1051\/0004-6361\/201322653"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1051\/0004-6361\/201322653"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735462"},{"key":"e_1_2_1_78_1","volume-title":"Southwest University Adult Lifespan Dataset (SALD) http:\/\/fcon_1000.projects.nitrc.org\/indi\/retro\/sald.html?utm_source=newsletter&utm_medium=email&utm_content=See%20Data&utm_campaign=indi-1","author":"S. University","year":"2018","unstructured":"S. University . Southwest University Adult Lifespan Dataset (SALD) http:\/\/fcon_1000.projects.nitrc.org\/indi\/retro\/sald.html?utm_source=newsletter&utm_medium=email&utm_content=See%20Data&utm_campaign=indi-1 , 2018 . S. University. Southwest University Adult Lifespan Dataset (SALD) http:\/\/fcon_1000.projects.nitrc.org\/indi\/retro\/sald.html?utm_source=newsletter&utm_medium=email&utm_content=See%20Data&utm_campaign=indi-1, 2018."},{"key":"e_1_2_1_79_1","volume-title":"http:\/\/sites.skoltech.ru\/compvision\/noimi","author":"Vision S. C.","year":"2018","unstructured":"S. C. Vision . Deep billion-scale indexing. http:\/\/sites.skoltech.ru\/compvision\/noimi , 2018 . S. C. Vision. Deep billion-scale indexing. http:\/\/sites.skoltech.ru\/compvision\/noimi, 2018."},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-012-0250-5"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536208"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2005.01.025"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.5555\/645924.671192"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1061\/(ASCE)0733-947X(2003)129:6(664)"},{"key":"e_1_2_1_85_1","volume-title":"Dpisax: Massively distributed partitioned isax","author":"Yagoubi D.-E.","year":"2017","unstructured":"D.-E. Yagoubi , R. Akbarinia , F. Masseglia , and T. Palpanas . Dpisax: Massively distributed partitioned isax . 2017 . D.-E. Yagoubi, R. Akbarinia, F. Masseglia, and T. Palpanas. Dpisax: Massively distributed partitioned isax. 2017."},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.226"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-017-0519-9"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516439"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0442-5"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0513-x"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783382"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3282495.3282498","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:31:50Z","timestamp":1672223510000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3282495.3282498"}},"subtitle":["an experimental evaluation of the state of the art"],"short-title":[],"issued":{"date-parts":[[2018,10]]},"references-count":91,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["10.14778\/3282495.3282498"],"URL":"https:\/\/doi.org\/10.14778\/3282495.3282498","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,10]]}}}