جستجوی k نزدیک‌ترین همسایه تقریبی با روش ترکیب خطی
|
|
|
|
|
|
|
|
نویسنده
|
منعمی‌زاده وحیده ,حمیدزاده جواد
|
|
منبع
|
مهندسي برق دانشگاه تبريز - 1396 - دوره : 47 - شماره : 3 - صفحه:1237 -1249
|
|
چکیده
|
مسئله جستجوی k نزدیک‌ترین همسایه تقریبی در ابعاد بالا یک مسئله کلاسیک در هندسه محاسباتی، شباهت تصویر و سایر زمینه‌های مشابه می‌باشد. در این مسئله، یک مجموعه داده متشکل از n نقطه در فضای d بعدی و یک پارامتر k داریم، هدف پیش‌پردازش مجموعه داده است به‌طوری‌که با داشتن یک نقطه پرس‌وجوی d بعدی q داده‌شده بتوان k نقطه را یافت به‌طوری‌که k نزدیک‌ترین همسایه تقریبی به q باشد. هدف این مقاله ارائه روشی جدید برای یافتن k نزدیک‌ترین همسایه تقریبی برای ابعاد بالا است. در روش پیشنهادی، ابتدا داده‌های با ابعاد بالای مجموعه داده مورد نظر درون فضای همینگ جاسازی‌شده، سپس با ترکیب خطی بردارهای تصادفی و داده‌های جاسازی‌شده در فضای همینگ، جدول‌های درهم‌سازی تشکیل می‌شود. آزمایش‌های زیادی بر روی پایگاه داده بزرگ تصاویر انجام گرفته است و نتایج گویای این نکته می‌باشد که این الگوریتم برای ماتریس‌های خلوت منجر به حاصل شدن جواب‌های مناسب‌تری خواهد شد. روش پیشنهادی با روش‌های جدید نیز مقایسه شده است که نتایج آزمایش‌ها و ارزیابی آن‌ها، نشان‌دهنده برتری روش پیشنهادی از نظر صحت نسبت به آن روش‌ها می‌باشد.
|
|
کلیدواژه
|
جستجوی k نزدیک‌ترین همسایه تقریبی، ابعاد بالا، ترکیب خطی، جاسازی، نفرین ابعاد، درهم‌سازی حساس به محل یا lsh
|
|
آدرس
|
دانشگاه بین المللی امام رضا (ع), گروه مهندسی کامپیوتر, ایران, دانشگاه صنعتی سجاد, دانشکده مهندسی کامپیوتر و فناوری اطلاعات, ایران
|
|
پست الکترونیکی
|
j_hamidzadeh@sadjad.ac.ir
|
|
|
|
|
|
|