{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T19:42:48Z","timestamp":1782934968050,"version":"3.54.5"},"reference-count":30,"publisher":"EDP Sciences","issue":"1","license":[{"start":{"date-parts":[[2019,2,14]],"date-time":"2019-02-14T00:00:00Z","timestamp":1550102400000},"content-version":"vor","delay-in-days":44,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Minist\u00e8re de l\u02bcEnseignement sup\u00e9rieur, de la Recherche et de l\u02bcInnovation"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2018,10,12]]},"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>The Piecewise Aggregate Approximation (PAA) is widely used in time series data mining because it allows to discretize, to reduce the length of time series and it is used as a subroutine by algorithms for patterns discovery, indexing, and classification of time series. However, it requires setting one parameter: the number of segments to consider during the discretization. The optimal parameter value is highly data dependent in particular on large time series. This paper presents a heuristic for time series compression with PAA which minimizes the loss of information. The heuristic is built upon the well known metaheuristic GRASP and strengthened with an inclusion of specific global search component. An extensive experimental evaluation on several time series datasets demonstrated its efficiency and effectiveness in terms of compression ratio, compression interpretability and classification.<\/jats:p>","DOI":"10.1051\/ro\/2018089","type":"journal-article","created":{"date-parts":[[2018,10,15]],"date-time":"2018-10-15T08:10:19Z","timestamp":1539591019000},"page":"243-259","source":"Crossref","is-referenced-by-count":13,"title":["Grasp heuristic for time series compression with piecewise aggregate approximation"],"prefix":"10.1051","volume":"53","author":[{"given":"Vanel Steve","family":"Siyou Fotso","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Engelbert","family":"Mephu Nguifo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Philippe","family":"Vaslin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"250","published-online":{"date-parts":[[2019,2,14]]},"reference":[{"key":"R1","unstructured":"Bagnall A., Keogh E., Lines J., Bostrom A., Large J., Time Series Classification Website. Available at: http:\/\/timeseriesclassification.com (2016)."},{"key":"R2","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1007\/s10618-016-0483-9","volume":"31","author":"Bagnall","year":"2017","journal-title":"Data Min. Knowl. Discov."},{"key":"R3","unstructured":"Camerra A., Palpanas T., Shieh J., Keogh E., isax 2.0: Indexing and mining one billion time series. In: 2010 IEEE 10th International Conference on Data Mining \u2013 ICDM (2010) 58\u201367."},{"key":"R4","doi-asserted-by":"crossref","first-page":"1519","DOI":"10.14778\/2350229.2350266","volume":"5","author":"Candan","year":"2012","journal-title":"VLDB Endowment"},{"key":"R5","unstructured":"Chen Y., Keogh E., Hu B., Begum N., Bagnall A., Mueen A., Batista G., The UCR time series classification archive. Available at: http:\/\/www.cs.ucr.edu\/~eamonn\/time_series_data\/ (2015)."},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Chu S., Keogh E.J., Hart D.M., Pazzani M.J., et al., Iterative deepening dynamic time warping for time series. In: Proc. of the 2002 SIAM International Conference on Data Mining. SIAM (2002) 195\u2013212.","DOI":"10.1137\/1.9781611972726.12"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Cu\u0159\u00edn J., Fleury P., Kleindienst J., Kessl R., Meeting state recognition from visual and aural labels. In: Learning for Multimodal Interaction, Springer, 2007, 24\u201325.","DOI":"10.1007\/978-3-540-78155-4_3"},{"key":"R8","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF01096763","volume":"6","author":"Feo","year":"1995","journal-title":"J. Glob. Optim."},{"key":"R9","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"Ibarra","year":"1975","journal-title":"J. ACM (JACM)"},{"key":"R10","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1109\/TASSP.1975.1162641","volume":"23","author":"Itakura","year":"1975","journal-title":"IEEE Trans. Acoust. Speech Signal Process."},{"key":"R11","doi-asserted-by":"crossref","first-page":"2231","DOI":"10.1016\/j.patcog.2010.09.022","volume":"44","author":"Jeong","year":"2011","journal-title":"Pattern Recogn."},{"key":"R12","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/s10618-015-0418-x","volume":"30","author":"Kate","year":"2016","journal-title":"Data Min. Knowl. Discov."},{"key":"R13","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/PL00011669","volume":"3","author":"Keogh","year":"2001","journal-title":"Knowl. Inform. Syst."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Keogh E.J., Pazzani M.J., Scaling up dynamic time warping for datamining applications. In: Sixth ACM SIGKDD. ACM (2000) 285\u2013289.","DOI":"10.1145\/347090.347153"},{"key":"R15","unstructured":"Keogh E.J., Pazzani M.J., Derivative dynamic time warping. In: 1st SIAM International Conference on Data Mining. SIAM (2001) 1\u201311."},{"key":"R16","unstructured":"Lin J., Keogh E., Lonardi S., Chiu B., A symbolic representation of time series, with implications for streaming algorithms. In: 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery. ACM (2003) 2\u201311."},{"key":"R17","unstructured":"Lkhagva B., Suzuki Y., Kawagoe K., Extended SAX: Extension of Symbolic aggregate approximation for financial time series data representation. DEWS2006 4A\u2013i8, 7 (2006)."},{"key":"R18","unstructured":"Longin J., Vasilis M., Qiang W., Rolf L., Chotirat A., Keogh E., Elastic partial matching of time series. In: 9th European Conference on Principles and Practice of Knowledge Discovery in Databases, Porto, Portugal (2005)."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Myers C., Rabiner L., Rosenberg A., Performance tradeoffs in dynamic time warping algorithms for isolated word recognition. IEEE Trans. Acoust. Speech Signal Process. 28 (1980) 623\u2013635.","DOI":"10.1109\/TASSP.1980.1163491"},{"key":"R20","unstructured":"Rakthanmanon T., Campana B., Mueen A., Batista G., Westover B., Zhu Q., Zakaria J., Keogh E., Searching and mining trillions of time series subsequences under dynamic time warping. In: 18th ACM SIGKDD (2012) 262\u2013270."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"Ratanamahatana C.A., Keogh E., Making time-series classification more accurate using learned constraints. In: Proc. of the 2004 SIAM International Conference on Data Mining. SIAM (2004) 11\u201322.","DOI":"10.1137\/1.9781611972740.2"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"Sakoe H., Chiba S., Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans. Acoust. Speech Signal Process. 26 (1978) 43\u201349.","DOI":"10.1109\/TASSP.1978.1163055"},{"key":"R23","doi-asserted-by":"crossref","first-page":"561","DOI":"10.3233\/IDA-2007-11508","volume":"11","author":"Salvador","year":"2007","journal-title":"Intell. Data Anal."},{"key":"R24","unstructured":"Siyou Fotso V.S., Mephu Nguifo E., Vaslin P., Comparaison des Algorithmes de classification. FDTW. Available at: http:\/\/fc.isima.fr\/~siyou\/fdtw (2016)."},{"key":"R25","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/j.neucom.2014.01.045","volume":"138","author":"Sun","year":"2014","journal-title":"Neurocomputing"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"Ulanova L., Begum N., Keogh E., Scalable clustering of time series with u-shapelets, In: 2015 SIAM International Conference on Data Mining. SIAM (2015) 900\u2013908.","DOI":"10.1137\/1.9781611974010.101"},{"key":"R27","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s10618-012-0250-5","volume":"26","author":"Wang","year":"2013","journal-title":"Data Min. Knowl. Discov."},{"key":"R28","doi-asserted-by":"crossref","first-page":"2787","DOI":"10.1016\/j.ins.2011.03.001","volume":"181","author":"Yu","year":"2011","journal-title":"Inform. Sci."},{"key":"R29","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.ins.2015.04.007","volume":"315","author":"Zhang","year":"2015","journal-title":"Inform. Sci."},{"key":"R30","unstructured":"Zhao J., Itti L., Shapedtw: shape dynamic time warping. Preprint arXiv: 1606.01601 (2016)."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2018089\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,28]],"date-time":"2020-08-28T18:58:30Z","timestamp":1598641110000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2018089"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":30,"journal-issue":{"issue":"1"},"alternative-id":["ro170169"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2018089","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"1290-3868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}