{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,25]],"date-time":"2023-09-25T14:23:53Z","timestamp":1695651833990},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,2]]},"abstract":"Many modern applications produce massive amounts of data series that need to be analyzed, requiring efficient similarity search operations. However, the state-of-the-art data series indexes that are used for this purpose do not scale well for massive datasets in terms of performance, or storage costs. We pinpoint the problem to the fact that existing summarizations of data series used for indexing cannot be sorted while keeping similar data series close to each other in the sorted order. This leads to two design problems. First, traditional bulk-loading algorithms based on sorting cannot be used. Instead, index construction takes place through slow top-down insertions, which create a non-contiguous index that results in many random I\/Os. Second, data series cannot be sorted and split across nodes evenly based on their median value; thus, most leaf nodes are in practice nearly empty. This further slows down query speed and amplifies storage costs. To address these problems, we present Coconut. The first innovation in Coconut is an inverted, sortable data series summarization that organizes data series based on a z-order curve, keeping similar series close to each other in the sorted order. As a result, Coconut is able to use bulk-loading techniques that rely on sorting to quickly build a contiguous index using large sequential disk I\/Os. We then explore prefix-based and median-based splitting policies for bottom-up bulk-loading, showing that median-based splitting outperforms the state of the art, ensuring that all nodes are densely populated. Overall, we show analytically and empirically that Coconut dominates the state-of-the-art data series indexes in terms of construction speed, query speed, and storage costs.<\/jats:p>","DOI":"10.14778\/3184470.3184472","type":"journal-article","created":{"date-parts":[[2020,2,16]],"date-time":"2020-02-16T19:50:53Z","timestamp":1581882653000},"page":"677-690","source":"Crossref","is-referenced-by-count":4,"title":["Coconut"],"prefix":"10.14778","volume":"11","author":[{"given":"Haridimos","family":"Kondylakis","sequence":"first","affiliation":[{"name":"FORTH-ICS"}]},{"given":"Niv","family":"Dayan","sequence":"additional","affiliation":[{"name":"Harvard University"}]},{"given":"Kostas","family":"Zoumpatianos","sequence":"additional","affiliation":[{"name":"Harvard University"}]},{"given":"Themis","family":"Palpanas","sequence":"additional","affiliation":[{"name":"Paris Descartes University"}]}],"member":"320","published-online":{"date-parts":[[2018,10,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"http:\/\/ds.iris.edu\/data\/access\/","year":"2016","unstructured":"Incorporated Research Institutions for Seismology - Seismic Data Access. http:\/\/ds.iris.edu\/data\/access\/ , 2016 . Incorporated Research Institutions for Seismology - Seismic Data Access. http:\/\/ds.iris.edu\/data\/access\/, 2016."},{"key":"e_1_2_1_2_1","volume-title":"http:\/\/fcon_1000.projects.nitrc.org\/indi\/adhd200\/","year":"2017","unstructured":"Adhd-200. http:\/\/fcon_1000.projects.nitrc.org\/indi\/adhd200\/ , 2017 . Adhd-200. http:\/\/fcon_1000.projects.nitrc.org\/indi\/adhd200\/, 2017."},{"key":"e_1_2_1_3_1","volume-title":"https:\/\/www.sdss3.org\/dr10\/data_access\/volume.php","year":"2017","unstructured":"Sloan digital sky survey. https:\/\/www.sdss3.org\/dr10\/data_access\/volume.php , 2017 . Sloan digital sky survey. https:\/\/www.sdss3.org\/dr10\/data_access\/volume.php, 2017."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/645415.652239"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353376"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.124"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-012-0606-6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/568518.568520"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1541880.1541882"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064054"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191925"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2940329"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCI.2014.2326100"},{"key":"e_1_2_1_16_1","first-page":"68","volume-title":"CIDR 2007","author":"Idreos S.","year":"2007","unstructured":"S. Idreos , M. L. Kersten , and S. Manegold . Database cracking . In CIDR 2007 , pages 68 -- 78 , 2007 . S. Idreos, M. L. Kersten, and S. Manegold. Database cracking. In CIDR 2007, pages 68--78, 2007."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.1999.757470"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020607"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-015-0418-x"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/876886.880107"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00011669"},{"key":"e_1_2_1_22_1","first-page":"239","volume-title":"KDD","author":"Keogh E. J.","year":"1998","unstructured":"E. J. Keogh and M. J. Pazzani . An enhanced representation of time series which allows fast and accurate classification, clustering and relevance feedback . In KDD , pages 239 -- 243 , 1998 . E. J. Keogh and M. J. Pazzani. An enhanced representation of time series which allows fast and accurate classification, clustering and relevance feedback. In KDD, pages 239--243, 1998."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253332"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/645482.653437"},{"key":"e_1_2_1_25_1","first-page":"546","volume-title":"ICDE","author":"Li C.","year":"1996","unstructured":"C. Li , P. S. Yu , and V. Castelli . Hierarchyscan: A hierarchical similarity search algorithm for databases of long sequences . In ICDE , pages 546 -- 553 , 1996 . C. Li, P. S. Yu, and V. Castelli. Hierarchyscan: A hierarchical similarity search algorithm for databases of long sequences. In ICDE, pages 546--553, 1996."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2005.01.025"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/882082.882096"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00149"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183744"},{"key":"e_1_2_1_30_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_31_1","volume-title":"A computer oriented geodetic data base and a new technique in file sequencing","author":"Morton G. M.","year":"1966","unstructured":"G. M. Morton . A computer oriented geodetic data base and a new technique in file sequencing . Ottawa, International Business Machines Company , 1966 . G. M. Morton. A computer oriented geodetic data base and a new technique in file sequencing. Ottawa, International Business Machines Company, 1966."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2014.52"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-010-0176-8"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807188"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814710.2814719"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49192-8_6"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCS.2017.155"},{"key":"e_1_2_1_39_1","volume-title":"D4D Challenge session","author":"Paraskevopoulos P.","year":"2013","unstructured":"P. Paraskevopoulos , T.-C. Dinh , Z. Dashdorj , T. Palpanas , 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. Palpanas, 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_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824078"},{"key":"e_1_2_1_41_1","first-page":"126","volume-title":"ICDE","author":"K.","year":"1999","unstructured":"K. pong Chan and A. W. Fu. Efficient time series matching by wavelets . In ICDE , pages 126 -- 133 , 1999 . K. pong Chan and A. W. Fu. Efficient time series matching by wavelets. In ICDE, pages 126--133, 1999."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/846218.847198"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253264"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339576"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.146"},{"key":"e_1_2_1_46_1","volume-title":"Database management systems (3. ed.)","author":"Ramakrishnan R.","year":"2003","unstructured":"R. Ramakrishnan and J. Gehrke . Database management systems (3. ed.) . McGraw-Hill , 2003 . R. Ramakrishnan and J. Gehrke. Database management systems (3. ed.). McGraw-Hill, 2003."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335449"},{"key":"e_1_2_1_48_1","first-page":"506","volume-title":"Three myths about dynamic time warping data mining","author":"Ratanamahatana C. A.","year":"2005","unstructured":"C. A. Ratanamahatana and E. J. Keogh . Three myths about dynamic time warping data mining . In SIAM , pages 506 -- 510 , 2005 . C. A. Ratanamahatana and E. J. Keogh. Three myths about dynamic time warping data mining. In SIAM, pages 506--510, 2005."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276320"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2411594"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190727"},{"issue":"2","key":"e_1_2_1_52_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_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-009-0125-6"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401966"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1051\/0004-6361\/201322653"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536208"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143974"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2017.151"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557122"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610498"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824099"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0442-5"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783382"},{"key":"e_1_2_1_64_1","doi-asserted-by":"crossref","unstructured":"K.\n Zoumpatianos\n and \n T.\n Palpanas\n . \n Data series management: Fulfilling the need for big sequence analytics\n . \n In ICDE 2018\n . K. Zoumpatianos and T. Palpanas. Data series management: Fulfilling the need for big sequence analytics. In ICDE 2018.","DOI":"10.1109\/ICDE.2018.00211"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3184470.3184472","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:57:55Z","timestamp":1672225075000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3184470.3184472"}},"subtitle":["a scalable bottom-up approach for building data series indexes"],"short-title":[],"issued":{"date-parts":[[2018,2]]},"references-count":64,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["10.14778\/3184470.3184472"],"URL":"https:\/\/doi.org\/10.14778\/3184470.3184472","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,2]]}}}