• صفحه اصلی
  • اندازه¬گیری میزان تشابه مسیرهای جهت¬دار بر روی داده¬های هندسی

اشتراک گذاری

آدرس مقاله


کد مقاله : A-10-2441-1 بازدید : 6372 صفحه: 145 - 158

20.1001.1.27170411.1399.12.45.12.2

نوع مقاله: پژوهشی

اندازه¬گیری میزان تشابه مسیرهای جهت¬دار بر روی داده¬های هندسی

محورهای موضوعی :

محمد فرشی 1 * , زینب سعیدی 2

1 - استادیار
2 - دانشجو

تاریخ دریافت : 1400/03/25 تاریخ پذیرش : 1400/03/25 تاریخ انتشار : 1400/03/25

کلید واژه: ساختمان داده, فاصله فرشه, فاصله هاسدورف, تشابه, مسیر جهت‌دار ,

چکیده مقاله :

در این مقاله به بررسی مسئله تشابه زیر در حوزه فاصله فرشه می پردازیم. یک مسیر جهت‌دار به عنوان ورودی و یک پاره‌خط افقی که در لحظه پرس‌و‌جو توسط کاربر ارائه می‌شود، داده شده اند، هدف پیش‌پردازش و ذخیره مسیر جهت‌دار در یک ساختمان داده است به طوری که با توجه به اطلاعات ذخیره شده در ساختمان داده بتوان زیرمسیری از مسیر جهت‌دار را گزارش کرد که فاصله فرشه میان زیرمسیر گزارش‌شده و پاره‌خط افقی بین تمام زیرمسیرهای ممکن مینیمم باشد. تا آنجایی که ما اطلاع داریم هیچ‌گونه نتیجه تئوری برای این مسئله گزارش نشده است. در این مقاله اولین الگوریتم ابتکاری برای مسئله ارائه شده است و به دلیل عدم ارائه الگوریتمی برای حل این مسئله در گذشته، صرفاً کیفیت الگوریتم ارائه شده بر روی چند پایگاه داده بررسی می‌گردد.

چکیده انگلیسی:

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

























متن کامل:
الگوي تهيه مقالات

 

 

دو فصلنامه علمي

فناوري اطلاعات و ارتباطات ایران

سال دوازدهم، شماره‌هاي 45 و 46، پاییز و زمستان 1399

صص:  145-158   

E:\E Drive\logo\iicta Logo0.JPG 

اندازه­گیری میزان تشابه مسیرهای جهت­دار بر روی داده­های هندسی

زینب سعیدی*            محمد فرشی**

 * دانشجوی دکتری، گروه علوم کامپیوتر، دانشکده علوم ریاضی، دانشگاه یزد

                                                 ** استادیار، گروه علوم کامپیوتر، دانشکده علوم ریاضی، دانشگاه یزد

تاریخ دریافت: 100/06/1399                         تاریخ پذیرش: 20/10/1399

نوع مقاله: پژوهشی

 

 

 

چكیده

 در این مقاله به بررسی مسئله تشابه زیر در حوزه فاصله فرشه می­پردازیم. یک مسیر جهت‌دار img0 به عنوان ورودی و یک پاره‌خط افقی img0 که در لحظه پرس‌و‌جو توسط کاربر ارائه می‌شود، داده شده­اند، هدف پیش‌پردازش و ذخیره مسیر جهت‌دار img0 در یک ساختمان داده است به­طوری­که با توجه به اطلاعات ذخیره شده در ساختمان داده بتوان زیرمسیری از مسیر جهت‌دار را گزارش کرد که فاصله فرشه میان زیرمسیر گزارش‌شده و پاره‌خط افقی img0 بین تمام زیرمسیرهای ممکن مینیمم باشد. تا آنجایی که ما اطلاع داریم هیچ‌گونه نتیجه تئوری برای این مسئله گزارش نشده است. در این مقاله اولین الگوریتم ابتکاری برای مسئله ارائه شده است و به دلیل عدم ارائه الگوریتمی برای حل این مسئله در گذشته، صرفاً کیفیت الگوریتم ارائه شده بر روی چند پایگاه داده بررسی می‌گردد.

 

واژگان کلیدی: ساختمان داده، فاصله فرشه، فاصله هاسدورف، تشابه، مسیر جهت‌دار  

 

 

 

 

1. مقدمه

توصیف عددی دور بودن دو شی از هم فاصله نامیده می­شود. در ریاضیات، تابع فاصله یا متر، تعمیمی از مفهوم فاصله فیزیکی است. متر، یک راه برای توصیف مفهوم نزدیک یا دور بودن عناصر یک فضا از هم است. اندازه­گیری همسانی بین دو شی هندسی، یک مسئله اساسی در زمینه­های بسیاری از علوم و مهندسی می­باشد. برای مهیا کردن چنین مقایسه­هایی، یک معیار خوب برای فرمول­بندی میزان تشابه یا همسانی لازم می­باشد.

 

 

نویسنده مسئول: محمد فرشی mfarshi@yazd.ac.ir

فاصله هاسدورف یک ابزار برای اندازه­گیری میزان تشابه بین دو منحنی است. این فاصله برای اولین بار توسط فلیکس هاسدورف1 در سال 1914 میلادی در کتابش معرفی شد [1]. در سال 2009، آلت2  نشان داد که فاصله هاسدورف میان دو چندضلعی با img0 و img0 رأس در زمان img0 قابل محاسبه است. یکی از کاربردهای فاصله هاسدورف در گرافیک کامپیوتری برای اندازه‌گیری تفاوت بین دو دید مختلف از یک شی می‌باشد [3] [2]. فاصله هاسدورف به صورت غیر رسمی برابر با ماکزیمم فاصله بین دو نقطه از دو منحنی است زمانی که هر نقطه از یک منحنی به نزدیک‌ترین نقطه­اش در منحنی دیگر نگاشت گردد. یکی از مزیت­های فاصله هاسدورف این است که به آسانی قابل توصیف است. فاصله هاسدورف جهت‌دار از منحنی img0  به منحنی img0 به صورت زیر تعریف می­شود:

(1)

img0 

فاصله هاسدورف بین img0 و img0 نیز به صورت زیر تعریف می­شود:

(2)

img0 

