محقق ایرانی نفرین دادههای ابعاد بالا را با الگوریتم LSH شکست
دکتر وهاب میررکنی، پژوهشگر ایرانی و دانشآموخته شریف و MIT، با تعمیم الگوریتم «هش حساس به مجاورت» (LSH) بر پایه توزیعهای پایدار، راهکاری سریع و همهمنظوره برای جستوجوی دادههای مشابه در ابعاد بسیار بالا ارائه کرد. این دستاورد که سرعت جستوجو را تا ۴۰ برابر افزایش داد، او را به عنوان برگزیده جایزه مصطفی(ص) ۱۴۰۳ معرفی کرد.
چالش نفرین ابعاد بالا
دادههای واقعی مانند تصاویر، متون و توالیهای ژنتیکی اغلب در فضاهای صدها تا میلیونها بُعدی قرار دارند. در چنین فضاها، مفهوم فاصله و شباهت از بین میرود و جستوجوی نزدیکترین همسایه با روشهای سنتی غیرممکن میشود.
راهحل مبتنی بر هش تصادفی
ایده LSH در سال ۱۹۹۸ مطرح شد: دادهها با توابع هش تصادفی به سطلهای سادهتر نگاشت میشوند تا جستوجو تنها در سطلهای مربوطه انجام گیرد. اما نسخههای اولیه تنها برای مترهای اقلیدسی و منهتن کارایی داشتند.
نوآوری میررکنی: LSH مبتنی بر توزیعهای پایدار
میررکنی و همکارانش در ۲۰۰۴ با استفاده از توزیعهای پایدار، محدودیت مترها را برداشتند. این روش برای طیف وسیعی از معیارهای فاصله کار میکند، توابع هش نادر را نیز بهکار میگیرد و حفظ شباهت در فضای جدید را تضمین میکند.
تأثیر و کاربرد
این الگوریتم امروزه از فناوریهای کلیدی در پردازش کلانداده، هوش مصنوعی، بازیابی اطلاعات، ژنتیک و سیستمهای پیشنهاددهنده است و جستوجوی سریع در میان میلیونها داده پُربُعد را عملی ساخته است.