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

Measuring Similarity for Directed Path in Geometric Data

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

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.