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

نویسندگان

1 دانشگاه بین‌المللی امام رضا علیه‌السلام - گروه مهندسی کامپیوتر

2 دانشگاه صنعتی سجاد - دانشکده مهندسی کامپیوتر و فناوری اطلاعات

چکیده

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

کلیدواژه‌ها


عنوان مقاله [English]

Approximate k Nearest Neighbor Search with Linear Combination Method

نویسندگان [English]

  • V. Monemizadeh 1
  • J. Hamidzadeh 2
1 Computer Engineering Department, Imam Reza International University, Mashhad, Iran
2 Faculty of Computer Engineering and Information Technology, Sadjad University of Technology, Mashhad, Iran
چکیده [English]

Approximate k nearest neighbor search problem in high dimensional Euclidean spaces is a classical problem in computational geometry, image similarity search, video, and so on. In this problem, we are given a point set P of size n in the d-dimensional space and a parameter k, the goal is to preprocess P. So that given a query point q we can return fairly fast k points in which the points are good approximations of the k nearest neighbors to Q in P. In this paper, an algorithm for searching k nearest neighbor is presented for high dimensional data. In this method, first, data with high-dimensional are embedded in hamming space, then with a linear combination of random vectors and embedded data in hamming space, hash tables are formed. We conduct extensive experiments for this algorithm on big dataset of handwriting English single-digit images. This algorithm led good results for sparse matrices. Experimental results show that the proposed algorithm has the better accuracy comparing to the new methods.

کلیدواژه‌ها [English]

  • Approximate k nearest neighbor search
  • high dimensional
  • linear combination
  • Embedding
  • curse dimensional
  • locality sensitive hashing (LSH)