جستجوی k نزدیک‌ترین همسایه تقریبی با روش ترکیب خطی

Abstract

مسئله جستجوی <em>k</em> نزدیک‌ترین همسایه تقریبی در ابعاد بالا یک مسئله کلاسیک در هندسه محاسباتی، شباهت تصویر و سایر زمینه‌های مشابه می‌باشد. در این مسئله، یک مجموعه داده متشکل از <em>n</em> نقطه در فضای <em>d</em> بعدی و یک پارامتر <em>k</em> داریم، هدف پیش‌پردازش مجموعه داده است به‌طوری‌که با داشتن یک نقطه پرس‌وجوی <em>d</em> بعدی <em>Q</em> داده‌شده بتوان <em>k</em> نقطه را یافت به‌طوری‌که <em>k </em>نزدیک‌ترین همسایه تقریبی به <em>Q</em> باشد. هدف این مقاله ارائه روشی جدید برای یافتن <em>k</em> نزدیک‌ترین همسایه تقریبی برای ابعاد بالا است. در روش پیشنهادی، ابتدا داده‌های با ابعاد بالای مجموعه داده مورد نظر درون فضای همینگ جاسازی‌شده، سپس با ترکیب خطی بردارهای تصادفی و داده‌های جاسازی‌شده در فضای همینگ، جدول‌های درهم‌سازی تشکیل می‌شود. آزمایش‌های زیادی بر روی پایگاه داده بزرگ تصاویر انجام گرفته است و نتایج گویای این نکته می‌باشد که این الگوریتم برای ماتریس‌های خلوت منجر به حاصل شدن جواب‌های مناسب‌تری خواهد شد. روش پیشنهادی با روش‌های جدید نیز مقایسه شده است که نتایج آزمایش‌ها و ارزیابی آن‌ها، نشان‌دهنده برتری روش پیشنهادی از نظر صحت نسبت به آن روش‌ها می‌باشد.