{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T19:18:49Z","timestamp":1758309529301,"version":"3.44.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,12,11]],"date-time":"2024-12-11T00:00:00Z","timestamp":1733875200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,12,11]],"date-time":"2024-12-11T00:00:00Z","timestamp":1733875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"HORIZON EUROPE Innovation and Research","award":["95734"],"award-info":[{"award-number":["95734"]}]},{"DOI":"10.13039\/501100014603","name":"Hausdorff Center for Mathematics","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100014603","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2025,9]]},"DOI":"10.1007\/s00454-024-00710-5","type":"journal-article","created":{"date-parts":[[2024,12,11]],"date-time":"2024-12-11T17:08:35Z","timestamp":1733936915000},"page":"374-398","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Random Projections for Curves in High Dimensions"],"prefix":"10.1007","volume":"74","author":[{"given":"Ioannis","family":"Psarros","sequence":"first","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":[[2024,12,11]]},"reference":[{"issue":"11","key":"710_CR1","doi-asserted-by":"publisher","first-page":"1857","DOI":"10.1016\/j.patcog.2005.01.025","volume":"38","author":"TW Liao","year":"2005","unstructured":"Liao, T.W.: Clustering of time series data\u2013a survey. Pattern Recogn. 38(11), 1857\u20131874 (2005)","journal-title":"Pattern Recogn."},{"issue":"1","key":"710_CR2","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1002\/rsa.10073","volume":"22","author":"S Dasgupta","year":"2003","unstructured":"Dasgupta, S., Gupta, A.: An elementary proof of a theorem of Johnson and Lindenstrauss. Random Struct. Algorithms 22(1), 60\u201365 (2003)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"710_CR3","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0095-8956(88)90043-3","volume":"44","author":"P Frankl","year":"1988","unstructured":"Frankl, P., Maehara, H.: The Johnson\u2013Lindenstrauss lemma and the sphericity of some graphs. J. Combin. Theory Ser. B 44(3), 355\u2013362 (1988)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"4","key":"710_CR4","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/S0022-0000(03)00025-4","volume":"66","author":"D Achlioptas","year":"2003","unstructured":"Achlioptas, D.: Database-friendly random projections: Johnson\u2013Lindenstrauss with binary coins. J. Comput. Syst. Sci. 66(4), 671\u2013687 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"710_CR5","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N Linial","year":"1995","unstructured":"Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215\u2013245 (1995)","journal-title":"Combinatorica"},{"issue":"1","key":"710_CR6","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/2559902","volume":"61","author":"DM Kane","year":"2014","unstructured":"Kane, D.M., Nelson, J.: Sparser Johnson\u2013Lindenstrauss transforms. J. ACM 61(1), 4\u20131423 (2014)","journal-title":"J. ACM"},{"issue":"1","key":"710_CR7","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"WB Johnson","year":"1984","unstructured":"Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. Contemp. Math. 26(1), 189\u2013206 (1984)","journal-title":"Contemp. Math."},{"issue":"1\u20133","key":"710_CR8","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0012-365X(03)00227-9","volume":"273","author":"N Alon","year":"2003","unstructured":"Alon, N.: Problems and results in extremal combinatorics-I. Discret. Math. 273(1\u20133), 31\u201353 (2003)","journal-title":"Discret. Math."},{"key":"710_CR9","series-title":"LIPIcs","first-page":"82","volume-title":"43rd International Colloquium on Automata, Languages, and Programming, ICALP","author":"KG Larsen","year":"2016","unstructured":"Larsen, K.G., Nelson, J.: The Johnson\u2013Lindenstrauss lemma is optimal for linear dimensionality reduction. In: Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., Sangiorgi, D. (eds.) 43rd International Colloquium on Automata, Languages, and Programming, ICALP. LIPIcs, vol. 55, pp. 82\u201318211. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Rome (2016)"},{"key":"710_CR10","series-title":"FOCS","first-page":"633","volume-title":"58th IEEE Annual Symposium on Foundations of Computer Science","author":"KG Larsen","year":"2017","unstructured":"Larsen, K.G., Nelson, J.: Optimality of the Johnson\u2013Lindenstrauss lemma. In: Umans, C. (ed.) 58th IEEE Annual Symposium on Foundations of Computer Science. FOCS, pp. 633\u2013638. IEEE Computer Society, Berkeley (2017)"},{"key":"710_CR11","first-page":"604","volume-title":"Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing","author":"P Indyk","year":"1998","unstructured":"Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: Vitter, J.S. (ed.) Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, pp. 604\u2013613. ACM, Dallas (1998)"},{"issue":"1","key":"710_CR12","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1137\/060673096","volume":"39","author":"N Ailon","year":"2009","unstructured":"Ailon, N., Chazelle, B.: The fast Johnson\u2013Lindenstrauss transform and approximate nearest neighbors. SIAM J. Comput. 39(1), 302\u2013322 (2009)","journal-title":"SIAM J. Comput."},{"key":"710_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/3-540-45726-7_19","volume-title":"Randomization and Approximation Techniques, 6th International Workshop, RANDOM","author":"A Magen","year":"2002","unstructured":"Magen, A.: Dimensionality reductions that preserve volumes and distance to affine spaces, and their algorithmic applications. In: Rolim, J.D.P., Vadhan, S.P. (eds.) Randomization and Approximation Techniques, 6th International Workshop, RANDOM. Lecture Notes in Computer Science, vol. 2483, pp. 239\u2013253. Springer, Cambridge (2002)"},{"issue":"1","key":"710_CR14","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s00454-007-1329-4","volume":"38","author":"A Magen","year":"2007","unstructured":"Magen, A.: Dimensionality reductions in l$$ _{\\text{2 }}$$ that preserve volumes and distance to affine spaces. Discrete Comput. Geom. 38(1), 139\u2013153 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"710_CR15","doi-asserted-by":"crossref","unstructured":"Sheehy, D.R.: The persistent homology of distance functions under random projection. In: 30th Annual Symposium on Computational Geometry (SoCG), p. 328 (2014)","DOI":"10.1145\/2582112.2582126"},{"issue":"2","key":"710_CR16","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1137\/110830046","volume":"42","author":"PK Agarwal","year":"2013","unstructured":"Agarwal, P.K., Har-Peled, S., Yu, H.: Embeddings of surfaces, curves, and moving points in Euclidean space. SIAM J. Comput. 42(2), 442\u2013458 (2013)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"710_CR17","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s10208-007-9011-z","volume":"9","author":"RG Baraniuk","year":"2009","unstructured":"Baraniuk, R.G., Wakin, M.B.: Random projections of smooth manifolds. Found. Comput. Math. 9(1), 51\u201377 (2009)","journal-title":"Found. Comput. Math."},{"key":"710_CR18","doi-asserted-by":"crossref","unstructured":"Driemel, A., Krivosija, A.: Probabilistic embeddings of the Fr\u00e9chet distance. In: Proceedings of the 16th International Workshop on Approximation and Online Algorithms (WAOA), pp. 218\u2013237 (2018)","DOI":"10.1007\/978-3-030-04693-4_14"},{"issue":"1","key":"710_CR19","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/s00454-012-9402-z","volume":"48","author":"A Driemel","year":"2012","unstructured":"Driemel, A., Har-Peled, S., Wenk, C.: Approximating the Fr\u00e9chet distance for realistic curves in near linear time. Discrete Comput. Geom. 48(1), 94\u2013127 (2012)","journal-title":"Discrete Comput. Geom."},{"key":"710_CR20","series-title":"LIPIcs","first-page":"6","volume-title":"32nd International Symposium on Computational Geometry, SoCG","author":"PK Agarwal","year":"2016","unstructured":"Agarwal, P.K., Fox, K., Pan, J., Ying, R.: Approximating dynamic time warping and edit distance for a pair of point sequences. In: Fekete, S.P., Lubiw, A. (eds.) 32nd International Symposium on Computational Geometry, SoCG. LIPIcs, vol. 51, pp. 6\u20131616. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Boston (2016)"},{"key":"710_CR21","doi-asserted-by":"crossref","unstructured":"Bringmann, K.: Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 661\u2013670. IEEE Computer Society, Philadelphia (2014)","DOI":"10.1109\/FOCS.2014.76"},{"issue":"5","key":"710_CR22","doi-asserted-by":"publisher","first-page":"1830","DOI":"10.1137\/120865112","volume":"42","author":"A Driemel","year":"2013","unstructured":"Driemel, A., Har-Peled, S.: Jaywalking your dog: computing the Fr\u00e9chet distance with shortcuts. SIAM J. Comput. 42(5), 1830\u20131866 (2013)","journal-title":"SIAM J. Comput."},{"key":"710_CR23","unstructured":"Meintrup, S., Munteanu, A., Rohde, D.: Random projections and sampling algorithms for clustering of high-dimensional polygonal curves. In: Wallach, H.M., Larochelle, H., Beygelzimer, A., d\u2019Alch\u00e9-Buc, F., Fox, E.B., Garnett, R. (eds.) Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems, NeurIPS, 8\u201314 December 2019, pp. 12807\u201312817. Canada, Vancouver (2019)"},{"key":"710_CR24","first-page":"898","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA","author":"P Afshani","year":"2018","unstructured":"Afshani, P., Driemel, A.: On the complexity of range searching among curves. In: Czumaj, A. (ed.) Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 898\u2013917. SIAM, New Orleans (2018)"},{"issue":"1\u20132","key":"710_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/0400000060","volume":"10","author":"DP Woodruff","year":"2014","unstructured":"Woodruff, D.P.: Sketching as a tool for numerical linear algebra. Found. Trends Theor. Comput. Sci. 10(1\u20132), 1\u2013157 (2014). https:\/\/doi.org\/10.1561\/0400000060","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"710_CR26","doi-asserted-by":"publisher","unstructured":"Cheng, S., Huang, H.: Solving fr\u00e9chet distance problems by algebraic geometric methods. In: Woodruff, D.P. (ed.) Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, 7\u201310 January 2024, pp. 4502\u20134513. SIAM, New Orleans (2024). https:\/\/doi.org\/10.1137\/1.9781611977912.158","DOI":"10.1137\/1.9781611977912.158"},{"issue":"4","key":"710_CR27","doi-asserted-by":"publisher","first-page":"1351","DOI":"10.1007\/s00454-021-00318-z","volume":"66","author":"A Driemel","year":"2021","unstructured":"Driemel, A., Nusser, A., Phillips, J.M., Psarros, I.: The VC dimension of metric balls under Fr\u00e9chet and Hausdorff distances. Discrete Comput. Geom. 66(4), 1351\u20131381 (2021)","journal-title":"Discrete Comput. Geom."},{"key":"710_CR28","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 ACM-SIAM Symposium on Discrete Algorithms, SODA, Virtual Conference, pp. 2697\u20132717. SIAM (2021)","DOI":"10.1137\/1.9781611976465.160"},{"key":"710_CR29","unstructured":"Filtser, A., Filtser, O., Katz, M.J.: Approximate nearest neighbor for curves\u2014simple, efficient, and deterministic. In: Czumaj, A., Dawar, A., Merelli, E. (eds.) 47th International Colloquium on Automata, Languages, and Programming, ICALP (Virtual Conference). LIPIcs, vol. 168, pp. 48\u201314819. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Saarbr\u00fccken (2020)"},{"key":"710_CR30","doi-asserted-by":"crossref","unstructured":"Buchin, K., Driemel, A., Gudmundsson, J., Horton, M., Kostitsyna, I., L\u00f6ffler, M., Struijs, M.: Approximating (k, $$\\ell $$)-center clustering for curves. In: Chan, T.M. (ed.) Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 2922\u20132938. SIAM, San Diego (2019)","DOI":"10.1137\/1.9781611975482.181"},{"key":"710_CR31","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1142\/S0218195995000064","volume":"5","author":"H Alt","year":"1995","unstructured":"Alt, H., Godau, M.: Computing the Fr\u00e9chet distance between two polygonal curves. Int. J. Comput. Geom. Appl. 5, 75\u201391 (1995)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"710_CR32","doi-asserted-by":"crossref","unstructured":"Arriaga, R.I., Vempala, S.S.: An algorithmic theory of learning: robust concepts and random projection. In: 40th Annual Symposium on Foundations of Computer Science. FOCS, pp. 616\u2013623. IEEE Computer Society, New York (1999)","DOI":"10.1109\/SFFCS.1999.814637"},{"issue":"2","key":"710_CR33","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1006\/jcss.2000.1711","volume":"61","author":"CH Papadimitriou","year":"2000","unstructured":"Papadimitriou, C.H., Raghavan, P., Tamaki, H., Vempala, S.S.: Latent semantic indexing: a probabilistic analysis. J. Comput. Syst. Sci. 61(2), 217\u2013235 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"710_CR34","doi-asserted-by":"crossref","unstructured":"Sarl\u00f3s, T.: Improved approximation algorithms for large matrices via random projections. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 143\u2013152 (2006)","DOI":"10.1109\/FOCS.2006.37"},{"key":"710_CR35","doi-asserted-by":"crossref","unstructured":"Driemel, A., Krivosija, A., Sohler, C.: Clustering time series under the Fr\u00e9chet distance. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 766\u2013785 (2016)","DOI":"10.1137\/1.9781611974331.ch55"},{"key":"710_CR36","unstructured":"Buchin, K., Driemel, A., Struijs, M.: On the hardness of computing an average curve. In: Albers, S. (ed.) 17th Scandinavian Symposium and Workshops on Algorithm Theory. LIPIcs, vol. 162, pp. 19\u201311919. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, T\u00f3rshavn, Faroe Islands (2020)"},{"key":"710_CR37","doi-asserted-by":"crossref","unstructured":"Buchin, K., Driemel, A., L\u2019Isle, N., Nusser, A.: klcluster: Center-based clustering of trajectories. In: Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 496\u2013499 (2019)","DOI":"10.1145\/3347146.3359111"},{"key":"710_CR38","first-page":"71","volume":"6","author":"H Imai","year":"1988","unstructured":"Imai, H., Iri, M.: Polygonal approximations of a curve\u2014formulations and algorithms. Mach. Intell. Pattern Recogn. 6, 71\u201386 (1988)","journal-title":"Mach. Intell. Pattern Recogn."},{"key":"710_CR39","doi-asserted-by":"crossref","unstructured":"Narayanan, S., Nelson, J.: Optimal terminal dimensionality reduction in Euclidean space. In: Charikar, M., Cohen, E. (eds.) Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 1064\u20131069. ACM, Phoenix (2019)","DOI":"10.1145\/3313276.3316307"},{"key":"710_CR40","doi-asserted-by":"crossref","unstructured":"Makarychev, K., Makarychev, Y., Razenshteyn, I.P.: Performance of Johnson\u2013Lindenstrauss transform for k-means and k-medians clustering. In: Charikar, M., Cohen, E. (eds.) Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 1027\u20131038. ACM, Phoenix (2019)","DOI":"10.1145\/3313276.3316350"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00710-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-024-00710-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00710-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T15:04:34Z","timestamp":1758294274000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-024-00710-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,11]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["710"],"URL":"https:\/\/doi.org\/10.1007\/s00454-024-00710-5","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2024,12,11]]},"assertion":[{"value":"28 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 October 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 December 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}