{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:43:58Z","timestamp":1758267838464,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030835071"},{"type":"electronic","value":"9783030835088"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"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":[[2021]]},"DOI":"10.1007\/978-3-030-83508-8_23","type":"book-chapter","created":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T13:05:06Z","timestamp":1627650306000},"page":"315-328","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["ANN for Time Series Under the Fr\u00e9chet Distance"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1943-2589","authenticated-orcid":false,"given":"Anne","family":"Driemel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5079-5003","authenticated-orcid":false,"given":"Ioannis","family":"Psarros","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,31]]},"reference":[{"key":"23_CR1","doi-asserted-by":"publisher","unstructured":"Afshani, P., Driemel, A.: On the complexity of range searching among curves. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pp. 898\u2013917 (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.58","DOI":"10.1137\/1.9781611975031.58"},{"key":"23_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/978-3-030-24766-9_3","volume-title":"Algorithms and Data Structures","author":"B Aronov","year":"2019","unstructured":"Aronov, B., Filtser, O., Horton, M., Katz, M.J., Sheikhan, K.: Efficient nearest-neighbor query and clustering of planar curves. In: Friggstad, Z., Sack, J.-R., Salavatipour, M.R. (eds.) WADS 2019. LNCS, vol. 11646, pp. 28\u201342. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-24766-9_3"},{"key":"23_CR3","doi-asserted-by":"publisher","unstructured":"de Berg, M., Gudmundsson, J., Mehrabi, A.D.: A dynamic data structure for approximate proximity queries in trajectory data. In: Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL 2017 (2017). https:\/\/doi.org\/10.1145\/3139958.3140023","DOI":"10.1145\/3139958.3140023"},{"key":"23_CR4","doi-asserted-by":"publisher","unstructured":"Beygelzimer, A., Kakade, S.M., Langford, J.: Cover trees for nearest neighbor. In: Proceedings of the 23rd International Conference (ICML) on Machine Learning, pp. 97\u2013104 (2006). https:\/\/doi.org\/10.1145\/1143844.1143857","DOI":"10.1145\/1143844.1143857"},{"issue":"2","key":"23_CR5","doi-asserted-by":"publisher","first-page":"46","DOI":"10.20382\/jocg.v7i2a4","volume":"7","author":"K Bringmann","year":"2016","unstructured":"Bringmann, K., Mulzer, W.: Approximability of the discrete Fr\u00e9chet distance. JoCG 7(2), 46\u201376 (2016). https:\/\/doi.org\/10.20382\/jocg.v7i2a4","journal-title":"JoCG"},{"issue":"6","key":"23_CR6","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1016\/j.comgeo.2012.11.006","volume":"46","author":"M De Berg","year":"2013","unstructured":"De Berg, M., Cook, A.F., Gudmundsson, J.: Fast Fr\u00e9chet queries. Comput. Geom. 46(6), 747\u2013755 (2013)","journal-title":"Comput. Geom."},{"key":"23_CR7","doi-asserted-by":"publisher","unstructured":"Driemel, A., Krivosija, A., Sohler, C.: Clustering time series under the Fr\u00e9chet distance. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 766\u2013785 (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch55","DOI":"10.1137\/1.9781611974331.ch55"},{"key":"23_CR8","unstructured":"Driemel, A., Phillips, J.M., Psarros, I.: The VC dimension of metric balls under Fr\u00e9chet and Hausdorff distances. In: Proceedings of the 35th International Symposium on Computational Geometry, pp. 28:2\u201328:16 (2019)"},{"key":"23_CR9","unstructured":"Driemel, A., Psarros, I.: (2+$$\\epsilon $$)-ANN for time series under the Fr\u00e9chet distance. CoRR abs\/2008.09406 (2020). https:\/\/arxiv.org\/abs\/2008.09406"},{"key":"23_CR10","unstructured":"Driemel, A., Silvestri, F.: Locally-sensitive hashing of curves. In: Proceedings of 33rd International Symposium on Computational Geometry, pp. 37:1\u201337:16 (2017)"},{"key":"23_CR11","unstructured":"Emiris, I.Z., Psarros, I.: Products of Euclidean metrics and applications to proximity questions among curves. In: Proceedings of 34th International Symposium on Computational Geometry (SoCG), LIPIcs, vol. 99, pp. 37:1\u201337:13 (2018)"},{"key":"23_CR12","doi-asserted-by":"publisher","unstructured":"Farach-Colton, M., Indyk, P.: Approximate nearest neighbor algorithms for Hausdorff metrics via embeddings. In: 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, New York, NY, USA, 17\u201318 October 1999, pp. 171\u2013180 (1999). https:\/\/doi.org\/10.1109\/SFFCS.1999.814589","DOI":"10.1109\/SFFCS.1999.814589"},{"key":"23_CR13","doi-asserted-by":"publisher","unstructured":"Filtser, A., Filtser, O., Katz, M.J.: Approximate nearest neighbor for curves - simple, efficient, and deterministic. In: 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, pp. 48:1\u201348:19 (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.48","DOI":"10.4230\/LIPIcs.ICALP.2020.48"},{"issue":"3","key":"23_CR14","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"ML Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with $$O(1)$$ worst case access time. J. ACM 31(3), 538\u2013544 (1984)","journal-title":"J. ACM"},{"key":"23_CR15","doi-asserted-by":"crossref","unstructured":"Gudmundsson, J., Horton, M., Pfeifer, J., Seybold, M.P.: A practical index structure supporting Fr\u00e9chet proximity queries among trajectories (2020)","DOI":"10.1145\/3460121"},{"issue":"6","key":"23_CR16","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1016\/j.comgeo.2015.02.003","volume":"48","author":"J Gudmundsson","year":"2015","unstructured":"Gudmundsson, J., Smid, M.: Fast algorithms for approximate Fr\u00e9chet matching queries in geometric trees. Comput. Geom. 48(6), 479\u2013494 (2015). https:\/\/doi.org\/10.1016\/j.comgeo.2015.02.003","journal-title":"Comput. Geom."},{"issue":"1","key":"23_CR17","doi-asserted-by":"publisher","first-page":"321","DOI":"10.4086\/toc.2012.v008a014","volume":"8","author":"S Har-Peled","year":"2012","unstructured":"Har-Peled, S., Indyk, P., Motwani, R.: Approximate nearest neighbor: towards removing the curse of dimensionality. Theory Comput. 8(1), 321\u2013350 (2012). https:\/\/doi.org\/10.4086\/toc.2012.v008a014","journal-title":"Theory Comput."},{"issue":"5","key":"23_CR18","doi-asserted-by":"publisher","first-page":"1148","DOI":"10.1137\/S0097539704446281","volume":"35","author":"S Har-Peled","year":"2006","unstructured":"Har-Peled, S., Mendel, M.: Fast construction of nets in low-dimensional metrics and their applications. SIAM J. Comput. 35(5), 1148\u20131184 (2006). https:\/\/doi.org\/10.1137\/S0097539704446281","journal-title":"SIAM J. Comput."},{"key":"23_CR19","doi-asserted-by":"publisher","unstructured":"Indyk, P.: On approximate nearest neighbors in non-Euclidean spaces. In: 39th Annual Symposium on Foundations of Computer Science, FOCS 1998, pp. 148\u2013155 (1998). https:\/\/doi.org\/10.1109\/SFCS.1998.743438","DOI":"10.1109\/SFCS.1998.743438"},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Approximate nearest neighbor algorithms for Fr\u00e9chet distance via product metrics. In: Symposium on Computational Geometry, pp. 102\u2013106 (2002)","DOI":"10.1145\/513400.513414"},{"key":"23_CR21","unstructured":"Krauthgamer, R., Lee, J.R.: Navigating nets: simple algorithms for proximity search. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, pp. 798\u2013807 (2004). http:\/\/dl.acm.org\/citation.cfm?id=982792.982913"},{"key":"23_CR22","first-page":"12807","volume":"2019","author":"S Meintrup","year":"2019","unstructured":"Meintrup, S., Munteanu, A., Rohde, D.: Random projections and sampling algorithms for clustering of high-dimensional polygonal curves. NeurIPS 2019, 12807\u201312817 (2019)","journal-title":"NeurIPS"},{"key":"23_CR23","doi-asserted-by":"publisher","unstructured":"Miltersen, P.B.: Lower bounds for union-split-find related problems on random access machines. In: Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, STOC 1994, pp. 625\u2013634. ACM (1994). https:\/\/doi.org\/10.1145\/195058.195415","DOI":"10.1145\/195058.195415"},{"key":"23_CR24","unstructured":"Mirzanezhad, M.: On the approximate nearest neighbor queries among curves under the Fr\u00e9chet distance. CoRR abs\/2004.08444 (2020). https:\/\/arxiv.org\/abs\/2004.08444"},{"issue":"1","key":"23_CR25","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/3231541.3231549","volume":"10","author":"M Werner","year":"2018","unstructured":"Werner, M., Oliver, D.: ACM SIGSPATIAL GIS Cup 2017: range queries under Fr\u00e9chet distance. SIGSPATIAL Spec. 10(1), 24\u201327 (2018). https:\/\/doi.org\/10.1145\/3231541.3231549","journal-title":"SIGSPATIAL Spec."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-83508-8_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,18]],"date-time":"2022-02-18T11:27:56Z","timestamp":1645183676000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-83508-8_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030835071","9783030835088"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-83508-8_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"31 July 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Workshop on Algorithms and Data Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 August 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 August 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/projects.cs.dal.ca\/wads2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-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":"123","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":"47","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":"38% - 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.1","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":"13","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)"}}]}}