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

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

Keywords:

جستجوی k نزدیکترین همسایه تقریبی , ابعاد باال , ترکیب خطی , جاسازی , نفرین ابعاد , درهمسازی حساس به محل یا .LSH