اندازه¬گیری میزان تشابه مسیرهای جهت¬دار بر روی داده¬های هندسی
محورهای موضوعی :
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.