اندازه¬گیری میزان تشابه مسیرهای جهت¬دار بر روی داده¬های هندسی
محورهای موضوعی :
محمد فرشی
1
(استادیار)
زینب سعیدی
2
(دانشجو)
کلید واژه: ساختمان داده, فاصله فرشه, فاصله هاسدورف, تشابه, مسیر جهت‌دار ,
چکیده مقاله :
در این مقاله به بررسی مسئله تشابه زیر در حوزه فاصله فرشه می پردازیم. یک مسیر جهت‌دار به عنوان ورودی و یک پاره‌خط افقی که در لحظه پرس‌و‌جو توسط کاربر ارائه می‌شود، داده شده اند، هدف پیش‌پردازش و ذخیره مسیر جهت‌دار در یک ساختمان داده است به طوری که با توجه به اطلاعات ذخیره شده در ساختمان داده بتوان زیرمسیری از مسیر جهت‌دار را گزارش کرد که فاصله فرشه میان زیرمسیر گزارش‌شده و پاره‌خط افقی بین تمام زیرمسیرهای ممکن مینیمم باشد. تا آنجایی که ما اطلاع داریم هیچ‌گونه نتیجه تئوری برای این مسئله گزارش نشده است. در این مقاله اولین الگوریتم ابتکاری برای مسئله ارائه شده است و به دلیل عدم ارائه الگوریتمی برای حل این مسئله در گذشته، صرفاً کیفیت الگوریتم ارائه شده بر روی چند پایگاه داده بررسی می‌گردد.
We consider the following similarity problem concerning the Fréchet distance. A directed path π is given as input and a horizontal segment Q is defined at query time by the user. Our goal is to preprocess and save the directed path π into a data structure such that based on the information saved in the data structure, one sub-path of the directed path can be reported which Fréchet distance between the sub-path and the horizontal query segment Q is minimum between all possible sub-paths. To the best of our knowledge, no theoretical results have been reported for this problem. In this paper, the first heuristic algorithm is proposed. We only experimentally show the quality of the algorithm in several datasets due to no existing algorithm.
Felix Hausdorff. Grundzuge der mengenlehre, 1949
[2] Helmut Alt. The computational geometry of comparing shapes. In Efficient Algorithms, volume 5760 of Lecture Notes in Computer Science, pages 235–248, 2009.
[3] Paolo Cignoni, Claudio Rocchini, and Roberto Scopigno. Metro: measuring error on simplified surfaces. In Computer graphics forum, pages 167–174, 1998
[4] Maurice Fréchet. Les ensembles abstraits et le calcul fonctionnel. Rendiconti del Circolo Matematico di Palermo, pages 1-26, 1910.
[5] Helmut Alt and Michael Godau. Measuring the resemblance of polygonal curves. In Proceedings of the eighth annual symposium on Computational geometry, pages 102–109, 1992.
[6] Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry & Applications, pages75-91, 1995.
[7] E Sriraghavendra, K Karthik, and Chiranjib Bhattacharyya. Fréchet distance based approach for searching online handwritten documents. In Ninth International Conference on Document Analysis and Recognition, pages 461-465, 2007.
[8] Mark de Berg, Atlas F Cook, and Joachim Gudmundsson. Fast Fréchet queries. Computational Geometry, pages 747–755, 2013
[9] Joachim Gudmundsson and Michiel Smid. Fréchet queries in geometric trees. In European Symposium on Algorithms, pages 565–576. Springer, 2013
[10] Anne Driemel and Sariel Har-Peled. Jaywalking your dog: computing the Fréchet distance with shortcuts. SIAM Journal on Computing, pages 1830-1866, 2013
[11] Mark de Berg and Ali D Mehrabi. Straight-path queries in trajectory data. Journal of Discrete Algorithms, pages 27–38, 2016.
[12] Mark de Berg, Ali D Mehrabi, and Tim Ophelders. Data structures for Fréchet queries in trajectory data. In Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017), pages 214-219, 2017.
[13] Maike Buchin, Ivor van der Hoog, Tim Ophelders, Rodrigo I Silveira, Lena Schlipf, and Frank Staals. Improved space bounds for Fréchet distance queries. In Proceeding of the 36th European Workshop on Computational Geometry, pages 1-7, 2020.
[14] Joachim Gudmundsson, Majid Mirzanezhad, Ali Mohades, and Carola Wenk. International Journal of Computational Geometry & Applications, pages 161-187, 2019
[15] Mark de Berg, Joachim Gudmundsson, and Ali D Mehrabi. 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, pages 1-4,2017
[16] Julian Baldus and Karl Bringmann. A fast implementation of near neighbors queries for Fréchet distance (GIS cup). In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 1-4, 2017.
[17] Matteo Ceccarello, Anne Driemel, and Francesco Silvestri. Fresh: Fréchet similarity with hashing. In Workshop on Algorithms and Data Structures, pages 254–268, 2019.
[18] Fabian Dütsch and Jan Vahrenhold. A filter-and-refinement-algorithm for range queries based on the Fréchet distance (gis cup). In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 1–4, 2017
[19] Yanping Chen, Eamonn Keogh, Bing Hu, Nurjahan Begum, Anthony Bagnall, Abdullah Mueen, and Gustavo Batista. The UCR time series classification archive, July 2015.http://www.cs.ucr.edu/eamonn/time_series_data.
[20] Joachim Gudmundsson and Michiel Smid. Fast algorithms for approximate Fréchet matching queries in geometric trees. Computational Geometry, pages 479-494, 2015
[21] Bahram Sadeghi Bigham, and Samaneh Mazaheri. Survey on Metrics for Shape Matching Based on Similarity, Scaling and Spatial Distance. In The 7th International Conference on Contemporary Issues in Data Science, pages 13-23, 2017