نزدیک ترین همسایه در ابعاد پایین
دوشنبه, ۲۱ بهمن ۱۳۹۲، ۰۶:۱۵ ب.ظ
مرجع: http://graphics.stanford.edu/courses/cs468-06-fall/Slides/nikola.pdf
پیدا کردن نزدیک ترین همسایه در ابعاد کم
هدف کاهش ثابت بر حسب epsilon ورودی در مساله ی نزدیک ترین همسایه است.
برای این کار از ساختمان داده ای به نام BBD-tree که مخفف Balanced Box Decomposition tree است، استفاده می کند. با داشتن نقطه کوئری و شعاع، پیدا کردن نقاط درون توپ به مرکز نقطه کوئری و حداکثر دو برابر شعاع ورودی زمان O(log n) می برد.
برای جستجوی بازه ای در d-1 بعد از BBD-tree که d-بعدی باشد استفاده می کنیم.
