{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,13]],"date-time":"2025-09-13T15:50:08Z","timestamp":1757778608222,"version":"3.40.3"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031183669"},{"type":"electronic","value":"9783031183676"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-18367-6_12","type":"book-chapter","created":{"date-parts":[[2022,10,20]],"date-time":"2022-10-20T16:05:36Z","timestamp":1666281936000},"page":"225-253","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximating Length-Restricted Means Under Dynamic Time Warping"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3446-4343","authenticated-orcid":false,"given":"Maike","family":"Buchin","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1943-2589","authenticated-orcid":false,"given":"Anne","family":"Driemel","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6105-2846","authenticated-orcid":false,"given":"Koen","family":"van Greevenbroek","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5079-5003","authenticated-orcid":false,"given":"Ioannis","family":"Psarros","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8984-1962","authenticated-orcid":false,"given":"Dennis","family":"Rohde","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,21]]},"reference":[{"issue":"6","key":"12_CR1","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1093\/bioinformatics\/17.6.495","volume":"17","author":"J Aach","year":"2001","unstructured":"Aach, J., Church, G.M.: Aligning gene expression time series with time warping algorithms. Bioinformatics 17(6), 495\u2013508 (2001)","journal-title":"Bioinformatics"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Abboud, A., Backurs, A., Williams, V.V.: Tight hardness results for LCS and other sequence similarity measures. In: Guruswami, V. (ed.) IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17\u201320 October 2015, pp. 59\u201378. IEEE Computer Society (2015)","DOI":"10.1109\/FOCS.2015.14"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Abdulla, W.H., Chow, D., Sin, G.: Cross-words reference template for DTW-based speech recognition systems. In: TENCON 2003. Conference on Convergent Technologies for Asia-Pacific Region, vol. 4, pp. 1576\u20131579 (2003)","DOI":"10.1109\/TENCON.2003.1273186"},{"key":"12_CR4","unstructured":"Berndt, D.J., Clifford, J.: Using dynamic time warping to find patterns in time series. In: Fayyad, U.M., Uthurusamy, R. (eds.) Knowledge Discovery in Databases: Papers from the 1994 AAAI Workshop, Seattle, Washington, USA, July 1994. Technical report WS-94-03, pp. 359\u2013370. AAAI Press (1994)"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Brankovic, M., Buchin, K., Klaren, K., Nusser, A., Popov, A., Wong, S.: (k, l)-medians clustering of trajectories using continuous dynamic time warping. In: Lu, C., Wang, F., Trajcevski, G., Huang, Y., Newsam, S.D., Xiong, L. (eds.) SIGSPATIAL 2020: 28th International Conference on Advances in Geographic Information Systems, Seattle, WA, USA, 3\u20136 November 2020, pp. 99\u2013110. ACM (2020)","DOI":"10.1145\/3397536.3422245"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Brill, M., Fluschnik, T., Froese, V., Jain, B.J., Niedermeier, R., Schultz, D.: Exact mean computation in dynamic time warping spaces. In: Proceedings of the 2018 SIAM International Conference on Data Mining, SDM 2018, 3\u20135 May 2018, San Diego Marriott Mission Valley, San Diego, CA, USA, pp. 540\u2013548 (2018)","DOI":"10.1137\/1.9781611975321.61"},{"issue":"1","key":"12_CR7","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/s10618-018-0604-8","volume":"33","author":"M Brill","year":"2018","unstructured":"Brill, M., Fluschnik, T., Froese, V., Jain, B., Niedermeier, R., Schultz, D.: Exact mean computation in dynamic time warping spaces. Data Min. Knowl. Disc. 33(1), 252\u2013291 (2018). https:\/\/doi.org\/10.1007\/s10618-018-0604-8","journal-title":"Data Min. Knowl. Disc."},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"Bringmann, K., K\u00fcnnemann, M.: Quadratic conditional lower bounds for string problems and dynamic time warping. In: Guruswami, V. (ed.) IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17\u201320 October 2015, pp. 79\u201397. IEEE Computer Society (2015)","DOI":"10.1109\/FOCS.2015.15"},{"issue":"5","key":"12_CR9","doi-asserted-by":"publisher","first-page":"1552","DOI":"10.1137\/S0097539796260321","volume":"28","author":"H Br\u00f6nnimann","year":"1999","unstructured":"Br\u00f6nnimann, H., Chazelle, B., Matousek, J.: Product range spaces, sensitive sampling, and derandomization. SIAM J. Comput. 28(5), 1552\u20131575 (1999)","journal-title":"SIAM J. Comput."},{"key":"12_CR10","unstructured":"Buchin, K., Driemel, A., Struijs, M.: On the hardness of computing an average curve. In: 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020, 22\u201324 June 2020, T\u00f3rshavn, Faroe Islands, pp. 19:1\u201319:19 (2020)"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Buchin, M., Driemel, A., Rohde, D.: Approximating $$(k,\\ell )$$-median clustering for polygonal curves. In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, 10\u201313 January 2021, pp. 2697\u20132717. SIAM (2021)","DOI":"10.1137\/1.9781611976465.160"},{"issue":"3","key":"12_CR12","doi-asserted-by":"publisher","first-page":"1854","DOI":"10.1137\/19M1255781","volume":"34","author":"L Bulteau","year":"2020","unstructured":"Bulteau, L., Froese, V., Niedermeier, R.: Tight hardness results for consensus problems on circular strings and time series. SIAM J. Discret. Math. 34(3), 1854\u20131883 (2020)","journal-title":"SIAM J. Discret. Math."},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Caiani, E.G., et al.: Warped-average template technique to track on a cycle-by-cycle basis the cardiac filling phases on left ventricular volume. In: Computers in Cardiology 1998, vol. 25 (Cat. No.98CH36292), pp. 73\u201376 (1998)","DOI":"10.1109\/CIC.1998.731723"},{"issue":"1","key":"12_CR14","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0304-3975(91)90261-Y","volume":"84","author":"B Chazelle","year":"1991","unstructured":"Chazelle, B., Edelsbrunner, H., Guibas, L.J., Sharir, M.: A singly exponential stratification scheme for real semi-algebraic varieties and its applications. Theoret. Comput. Sci. 84(1), 77\u2013105 (1991)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"Datta, S., Karmakar, C.K., Palaniswami, M.: Averaging methods using dynamic time warping for time series classification. In: 2020 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 2794\u20132798 (2020)","DOI":"10.1109\/SSCI47803.2020.9308409"},{"issue":"2","key":"12_CR16","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., O\u2019Rourke, J., Seidel, R.: Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput. 15(2), 341\u2013363 (1986)","journal-title":"SIAM J. Comput."},{"key":"12_CR17","doi-asserted-by":"crossref","unstructured":"Har-peled, S.: Geometric Approximation Algorithms. American Mathematical Society, USA (2011)","DOI":"10.1090\/surv\/173"},{"key":"12_CR18","doi-asserted-by":"crossref","unstructured":"Hautam\u00e4ki, V., Nykanen, P., Franti, P.: Time-series clustering by approximate prototypes. In: 2008 19th International Conference on Pattern Recognition, pp. 1\u20134 (2008)","DOI":"10.1109\/ICPR.2008.4761105"},{"issue":"9","key":"12_CR19","doi-asserted-by":"publisher","first-page":"2169","DOI":"10.1016\/j.patcog.2008.11.030","volume":"42","author":"D Lemire","year":"2009","unstructured":"Lemire, D.: Faster retrieval with a two-pass dynamic-time-warping lower bound. Pattern Recogn. 42(9), 2169\u20132180 (2009)","journal-title":"Pattern Recogn."},{"key":"12_CR20","doi-asserted-by":"publisher","first-page":"2129","DOI":"10.1109\/TSP.2019.2897958","volume":"67","author":"YT Liu","year":"2019","unstructured":"Liu, Y.T., Zhang, Y., Zeng, M.: Adaptive global time sequence averaging method using dynamic time warping. IEEE Trans. Signal Process. 67, 2129\u20132142 (2019)","journal-title":"IEEE Trans. Signal Process."},{"key":"12_CR21","unstructured":"Luca, A.D., Hang, A., Brudy, F., Lindner, C., Hussmann, H.: Touch me once and i know it\u2019s you!: implicit authentication based on touch screen patterns. In: Konstan, J.A., Chi, E.H., H\u00f6\u00f6k, K. (eds.) CHI Conference on Human Factors in Computing Systems, CHI 2012, Austin, TX, USA, 05\u201310 May 2012, pp. 987\u2013996. ACM (2012)"},{"key":"12_CR22","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J Matousek","year":"2002","unstructured":"Matousek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, New York (2002). https:\/\/doi.org\/10.1007\/978-1-4613-0039-7"},{"key":"12_CR23","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"M Mitzenmacher","year":"2017","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis, 2nd edn. Cambridge University Press, Cambridge (2017)","edition":"2"},{"key":"12_CR24","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.patcog.2017.08.015","volume":"74","author":"M Morel","year":"2018","unstructured":"Morel, M., Achard, C., Kulpa, R., Dubuisson, S.: Time-series averaging using constrained dynamic time warping with tolerance. Pattern Recogn. 74, 77\u201389 (2018)","journal-title":"Pattern Recogn."},{"key":"12_CR25","unstructured":"Muda, L., Begam, M., Elamvazuthi, I.: Voice recognition algorithms using MEL frequency cepstral coefficient (MFCC) and dynamic time warping (DTW) techniques (2010)"},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"Munich, M.E., Perona, P.: Continuous dynamic time warping for translation-invariant curve alignment with applications to signature verification. In: Proceedings of the International Conference on Computer Vision, Kerkyra, Corfu, Greece, 20\u201325 September 1999, pp. 108\u2013115. IEEE Computer Society (1999)","DOI":"10.1109\/ICCV.1999.791205"},{"key":"12_CR27","doi-asserted-by":"publisher","first-page":"107699","DOI":"10.1016\/j.patcog.2020.107699","volume":"112","author":"M Okawa","year":"2021","unstructured":"Okawa, M.: Time-series averaging and local stability-weighted dynamic time warping for online signature verification. Pattern Recogn. 112, 107699 (2021)","journal-title":"Pattern Recogn."},{"issue":"3","key":"12_CR28","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1016\/j.patcog.2010.09.013","volume":"44","author":"F Petitjean","year":"2011","unstructured":"Petitjean, F., Ketterlin, A., Gan\u00e7arski, P.: A global averaging method for dynamic time warping, with applications to clustering. Pattern Recognit. 44(3), 678\u2013693 (2011)","journal-title":"Pattern Recognit."},{"key":"12_CR29","doi-asserted-by":"crossref","unstructured":"Rabiner, L., Wilpon, J.: Considerations in applying clustering techniques to speaker independent word recognition. In: ICASSP 1979. IEEE International Conference on Acoustics, Speech, and Signal Processing, vol. 4, pp. 578\u2013581 (1979)","DOI":"10.1109\/ICASSP.1979.1170822"},{"issue":"1","key":"12_CR30","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1109\/TASSP.1978.1163055","volume":"26","author":"H Sakoe","year":"1978","unstructured":"Sakoe, H., Chiba, S.: Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans. Acoust. Speech Signal Process. 26(1), 43\u201349 (1978)","journal-title":"IEEE Trans. Acoust. Speech Signal Process."},{"key":"12_CR31","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N Sauer","year":"1972","unstructured":"Sauer, N.: On the density of families of sets. J. Comb. Theory Ser. A 13, 145\u2013147 (1972)","journal-title":"J. Comb. Theory Ser. A"},{"key":"12_CR32","unstructured":"Schaar, N., Froese, V., Niedermeier, R.: Faster binary mean computation under dynamic time warping. In: 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, 17\u201319 June 2020, Copenhagen, Denmark, pp. 28:1\u201328:13 (2020)"},{"key":"12_CR33","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1016\/j.patcog.2017.08.012","volume":"74","author":"D Schultz","year":"2018","unstructured":"Schultz, D., Jain, B.: Nonsmooth analysis and subgradient methods for averaging in dynamic time warping spaces. Pattern Recogn. 74, 340\u2013358 (2018)","journal-title":"Pattern Recogn."},{"issue":"1","key":"12_CR34","doi-asserted-by":"publisher","first-page":"247","DOI":"10.2140\/pjm.1972.41.247","volume":"41","author":"S Shelah","year":"1972","unstructured":"Shelah, S.: A combinatorial problem; stability and order for models and theories in infinitary languages. Pac. J. Math. 41(1), 247\u2013261 (1972)","journal-title":"Pac. J. Math."},{"key":"12_CR35","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V Vapnik","year":"1971","unstructured":"Vapnik, V., Chervonenkis, A.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl 16, 264\u2013280 (1971)","journal-title":"Theory Probab. Appl"},{"key":"12_CR36","series-title":"Cambridge Mathematical Library","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511608759","volume-title":"A Course of Modern Analysis","author":"ET Whittaker","year":"1996","unstructured":"Whittaker, E.T., Watson, G.N.: A Course of Modern Analysis. Cambridge Mathematical Library, 4th edn. Cambridge University Press, Cambridge (1996)","edition":"4"},{"key":"12_CR37","doi-asserted-by":"crossref","unstructured":"Zhu, Y., Shasha, D.E.: Warping indexes with envelope transforms for query by humming. In: Halevy, A.Y., Ives, Z.G., Doan, A. (eds.) Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, California, USA, 9\u201312 June 2003, pp. 181\u2013192. ACM (2003)","DOI":"10.1145\/872757.872780"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-18367-6_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,6]],"date-time":"2024-10-06T07:29:35Z","timestamp":1728199775000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-18367-6_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031183669","9783031183676"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-18367-6_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"21 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Potsdam","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 September 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 September 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo2022.eu\/waoa\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"57% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}