ارائه معیاری برای حل مسائل غلبگی در شرایط نادقیق

در سال های اخیر، مدیریت داده های نادقیق، بخش مهمی از مسائل مربوط به شبکه های بی سیم را به خود اختصاصداده است. در دنیای واقعی، جمع آوری و تحلیل داده ها به دلایل مختلفی مانند نویز، خطا در وسایل اندازه گیری، حفظامنیت و ... ، همراه با خطا است. پیش فرض بسیاری از الگوریتم های کامپیوتری بر دقیق بودن داده ها است ولی داده هاتحت تاثیر عوامل مختلفی چون اختلال و خطای دستگاه های اندازه گیری، به صورت نادقیق میباشند. پردازشدرخواست های مجاورت نظیر جستجوی نزدیکترین همسایه در شرایطی که داده ها به صورت نادقیق هستند، ملزم به حلمسئله غلبگی است. فرض کنید a,bεR^d نقاط دقیق و R نقطه ای نادقیق باشد که به صورت یک گوی -d بعدی مدلشده است، در مسئله غلبگی هدف تعیین این موضوع است که آیا فاصله a از R نسبت به b از R نزدیکتر است. در اینمقاله معیاری ارائه کرده ایم که با توجه به آن، در زمان O(d) مسئله غلبگی را حل می کند.

کلیدواژه ها:

مسئله غلبگی شرایط نادقیق ، درخواست مجاورت ، جستجوی نزدیکترین همسایه