فاصله فرشه توسط موریس رنه فرشه3 در سال 1906 میلادی معرفی شد [4[. یک مطالعه پایه روی ویژگی­های محاسباتی فاصله فرشه توسط آلت و گوداو4 در سال 1992 انجام شد [5]. آنها الگوریتمی ارائه دادند که فاصله فرشه بین دو چندضلعی را در زمان img0 محاسبه می­کند که img0 و img0 تعداد رئوس چندضلعی­ها هستند. در سال 1995، آلت و گوداو  نشان دادند که فاصله فرشه بین دو چندضلعی در زمان img0 قابل محاسبه است و تا کنون هم نتیجه بهتری گزارش نشده است[6]. فاصله فرشه دارای کاربردهای متنوعی از جمله تشخیص گفتار، تشخیص امضا و تشخیص دست­خط  است[7[. 

فاصله فرشه به طور غیررسمی به صورت زیر تعریف می­شود. یک شخص و سگش را در نظر بگیرید به گونه­ای که سگ با یک قلاده به صاحبش وصل شده است. هر کدام از این دو روی یک مسیر جهت‌دار (منحنی) از نقطه ابتدایی آن تا انتهایش در حال حرکت می­باشند. هر دوی آنها اجازه دارند که سرعت خود را کنترل کنند اما نمی­توانند به عقب برگردند. هزینه هر پیاده‌روی برابر با حداکثر طول قلاده­ای است که شخص را به سگش وصل می­کند. پیاده­روی­های متفاوت هزینه­ی متفاوت دارند. فاصله فرشه برابر با هزینه پیاده­روی است که دارای هزینه مینیمم در بین تمام پیاده­روی­های ممکن است.

فاصله فرشه بین منحنی img0 و img0 به‌صورت زیر تعریف می­شود:

(3)

img0 

کهimg0فاصله اقلیدسی را نشان می‌دهد و img0 یک تابع پیوسته غیرنزولی است که هر نقطه img0 را به نقطه img0 در img0 نگاشت می­کند. تحت نگاشت img0، نقطه شروع img0 به نقطه شروع img0 نگاشت می­شود که مطمئن باشیم دو تا منحنی در یک جهت پیموده می­شوند. مزیت فاصله فرشه نسبت به معیارهای دیگر این است که فاصله فرشه ترتیب نقاط در امتداد منحنی­ها را رعایت می­کند.

2. مروری بر کارهای گذشته

 دسته جالبی از مسائل که در حوزه فاصله فرشه مطرح می­شود، ارائه ساختمان داده کارآمد برای مسائل پرس‌و‌جوی فرشه است. به این صورت که یک مسیر جهت­دار داده شده است. می­خواهیم با انجام یک پیش‌پردازش آن را در یک ساختمان داده ذخیره کنیم به صورتی که با توجه به اطلاعات ذخیره شده در ساختمان داده بتوانیم فاصله فرشه میان مسیر جهت­دار و هر پاره­خطی که در زمان پرس‌و‌جو داده می­شود را محاسبه کنیم و یا تعداد زیرمسیرهایی را شمارش کنیم که فاصله فرشه آنها از پاره­خطی که در زمان پرس‌و‌جو داده می­شود، کوچکتر یا مساوی مقدار آستانه مشخص شده در زمان پرس‌و‌جو باشد.

دی برگ5 و همکارانش  در سال 2013 مسئله پرس‌و‌جوی فرشه در مسیر جهت­دار را مورد بررسی قرار دادند. آنها برای ساده­تر کردن مسئله، پرس‌و‌جو را به صورت پاره­خط افقی در نظر گرفتند و تعداد زیرمسیرهایی که فاصله فرشه آنها از پاره­خط افقی داده شده حداکثر برابر img0 است را شمارش کردند[8]. ساختمان داده­ای که توسط دی برگ و همکارانش ارائه شد، این مسئله را به صورت تقریبی حل می‌کند. این ساختمان داده، علاوه بر تمام زیرمسیرهایی با فاصله img0، شامل تعدادی زیرمسیر اضافه است که فاصله فرشه آنها از پاره­خط داده شده حداکثر برابر با img0 است. آنها فرض کردند که طول پاره­خط داده شده در پرس‌و‌جو حداقل img0 است و مسئله را در دو حالت بررسی کردند. الف) حالتی که img0 از قبل مشخص است. ب) حالتی که img0 جزء پرس‌و‌جو است و از قبل مشخص نمی­باشد. آنها با طراحی یک ساختمان داده چندسطحی با زمان پیش­پردازش img0 و فضای ذخیره­سازی img0 حالت (الف) مسئله را حل کردند که img0 تعداد رئوس مسیر است و s پارامتری است که بین img0 و img0 قرار دارد. زمان پاسخ به پرس‌و‌جو img0 است. با افزایش زمان پیش‌پردازش به img0 می­توان مسئله را در حالت (ب) حل کرد. فضای ذخیره­سازی و زمان پاسخ به پرس‌و‌جو نسبت به حالت (الف) تغییری نمی‌کند.

گودموندسون6 و اسمید7  در سال 2013 مسئله پرس‌و‌جوی فرشه در درخت هندسی (درختی که بر روی یک مجموعه از نقاط در صفحه ساخته شود) را مورد بررسی قرار دادند[9[. درختimg0 و مقدار img0 را به عنوان ورودی داریم. پرس‌و‌جو img0 به صورت مسیر در نظر گرفته شده است. آنها در پی یافتن ساختمان داده­ای برای ذخیره کردن درخت img0 بودند که بتواند در زمان پرس‌و‌جو مشخص کند آیا درخت img0 شامل مسیری مانند img0 است که فاصله فرشه آن از مسیر داده شده در پرس‌و‌جو کمتر از img0 باشد. آنها مسئله را در حالتی که درخت img0 به صورت img0-بسته‌بندی (درختی که کل طول قرار گرفته از آن داخل هر دیسک حداکثر img0 برابر شعاع دیسک باشد) است و طول هر کدام از یال­های درخت و مسیر داده شده در پرس‌و‌جو از img0 است، بررسی کردند. ساختمان داده ارائه شده دارای زمان ساخت و فضای ذخیره‌سازی img0 است و برای مسیر img0 داده شده در پرس‌و‌جو با img0 رأس می­تواند در زمان img0 پاسخ آری یا نه را بدهد. اگر ساختمان داده پاسخ نه بدهد، حتماً مسیری در img0 وجود نداشته است که فاصله آن از img0 کمتر از img0 باشد. اگر پاسخ آری بدهد و img0 باشد، به این معنی است که مسیری در img0 وجود دارد که فاصله فرشه آن از img0 حداکثر برابر با

 img0 است. اگر پاسخ آری بدهد و img0 باشد، به این معنی است که مسیری در img0 وجود دارد که فاصله فرشه آن از img0 حداکثر برابر با img0 است. یعنی در حالت آری پاسخ تقریبی خواهیم داشت. آنها در سال 2015 [18] ضریب img0 را از کران بدست آمده برای حالتی که img0 است، حذف کردند و نتیجه بهتری را بدست آورند. اما برای حالت img0 کران بدست آمده جدید برابر با img0 است.

دریمل8  و هارپلد9  در سال 2013 مسئله پرس‌و‌جوی فرشه با کمک یال میان‌بر را بررسی کردند. آنها ساختمان داده­ای ارائه کردند که می­تواند دو مسئله­ای که در ادامه مطرح می­شود را حل کند[10[.

    • منحنی img0 که دارای img0 رأس است را به عنوان ورودی داریم. پرس‌و‌جو، منحنی img0 شامل img0 رأس و رئوس img0 و img0 است. هدف، ذخیره منحنی img0  در یک ساختمان داده­ است به صورتی که بتوانیم به ازای هر img0، img0 و img0 که در پرس‌و‌جو داده می­شود، فاصله فرشه میان زیر­منحنی از img0 که بین img0 و img0 قرار دارد و منحنی img0 را محاسبه کنیم. ساختمان داده ارائه شده دارای زمان ساخت img0 و فضای ذخیره‌سازی img0 است. زمان پاسخ به پرس‌و‌جو img0 است. ساختمان داده ارائه شده، فاصله فرشه تقریبی با ضریب تقریب ثابت 23 را محاسبه می­کند.

• منحنی داده شده در پرس‌و‌جو را به صورت پاره­خط افقی در نظر می­گیرد. ساختمان داده ارائه شده دارای زمان ساخت img0 و فضای ذخیره­سازی img0 است که

 img0. ساختمان داده ارائه شده در زمان img0 فاصله فرشه میان زیرمنحنی از img0 که بین img0 و img0 قرار دارد و پاره­خط افقی img0 را با ضریب تقریب img0 محاسبه می‌کند.

 دی برگ و مهرابی  در سال 2015 مسئله یافتن زیرمسیرهای مستقیم در مسیر جهت­دار را بررسی کردند. آنها دو معیار متفاوت برای مستقیم بودن ارائه کردند و با توجه به آن دو تعریف، مسئله را بررسی کردند. معیار اول، ضریب کشش و معیار دوم انحراف جهت است. با توجه به این دو معیار ساختمان داده‌های زیر طراحی شده است[11].

    • ضریب کشش: مسیر جهت‌دار img0 و مقدار img0 را به عنوان ورودی داریم. در پرس‌و‌جو دو مکان img0 و img0 که به ترتیب نشان دهنده نقطه شروع و نقطه پایان است، داده می‌شود. هدف گزارش تمام زیرمسیرهایی از img0 است به صورتی­که نقطه شروع و پایان آن به ترتیب img0 و img0 باشد و ضریب کشش آن حداکثر img0 باشد. آنها صفحه را به سلول‌های مربعی تقسیم‌بندی کردند. به عبارتی صفحه را به صورت مشبکه img0 در نظر گرفتند. ساختمان داده ارائه شده نیازمند فضای ذخیره‌سازی img0 است که در زمان مورد انتظار img0 ساخته می­شود و img0 تعداد رئوس مسیر جهت‌دار و img0 تعداد کل زیرمسیرهای جهت‌دار با شرایط ذکر شده است.

    • انحراف جهت: مسیر جهت‌دار img0 و مقدار img0 را به عنوان ورودی داریم. در پرس‌و‌جو دو مکان img0 و img0 که به ترتیب نشان دهنده نقطه شروع و نقطه پایان است، داده می‌شود. هدف گزارش تمام زیرمسیرهایی از img0 است که نقطه شروع و پایان آن‌ها به ترتیب img0 و img0 هستند و انحراف جهت آن حداکثر img0 باشد که انحراف جهت مقدار بیشینه زاویه بین هر دو پاره‌خط متوالی مسیر جهت‌دار است. آنها صفحه را به سلول‌های مربعی تقسیم‌بندی کردند. به عبارتی صفحه را به صورت مشبکه در نظر گرفتند. ساختمان داده ارائه شده نیازمند فضای ذخیره‌سازی img0 است که در زمان img0 ساخته می­شود و img0 تعداد رئوس مسیر جهت‌دار و img0 تعداد کل زیرمسیرهای جهت‌دار با شرایط ذکر شده است.

 مسئله­ی دیگری که در سال 2017 توسط دی برگ و همکارانش  مورد بررسی قرار گرفته است، محاسبه فاصله فرشه میان مسیر جهت­دار img0 و پرس‌و‌جو ورودی img0 که به صورت پاره­خط افقی فرض شده است، می­باشد[12]. هدف طراحی ساختمان داده­هایی که برای مسیر img0 بتوانند برای هر پاره­خطی که به عنوان پرس‌و‌جو داده می­شود، فاصله فرشه میان پاره­خط و مسیر جهت­دار را به صورت دقیق محاسبه کنند. آن­ها ساختمان داده­ای ارائه دادند که فاصله فرشه میان مسیر جهت­دار img0 را از هر پاره­خط داده شده در پرس‌و‌جو با زمان پیش­پردازش img0 و فضای ذخیره­سازی img0 و زمان پرس‌و‌جوی img0 محاسبه می­کند. دی برگ و همکارانش ساختمان داده دیگری طراحی کردند که فاصله فرشه میان زیرمسیری که توسط دو رأس داده شده در پرس‌و‌جو مشخص می­شود و هر پاره­خط دلخواهی که در زمان پرس‌و‌جو داده می­شود را محاسبه کند. زمان پیش­پردازش ساختمان داده ارائه شده  img0 و پیچیدگی فضای img0 است. زمان پاسخ به پرس‌و‌جو برابر با img0 است.

بوخین و همکارانش  در سال 2020 فضای ذخیره‌سازی ساختمان داده برای محاسبه فاصله فرشه میان مسیر جهت­دار img0 و پاره­خط افقی داده شده در پرس‌و‌جو را به img0 کاهش دادند[13[.

 گودموندسون و همکارانش  در سال 2017 مسئله پرس‌و‌جوی فرشه برای منحنی با طول یال‌های طویل را مورد بررسی قرار دادند. ورودی مسئله منحنی img0 شامل img0 رأس است[14]. img0 طول کوتاه‌ترین یال منحنی img0 است. در پرس‌و‌جو، منحنی img0 با img0 رأس و مقدار img0 داده می‌شود. img0 طول کوتاه‌ترین یال منحنی img0 است. منحنی img0 و img0 دارای یال‌هایی با شرط img0 و img0 هستند. شرط‌ها در واقع نشان دهنده این هستند که مسئله برای منحنی با طول یال‌های طویل است. هدف،  مشخص کردن این است که فاصله فرشه میان img0 و img0 حداکثر مقدار img0 است یا نه. گودموندسون و همکارانش ساختمان داده‌ای ارائه کردند که با زمان پیش‌پردازش و فضای ذخیره‌سازی img0 به پرس‌و‌جو در زمان img0 پاسخ می­دهد.

 دی برگ و همکارانش  در سال 2017 ساختمان داده پویا برای پرس‌و‌جوی مجاورت در مجموعه‌ای از مسیرهای جهت‌دار ارائه کردند. برخلاف کارهای قبلی که ورودی مسئله تنها یک مسیر جهت‌دار بود، در این مقاله ورودی مسئله مجموعه img0 شامل img0 مسیر جهت‌دار و مقدار ثابت img0 است که تعداد رئوس مسیر جهت‌داری است که در زمان پرس‌و‌جو داده می‌شود. ساختمان داده طراحی شده توسط دی برگ و همکارانش می‌تواند پرس‌و‌جوهای زیر را پاسخ بدهد[15].

    1.  نزدیک‌ترین همسایه: پرس‌و‌جو مسیر جهت‌دار img0 است. هدف یافتن مسیری از بین مسیرهای جهت‌دار موجود در img0 است که فاصله فرشه آن از img0 کمینه باشد.

    2. img0-تا نزدیک‌ترین: پرس‌و‌جو، مسیر جهت‌دار img0 و مقدار صحیح img0 است. هدف گزارش img0  مسیر از بین مسیرهای جهت‌دار موجود در img0 است که فاصله فرشه آنها از img0 کمینه است. 

    3.  پرس‌و‌جوی بازه‌ای: پرس‌و‌جو، مسیر جهت‌دار img0 و مقدار img0 است. هدف گزارش کردن تمام مسیرهای جهت‌دار است که فاصله فرشه آنها از img0 حداکثر img0 است.

    4.  تشابه: پرس‌و‌جو، مسیر جهت‌دار img0 و مسیر جهت‌دار img0 موجود در مجموعه ورودی است. هدف محاسبه فاصله فرشه میان img0 و img0 است.

 ساختمان داده ارائه شده، مسائلی که در بالا بیان شد را به صورت تقریبی حل می‌کند. ضریب تقریب حداکثر برابر با img0 است که img0 حداکثر فاصله اقلیدسی میان نقطه شروع img0 و سایر رئوس دیگر img0 است. فضای مورد نیاز برای ساختن ساختمان داده img0 است. زمان پاسخ به پرس‌و‌جو برای مسائل ذکر شده در بالا به ترتیب به صورت زیر است:

    1.  نزدیک‌ترین همسایه: img0 

    2. img0-تا نزدیک‌ترین: img0 

    3.  پرس‌و‌جوی بازه‌ای: img0  img0 تعداد مسیرهای جهت‌دار خروجی است.

    4.  تشابه: img0 

 زمان درج کردن یک مسیر جهت‌دار با img0 رأس در ساختمان داده به صورت سرشکن برابر با img0 است. زمان حذف کردن یک مسیر جهت‌دار با img0 رأس از ساختمان داده به صورت سرشکن برابر با img0 است.

پرس‌و‌جوی فاصله فرشه برای مسئله جستجوی بازه‌ای بین یک مجموعه از مسیرهای جهت‌دار و یک پرس‌و‌جو به صورت تجربی مورد بررسی قرار گرفته است و کیفیت الگوریتم بر روی پایگاه داده گزارش شده است[16، 17، 18[.

در این مقاله مسئله تشابه در حوزه فاصله فرشه را به صورت تجربی بررسی می‌کنیم. به این صورت که مسیر جهت‌دار img0 با img0 رأس به عنوان ورودی داده شده است. در زمان پرس‌و‌جو پاره‌خط افقی img0 توسط کاربر مشخص می‌شود. هدف ذخیره مسیر جهت‌دار img0 در یک ساختمان داده است به صورتی که بتوانیم زیرمسیر img0 از مسیر جهت‌دار را گزارش کنیم که فاصله فرشه میان زیرمسیر img0 و پاره‌خط افقی img0 بین تمام زیرمسیرهای ممکن مینیمم باشد. زیرمسیر یک مسیر جهت‌دار همبند از مسیر اصلی است به‌صورتی که نقطه ابتدا و انتهای آن جزء رئوس مسیر اصلی هستند.

این مسئله بسیار پیچیده‌ای است و تا جایی که ما اطلاع داریم هیچ‌گونه نتیجه تئوری و تجربی برای این مسئله گزارش نشده است. راه حل اولیه برای یافتن پاسخ این است که فاصله فرشه میان تمامی زیرمسیرهای ممکن را محاسبه کنیم و سپس زیرمسیری که کمترین فاصله فرشه را دارا می‌باشد، گزارش کرد. با کمک ساختمان داده ارائه شده ، فاصله فرشه میان زیرمسیر و پاره‌خط افقی در زمان img0 قابل محاسبه است[12]. از طرفی تعداد زیرمسیرهای ممکن img0 می‌باشد. بنابراین می‌توان در زمان img0 هر پرس‌و‌جویی را پاسخ داد. اما این زمان در 

عمل کارآمد نمی‌باشد و نیازمند ایده خلاقانه برای بهبود زمان هستیم.

در این مقاله یک الگوریتم ابتکاری برای مسئله ارائه خواهیم داد. این الگوریتم از دو مرحله تشکیل شده است. در مرحله اول، با کمک ساختمان داده جستجوی بازه‌ای یک زیرمسیر را مشخص می‌کنیم و سپس در مرحله دوم با کمک روش‌های ارائه شده، زیرمسیر اولیه را تغییر می‌دهیم تا به پاسخ بهینه نزدیک گردد.

 

 

 

[1]  Felix Hausdorff

[2]  Alt

[3]  Maurice René Fréchet

[4]  Godua

[5]  de Berg

[6]  Gudmundsson

[7]  Smid

[8]  Driemel

[9]  Har-Peled

img0 

شکل 1 . حالات مختلف برای محاسبه فاصله زوج برگشتی

الگوریتم ارائه شده را بر روی چند پایگاه داده اجرا کرده‌ایم و کیفیت الگوریتم ارائه شده را برحسب درصد پرس‌و‌جو‌هایی که به درستی پاسخ داده می‌شوند، گزارش می‌کنیم.

3. مفاهیم اولیه

 مختصات هر نقطه img0 در صفحه را به صورت img0 نشان می‌دهیم. فرض می‌کنیم که img0 توالی از img0 نقطه در صفحه است و img0 یک مسیر جهت‌دار در صفحه است که توسط توالی ذکر شده تعریف شده است. img0 یک خط افقی در صفحه است به صورتی که مختصات نقطه img0 و img0 به ترتیب برابر با img0  و img0 است به صورتی که img0 و img0. فرض کنید که img0 و img0 دو رأس دلخواه از مسیر جهت‌دار img0 باشد. زیرمسیر جهت‌دار که از رأس img0 آغاز و به رأس img0 ختم می‌گردد را با عبارتimg0  نشان می‌دهند. زوج نقطه img0 زوج برگشتی (رو به جلو) است اگر img0 و نقطه img0 سمت چپ (رأست) نقطه img0 واقع شده باشد. یک یال که نقطه img0 را به نقطه img0 وصل می‌کند، یال برگشتی (رو به جلو) است اگر زوج img0 یک زوج برگشتی (رو به جلو) باشد.

فاصله زوج برگشتی، ماکزیمم فاصله میان نقطه img0 و img0 و یک نقطه بر روی پاره‌خط افقی است. نقطه‌ای بر روی پاره­خط افقی که فاصله زوج برگشتی را مشخص می‌کند، نقطه تقاطع بین عمودمنصف خط واصل بین img0 و img0 و پاره‌خط افقی است،  اگر نقطه تقاطع بین نوار عمودی img0 واقع شده باشد.  غیر اینصورت نقطه تقاطع بین خط img0 یا img0 و پاره‌خط افقی را باید محاسبه کرد. شکل 1 حالات مختلف فاصله زوج برگشتی را نشان می‌دهد. فاصله زوج برگشتی برای یک زوج برگشتی img0 به صورت زیر تعریف می‌گردد:

img0 

عبارات داخل آکولاد فاصله بین نقطه داده شده img0 و نقطه img0 و نقطه img0 را محاسبه می‌کند. فاصله زوج نقاط برگشتی مربوط به زیرمسیر جهت‌دار img0 به این‌گونه تعریف می‌شود:

img0 

فاصله هاسدورف جهت‌دار بین زیرمسیر جهت‌دار img0 و پاره‌خط افقی img0 به‌صورت زیر محاسبه می‌شود:

img0 

طبق نتایج موجود در [12]، فاصله فرشه بین زیرمسیر جهت‌دار img0 و پاره‌خط افقی img0 به‌صورت زیر محاسبه می‌شود:

img0 

img0 فاصله اقلیدسی میان نقطه img0 و img0 می‌باشد.

 زیرمسیر جهت‌دار بهینه img0 زیرمسیری از img0 است که فاصله فرشه آن از پاره‌خط افقی img0 بین تمامی زیرمسیرهای ممکن مینیمم است. بنابراین برای هر زیرمسیر جهت‌دار img0 از img0 خواهیم داشت: 

img0 

4. الگوریتم پیشنهادی

 در این قسمت یک الگوریتم ابتکاری ارائه خواهد شد که زیرمسیری از مسیر جهت‌دار را گزارش می‌کند که فاصله فرشه آن از پاره‌خط افقی میان تمام زیرمسیرهای ممکن مینیمم است. الگوریتم از دو مرحله تشکیل شده است که در مرحله اول نقطه ابتدا و انتها برای زیرمسیر مشخص می‌شود که این نقاط برأساس دو تا عبارت ابتدایی فرمول (4) مشخص می‌گردند. در مرحله دوم الگوریتم بررسی می‌شود که آیا سایر عبارات دیگر فرمول (4) فاصله فرشه را اضافه می‌کنند یا نه. اگر سایر عبارت فرمول (4) باعث ازدیاد فاصله فرشه گردد، زیرمسیر بدست آمده در مرحله اول تغییر داده می‌شود و در نهایت زیرمسیری گزارش می‌گردد.

نکته کلیدی برای بدست آوردن زیرمسیر img0، مینیمم کردن دو عبارت ابتدایی فرمول (4) است. برای مینیمم کردن دو عبارت ابتدایی، نزدیک‌ترین نقاط مسیر جهت‌دار img0 به نقطه img0 و نقطه img0 محاسبه می‌گردد. این نقاط به ترتیب img0 و img0 نامیده می‌شود. با کمک ساختمان داده نزدیک­ترین همسایه نقاط img0 و img0 محاسبه می‌شوند. اگر نقطه img0 بعد از نقطه img0 در مسیر img0 واقع شده باشد، اصلاحاتی بر روی زیرمسیر اعمال می‌گردد به صورتی که بعد از آن نقطه img0 قبل از نقطه img0 واقع می‌گردد. قابل ذکر است که اگر از ابتدا نقطه img0 قبل از نقطه img0 واقع شده باشد، می‌توان از مرحله اول صرفنظر کرد و به مرحله دوم رفت. در غیر اینصورت تغییراتی را اعمال می‌کنیم به صورتی که بعد از آن نقطه img0 قبل از نقطه img0 قرار خواهد گرفت.

 به منظور اعمال تغییرات، فواصل img0 و img0 محاسبه می‌گردد. اگر img0 باشد، اندیس img0 را می‌توان به رأسی قبل از نقطه img0 منتقل کرد که فاصله آن از نقطه img0 کمتر از img0 باشد. دیسک img0 را با مرکز img0 و شعاع img0 در نظر بگیرید. همانگونه که در شکل 2 مشخص است، اگر دیسک img0 مسیر جهت‌دار img0 را قبل از نقطه img0 قطع کند، نقطه img0 به رأسی داخل دیسک img0 قبل از img0 انتقال داده می‌شود. در غیر اینصورت رأسی بین img0 و img0 را به عنوان اندیس جدید انتخاب می‌کنیم که ماکزیمم فاصله آن از نقاط img0 و img0 مینیمم باشد.

 

C:\Users\Alborz\Desktop\Zeinab\Image\1.png 

شکل 2: در این حالت  i>j و  disti<distj است. نقطه آبی رنگ داخل دیسک Bi، اندیس جدید برای i می‌باشد.

 

اگر img0 باشد، اندیس img0 را می‌توان به رأسی بعد از نقطه img0 منتقل کرد که فاصله آن از نقطه img0 کمتر از img0 باشد. دیسک img0 را با مرکز img0 و شعاع img0 در نظر بگیرید. اگر دیسک img0 مسیر جهت‌دار img0 را بعد از نقطه img0 قطع کند، نقطه img0 به رأسی داخل دیسک img0 بعد از img0 انتقال داده می‌شود. اگر نتوانیم نقاط جدید در دیسک‌های img0 و img0 پیدا کنیم، رأسی بین img0 و img0 را به عنوان اندیس جدید انتخاب می‌کنیم که ماکزیمم فاصله آن از نقاط img0 و img0 مینیمم باشد. الگوریتم 1 جزئیات مرحله اول الگوریتم را نشان می‌دهد.

 

 

 

 

Algorithm 1 Finding The Subtrajectory

Input: The trajectory img0 and a horizontal segment pq

Output: Candidate subtrajectory

Let i and j be the index of the closest vertices of img0 to p and q

1:

if (i > j) then

2:

  if (img0) then

3:

    change i into a vertex in img0 before img0

4:

  else

5:

    if (img0) then

6:

      change j into index of vertex in img0 after img0

7:

    else

8:

      i = j = The index of a vertex between j and i which minimize the maximum distance to img0 and img0;

9:

    end if

10:

  end if

11:

end if

12:

 

در مرحله دوم الگوریتم، ماکزیمم عباراتی که فاصله فرشه میان زیرمسیر انتخاب شده از مرحله اول و پاره‌خط افقی را مشخص می‌کند، محاسبه می‌کنیم. در پایگاه داده‌هایی که در این مقاله بررسی می‌کنیم، عبارت آخر هیچ گاه فاصله فرشه را مشخص نمی‌کند. دلیل اصلی این است که چون طول یال‌های مسیرهای جهت‌دار در پایگاه داده‌های مورد بررسی کوچک است، نوار عمودی ایجاد شده باریک است و عمودمنصف، پاره خط افقی را خارج از نوار عمودی قطع می‌کند (حالت میانی و سمت رأست شکل 1). در این حالات، تصویر عمودی نقطه img0 یا img0 فاصله زوج برگشتی را مشخص می‌کند. بنابراین فاصله زوج برگشتی برای یک زیرمسیر جهت‌دار حداکثر برابر با فاصله هاسدورف است.

بر اساس مقدار ماکزیمم، حالات زیر را خواهیم داشت:

    • اگر مقدار ماکزیمم عبارت img0 یا img0 باشد، الگوریتم زیرمسیر img0 را گزارش می‌کند. ازآن‌جایی که img0 و img0 نزدیک‌ترین نقاط به img0 و img0 هستند، بنابراین دو عبارت اول، کمترین مقدار ممکن خود را دارا هستند، و از طرفی ماکزیمم این دو عبارت فاصله فاصله فرشه را تعیین می‌کند، بنابراین زیرمسیر img0 کمترین فاصله فرشه از پاره‌خط افقی را دارا است. لذا خواهیم داشت:

img0 

•  اگر مقدار ماکزیمم عبارت img0 باشد،  آنگاه ابتدا رأس img0 بین img0 و img0 که فاصله هاسدورف جهت‌دار بین img0 و پاره‌خط افقی را تعیین می‌کند، مشخص می‌کنیم. با توجه به موقعیت این رأس سه حالت زیر را خواهیم داشت:

1- اگر رأس img0 سمت چپ پاره­خط افقی واقع شده باشد، آنگاه اندیس img0 را به رأسی قبل از img0 منتقل می‌کنیم که فاصله آن از نقطه img0 مینیمم باشد. بنابراین، img0.  

2- اگر رأس img0 سمت رأست پاره خط افقی واقع شده باشد، آنگاه اندیس img0 را به رأسی قبل از img0 منتقل می‌کنیم که فاصله آن از نقطه img0 مینیمم باشد. بنابراین، img0 .

3- اگر رأس img0 بین نقطه img0 و img0 واقع شده باشد، آنگاه اندیس img0 و img0 را به اندیس‌های جدید img0 و img0 مطابق دو مورد بالا منتقل می‌کنیم. سپس عبارات img0، img0 و img0 را محاسبه می‌کنیم و هر کدام که مقدارش مینیمم گردید را گزارش می‌کنیم. جزئیات بیشتر این مرحله در الگوریتم 2 نشان داده شده است.

پایگاه داده

زمان بر حسب ثانیه

ECG200

1/6424

CBF

3/9366

GunPoint

6/4094

FaceUCR

3/9787

FaceAll

4/1524

Plane

5/3504

SwedishLeaf

4/0188

SIGSPATAL

3/9125

تحلیل پیچیدگی زمانی الگوریتم ارائه شده: اندیس img0 و img0  در خط اول الگوریتم 1 با کمک ساختمان داده جستجوی نزدیک­ترین همسایه در زمان img0محاسبه می­گردد. خط 4، 7 و 9 را می­توان در بدترین حالت در زمان img0 محاسبه کرد (در بدترین حالت باید img0 نقطه را بررسی کرد).  بنابراین، الگوریتم 1 به زمان  img0نیاز دارد. محاسبه خط اول الگوریتم 2 با استفاده از ساختمان داده­های ارائه شده در زمان img0 محاسبه می­گردد. خطوط 8، 12 ، 16 و17 را می­توان در بدترین حالت در زمان img0 محاسبه کرد. بنابراین، الگوریتم 2 به زمان  img0 نیاز دارد[12]. بنابراین الگوریتم ارائه شده در مقاله در زمان img0 زیرمسیر را گزارش می­کند. میانگین زمان صرف شده برای اجرای الگوریتم در پایگاه داده­های استفاده شده در این مقاله در جدول 1 آورده شده است. مقادیر جدول نشان می­دهد که اجرای

                جدول 1  .زمان صرف شده برای اجرای الگوریتم                                     

الگوریتم بر روی هر کدام از مسیرهای جهت­دار موجود در پایگاه داه به ­صورت میانگین چند ثانیه طول می­کشد.

 

        

                

Algorithm 2 Reporting The Subtrajectory

Input: The subtrajectory [pi, pj] that is determined in Algorithm 1

Output: Report the optimal subtrajectory

 

img0 

img0 

1:

if (img0) then

2:

  return img0

3:

else

4:

  if (img0) then

5:

    k = the index of vertex img0 between img0 and img0 that determines the Hausdroff distance.

6:

    if (img0) then

7:

      img0

8:

      return img0

9:

    else

10:

      if (img0) then

11:

       img0

12:

       return img0

13:

      else

14:

       if (img0) then

15:

        img0

16:

        img0

17:

 

img0 

img0 

18:

        if (img0) then

19:

          return img0

20:

        else

21:

          if (img0) then

22:

            return img0

23:

          else

24:

            return img0

25:

          end if

26:

        end if

27:

      end if

28:

    end if

29:

  end if

30:

 end if

31:

end if

32:

 

img0 

img0 

الف

ب

img0 

ج

 

شکل 3. (الف): مسیر جهت‌دار روبه­جلو (ب): مسیر جهت‌دار روبه‌عقب. (ج): مسیر جهت‌دار خنثی

5. نتایج تجربی

در این قسمت نتایج تجربی بر روی الگوریتم ارائه شده در قسمت قبل ارائه و کیفیت الگوریتم و زمان آن  گزارش می­شود. مسائل پرس­و­جوی فرشه مسائل جدیدی هستند. نتایج تئوری و تجربی زیادی در حوزه پرس­و­جوی فرشه وجود ندارد. به طور خاص، مسئله بررسی شده در این مقاله نه از نظر تئوری و نه از نظر تجربی تا­کنون بررسی نشده است و الگوریتم ارائه شده در بحش قبلی، ا‌ولین الگوریتم ابتکاری برای این مسئله است. با توجه به عدم وجود الگوریتم‌های دیگری برای حل مساله، امکان مقایسه بین الگوریتم‌های مختلف به صورت تجربی وجود ندارد. در ادامه، کیفیت این الگوریتم با اجرای آن روی چند پایگاه داده بررسی می‌شود.

پنج پایگاه داده از مجموعه UCR  که شامل 85 پایگاه داده از مسیرهای جهت‌دار یک بعدی است را برای اجرای الگوریتم انتخاب کرده‌ایم[19[. هم‌چنین از پایگاه داده که مربوط به سفرهای جاده‌ای در سانفرانسیسکو می‌باشد، استفاده کرده‌ایم. این پایگاه داده، پایگاه داده‌ای است که در چالش سال 2017 مربوط به SIGSPATIAL استفاده شده است. این پایگاه داده از 20000 مسیر جهت‌دار تشکیل شده است که تعداد رئوس مسیرها بین 11 تا 769 می‌باشد. این پایگاه داده دارای یک ویژگی خوب است، طول یال‌های مسیرهای جهت‌دار موجود در پایگاه داده کوچک است و این ویژگی باعث می‌شود که الگوریتم قادر باشد در اکثر موارد پاسخ بهینه را پیدا کند. پرس‌و‌جو که یک پاره‌خط افقی است به صورت تصادفی تولید شده است. برای هر مسیر جهت‌دار ده پاره‌خط افقی به صورت تصادفی تولید شده است (دو نقطه برای مولفه دو سر پاره‌خط و یک نقطه برای مولفه img0 به صورت تصادفی تولید کرده‌ایم) و الگوریتم بر روی آن اجرا شده است.

الگوریتم ارائه شده در نرم‌افزار متلب بر روی سیستم عامل ویندوز 10 پیاده‌سازی شده است. الگوریتم بر روی لپ‌تاپ لنوو با پردازنده مرکزی اینتل مدل core-i7 4510 با سرعت 2 گیگاهرتز و RAM هشت گیگابایت اجرا شده است.

در پایگاه داده‌های استفاده شده با توجه به جهت پاره‌خط افقی که از سمت چپ به رأست می‌باشد، سه نوع مسیر جهت‌دار وجود دارد. مسیر روبه­جلو مسیری است که شی متحرک در بیشتر مواقع رو به جلو حرکت می‌کند به این معنی که تعداد یال‌های رو به جلو بیشتر از نصف کل یال‌ها است و نقطه شروع حرکت سمت چپ نقطه انتها قرار دارد. نوع بعدی، مسیر جهت‌دار روبه‌عقب می‌باشد. در این نوع مسیر جهت‌دار، شی متحرک در بیشتر مواقع رو به عقب حرکت می‌کند به این معنی که تعداد یال‌های برگشتی بیشتر از نصف کل یال‌ها است و نقطه شروع حرکت سمت راست نقطه انتها قرار دارد. نوع آخر مسیر جهت‌داری است که شی متحرک تقریباً به صورت مساوی به جلو و عقب حرکت کرده است. این نوع را مسیر جهت‌دار خنثی می‌نامیم. شکل 3  انواع مختلف مسیر جهت‌دار را نشان می‌دهد.

شکل 4 توزیع مسیرهای جهت‌دار مختلف در پایگاه داده‌های استفاده شده را نشان می‌دهد. همان طور که در شکل 4 مشخص شده است بیشترین قسمت از هر پایگاه داده شامل مسیرهای جهت‌دار روبه‌عقب است. در پایگاه داده FaceAll ،ECG200  و FaceUCR مسیر خنثی وجود ندارد و فقط شامل مسیرهای روبه‌جلو و روبه‌عقب می‌باشد. در ادامه الگوریتم را بر روی انواع مختلف مسیرهای جهت‌دار در پایگاه داده‌های ذکر شده اجرا کرده و کیفیت الگوریتم را گزارش می‌کنیم. شکل 5 میزان درستی الگوریتم در پایگاه داده‌های استفاده شده را نشان می‌دهد. در ادامه نتیجه چند پایگاه داده را تحلیل خواهیم کرد.

تحلیل پایگاه داده SIGSPATIAL: نتایج نشان می‌دهد که کیفیت الگوریتم برای مسیرهای جهت‌دار روبه‌جلو در این پایگاه داده img0 است. در واقع الگوریتم ارائه شده فقط در img0 پرس‌و‌جوها برای مسیرهای جهت‌دار روبه‌جلو قادر نیست که جواب بهینه را گزارش کند. الگوریتم اندیس img0 یا img0 را با کمک دیسک img0 یا img0 در مرحله اول الگوریتم برای اکثر مسیرهای جهت‌دار روبه‌جلو تغییر می‌دهد. همچنین در مرحله دوم الگوریتم ماکزیمم عبارات img0 یا img0 فاصله فرشه را تعیین می‌کند. تنها در img0 پرس‌و‌جوها عبارت مربوط به فاصله هاسدورف، فاصله فرشه را تعیین می‌کند و الگوریتم ارائه شده علیرغم اصلاحات صورت گرفته قادر نیست که جواب بهینه را پیدا کند. کیفیت الگوریتم برای مسیرهای جهت‌دار روبه‌عقب و مسیرهای جهت‌دار خنثی در پایگاه داده img0 است. الگوریتم قادر نیست که در مرحله اول برای اکثر مسیرهای جهت‌دار روبه‌عقب، اندیس img0 یا img0 را با کمک دیسک img0 یا img0 تغییر بدهد. در واقع الگوریتم زیرمسیری را گزارش می‌کند که نقطه شروع و انتهای آن یکسان است. در img0 پرس‌و‌جوها عبارت مربوط به فاصله هاسدورف، فاصله فرشه را تعیین می‌کند و الگوریتم ارائه شده نمی‌تواند زیرمسیر بهینه را پیدا کند. در واقع اصلاحات انجام شده در فاصله هاسدورف در الگوریتم 2 همواره به درستی عمل نمی‌کند. اگر جهت پاره‌خط افقی را تغییر بدهیم، یعنی پاره‌خط افقی از سمت رأست به چپ باشد، مسیر جهت‌دار رو به عقب تبدیل به مسیر جهت‌دار رو به جلو می‌شود و نتایج هم تغییر خواهد کرد.

کیفیت الگوریتم ارائه شده برای پایگاه داده img0 است و تنها در یک درصد از پرس‌و‌جوها زیرمسیر بهینه گزارش نمی‌گردد. تنها علت اصلی برای خطای الگوریتم اصلاحاتی است که در الگوریتم2 در قسمت فاصله هاسدورف صورت گرفته است. برای حذف کردن یک درصد خطا باید اصلاحات این قسمت را بهبود داد.

تحلیل پایگاه داده GunPoint: نتایج نشان می‌دهد که کیفیت الگوریتم برای مسیرهای جهت‌دار روبه‌جلو در این پایگاه داده img0 است. در واقع الگوریتم ارائه شده تقریبا در img0 پرس‌و‌جوها برای مسیرهای جهت‌دار روبه‌جلو قادر نیست که جواب بهینه را گزارش کند. کیفیت الگوریتم برای مسیرهای جهت‌دار روبه‌عقب و مسیرهای جهت‌دار خنثی در پایگاه داده تقریبا img0 است.

 

 

 

 

 

 

img0 

شکل 4. توزیع مسیرهای جهت‌دار در پایگاه داده‌های استفاده شده

 

 

 

 

 

 

 

 

 

 

 

 

C:\Users\Alborz\Desktop\Zeinab\CBF1.jpg

Plane

C:\Users\Alborz\Desktop\Zeinab\SwedishLeaf1.jpg

SwedishLeaf

C:\Users\Alborz\Desktop\Zeinab\GunPoint1.jpg

GunPoint

C:\Users\Alborz\Desktop\Zeinab\Plane1.jpg

CBF

FaceUCR

C:\Users\Alborz\Desktop\Zeinab\FaceUCR1.jpg

FaceAll

C:\Users\Alborz\Desktop\Zeinab\FaceAll1.jpg

ECG200

C:\Users\Alborz\Desktop\Zeinab\ECG2001.jpg

SIGSPATIAL

C:\Users\Alborz\Desktop\Zeinab\OOld1.jpg 

شکل 5 .درستی الگوریتم ارائه شده برای مسیرهای جهت­دار مختلف در پایگاه داده­های استفاده شده

 

 

 

 

 

 

 

 

 

نکات زیر در مورد اجرای الگوریتم ارائه شده بر روی پایگاه داده‌های ذکر شده بدست آمده است:

  • اگر جهت پاره‌خط افقی را تغییر بدهیم، یعنی پاره‌خط افقی از سمت رأست به چپ باشد، مسیر جهت‌دار رو به عقب تبدیل به مسیر جهت‌دار رو به جلو می‌شود و نتایج هم تغییر خواهد کرد.

• دلیل اصلی برای پایین بودن خطای الگوریتم ارائه شده این است که طول یال‌های مسیرهای جهت‌دار موجود در پایگاه داده‌های مورد بررسی کوچک است. بنابراین اصلاحات صورت گرفته در مرحله اول و دوم الگوریتم ارائه شده به خوبی عمل می‌کند و الگوریتم قادر است در اکثر موارد پاسخ بهینه را پیدا کند.

• هر چقدر ماکزیمم طول یال در پایگاه داده بیشتر باشد، میزان خطای الگوریتم بالا می‌رود.

جدول 1 میزان اختلاف میان پاسخ الگوریتم ارائه شده و جواب بهینه، برای پایگاه داده‌های استفاده شده را نشان می‌دهد. همان‌طور که مشخص است، بیشترین اختلاف مربوط به پایگاه داده FaceAll است.

                  جدول 2. میزان اختلاف با مقدار بهینه

پایگاه داده

Forward

Backward

Neutral

ECG200

0/31

0/33

 

CBF

0/48

0/51

0/56

GunPoint

0/16

0/08

0/06

FaceUCR

1/13

1/2

 

FaceAll

1/31

1/15

 

Plane

0/39

0/37

0/5

SwedishLeaf

0/51

0/53

0/6

SIGSPATAL

0/22

1/53

0/43

 

6. نتیجه‌گیری

 در این مقاله مسئله تشابه در حوزه فاصله فرشه به صورت تجربی مورد بررسی قرار گرفت. به این صورت که مسیر جهت‌دار img0 به عنوان ورودی داده شده است. در زمان پرس‌و‌جو پاره‌خط افقی img0 توسط کاربر مشخص می‌شود. الگوریتم ابتکاری ارائه شده زیرمسیری از مسیر جهت‌دار را گزارش می‌کند به ‌صورتی که فاصله فرشه میان زیرمسیر گزارش‌شده و پاره‌خط افقی img0 بین تمام زیرمسیرهای ممکن مینیمم می‌باشد. کیفیت الگوریتم ارائه شده بر روی چند پایگاه داده بررسی و گزارش شد. مقاله را با ارائه چند مسئله باز به پایان می‌رسانیم:

    1.  چگونه می‌توان این مسئله را برای حالتی که پاره‌خط غیرافقی باشد، حل کرد؟ 

   2.  چگونه می‌توان الگوریتمی ارائه کرد که بتواند مسئله را برای هر نوع پرس‌و‌جو حل کند؟ 

    3.  آیا می‌توان الگوریتم را به صورتی تغییر داد که خطا نداشته باشد و همواره پاسخ بهینه را تولید کند؟

مراجع

[1] 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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Measuring Similarity for Directed Path in Geometric Data

Abstract:

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.

Keywords: Data structure, Fréchet distance, Hausdorff distance, Similarity, Directed Path

 

 

 

145

 

 


حقوق این وب‌سایت متعلق به سامانه مدیریت نشریات رایمگ است.
حق نشر © 1403-1396

صفحه اصلی| عضویت/ ورود| درباره رایمگ| تماس با ما|
[English] [العربية] [en] [ar]