بسیاری از مشکلات در حوزه‌ی کامپیوتر، به یک سوال ساده و گمراه‌کننده برمی‌گردند: با داشتن یک چیز، چگونه می‌توان چیز مشابه آن را پیدا کرد؟ فرض کنید می‌خواهید فردی را پیدا کنید که از نظر فیزیکی به شما نزدیک‌تر است. پاسخ در این صورت، بدیهی به نظر می‌رسد، اما چه اتفاقی می‌افتد وقتی مجبور باشیم در فضاهای پیچیده‌تر جست وجو کنیم؟
وقتی در یک خط ایستاده و می‌خواهید نزدیک‌ترین فرد را پیدا کنید، کار ساده است: به چپ و سپس به راست نگاه می‌کنید و فاصله خود را با افراد اطراف مقایسه می‌کنید. اما اگر در یک اتاق هستید، باید نزدیک‌ترین فرد را در فضای دو بعدی پیدا کنید. دوباره، این کار چندان دشوار نیست، زیرا می‌توانید بچرخید و فاصله‌ها را در جهات مختلف بررسی کنید.
چه اتفاقی می‌افتد اگر مردم بتوانند در فضای سه بعدی شنا کنند؟ در این صورت، مسائل پیچیده می‌شوند زیرا باید در ارتفاع، عمق و عرض جستجو کرد. با افزودن بعد زمانی، مسائل بیشتر پیچیده می‌شوند. با افزایش تعداد ابعاد، این کار به سرعت غیرعملی می‌شود.
حقیقت تکان‌دهنده: بسیاری از داده‌های دنیای واقعی در ابعاد بسیار بالاتری، گاهی اوقات 100 بعد یا بیشتر، نمایش داده می‌شوند! بنابراین، این اصطلاح به عنوان "لعنتی" برای توصیف این داده‌ها استفاده می‌شود.
دکتر وحاب میرروکنی، محقق ایرانی و فارغ‌التحصیل دانشگاه شریف و موسسه فناوری ماساچوست (MIT)، راه‌حل نوینی برای جستجوی سریع در بین داده‌های مشابه در مجموعه‌های داده بزرگ پیشنهاد کرد. الگوریتم "هاشینگ حساس به محل" (LSH) او اکنون به عنوان یکی از تکنیک‌های محبوب هاشینگ در پردازش داده‌های بزرگ و هوش مصنوعی در نظر گرفته می‌شود. میرروکنی، که در حال حاضر محقق ارشد در گوگل است، در سال 2025 به پاس این دستاورد، جایزه مستفا (پ.خ) را دریافت کرد.
برای درک بهتر این تکنیک، ابتدا باید یکی از چالش‌های اساسی عصر داده را مورد توجه قرار دهیم، چالشی که یافتن یک قطعه اطلاعات ارزشمند در میان حجم عظیمی از داده‌ها، مانند جستجوی یک سوزن در یک بوته‌ی در حال رشد، را دشوار کرده است.
داده‌های لعنتی
با پیشرفت فناوری و ظهور اشکال متنوع داده در دنیای محاسبات و پردازش، با داده‌های لعنتی با ابعاد بسیار بالا مواجه شده‌ایم. یک تصویر رنگی با ابعاد 1000x1000 پیکسل (که در آن هر پیکسل یک بعد است) در یک کامپیوتر، به عنوان یک داده سه میلیون بعدی در نظر گرفته می‌شود! این به این دلیل است که هر پیکسل توسط ترکیب سه رنگ قرمز، سبز و آبی نمایش داده می‌شود، که یکی از روش‌های استاندارد ذخیره تصاویر رنگی است. حتی پس از اعمال روش‌های کاهش ابعاد، ما همچنان با صدها یا هزاران بعد در پردازش تصاویر سروکار داریم.
هنگام پردازش فایل‌های متنی، وارد حوزه پردازش زبان طبیعی می‌شویم، جایی که کلمات به بردار‌های عددی با استفاده از روش‌های خاص تبدیل می‌شوند. هر کلمه یک بردار عددی n-بعدی (100-300 بعد) دریافت می‌کند، به طوری که کلمات مشابه دارای بردار‌های مشابهی هستند. سپس، برای پردازش یک متن، کلمات کلیدی شناسایی، استخراج و بررسی می‌شوند. با استفاده از این روش‌ها، یک متن، که از چندین کلمه تشکیل شده است، به شدت ابعاد دارد. بنابراین، یک پاراگراف می‌تواند ده ها هزار ابعاد داشته باشد!
یک دسته دیگر از داده‌ها که در ده سال گذشته توجه زیادی را به خود جلب کرده است، داده‌های ژنتیکی است. هر سلول از هر موجود زنده، مولکولی به نام DNA را در خود دارد، که از چهار نوع مولکول ساده‌تر به نام پایه‌ها تشکیل شده است. با توجه به اینکه طول DNA در انسان حدود 3 میلیارد جفت پایه است، زمانی که این توالی عظیم به صورت محاسباتی نمایش داده و تحلیل می‌شود، می‌تواند منجر به داده‌های بسیار ابعاد شود. بخش‌هایی از DNA، که به آن‌ها ژن می‌گویند، عمدتاً در طول نسل‌ها حفظ می‌شوند و عملکرد بدن یک موجود زنده را تعیین می‌کنند. حفظ اطلاعات DNA هر انسان می‌تواند به دو روش انجام شود: یا کل توالی مولکولی حفظ شود، یا فقط بخش‌هایی از ژن، که تقریباً 25000 بخش با طول‌های مختلف وجود دارد، حفظ شوند. در هر صورت، با حجم زیادی از اطلاعات مواجه می‌شویم.
نزدیک، اما بسیار دور: چالش جستجو در داده‌های با ابعاد بالا
در چنین فضای ابعاد بالا، "لعنت ابعاد" رخ می‌دهد. داده‌ها به ندرت پراکنده هستند، به طوری که تقریباً همه چیز به طور مساوی از هم فاصله دارند. به عبارت دیگر، مفهوم "شباهت" از بین می‌رود، زیرا تمام داده‌ها تقریباً یکسان به نظر می‌رسند، و جستجوی نزدیک‌ترین همسایه به یک ماموریت غیرممکن و محاسبات غیرعملی تبدیل می‌شود.
جستجوی نزدیک‌ترین همسایه یکی از مسائل اصلی در علم داده، یادگیری ماشین و بازیابی اطلاعات است. هدف اصلی این فرآیند، یافتن نزدیک‌ترین نقطه (یا نقاط) به یک نقطه داده شده است، که می‌تواند بر اساس یک معیار شباهت تعیین شود. معیارهای مختلفی برای اندازه‌گیری فاصله داده‌ها وجود دارد، از جمله دو ساده‌ترین آن‌ها، فاصله اقلیدسی و فاصله منهتنی. در مورد اول، طول یک خط مورب که دو نقطه را در فضا به هم متصل می‌کند، اندازه‌گیری می‌شود، در حالی که در مورد دوم، فاصله به این صورت محاسبه می‌شود که گویی از یک نقطه به نقطه دیگر به صورت گام به گام حرکت می‌کنیم، یعنی مجموع تفاوت‌ها در داده‌ها در طول ابعاد مختلف.
در نگاه اول، به نظر می‌رسد یافتن تصویری که بیشترین شباهت را با تصویر هدف از یک پایگاه داده تصاویر دارد، یا یافتن موجودات زیستی که از نظر ژنتیکی بیشترین شباهت را دارند تا یک درخت خانوادگی تکاملی ایجاد شود، یک کار ساده است، اما این وظایف چالش‌های بسیار پیچیده‌ای را به همراه دارند. گاهی اوقات ممکن است نیاز به تشخیص شباهت و سرقت ادبی متنی، یا تحلیل احساسات موجود در متون باشد. بازار تبلیغات و سیستم‌های توصیه نیز از این چالش‌ها مصون نیستند، اگر بخواهند محصولی را بر اساس سلیقه‌های افراد و کاربران مشابه پیشنهاد دهند. در واقع، در همه این موارد، ما فقط به دنبال یافتن داده‌های مشابه‌ترین با یک نقطه داده خاص هستیم. اگر داده‌ها کم‌بعد باشند، پاسخ با استفاده از روش‌های سنتی و الگوریتم‌های سریع در مدت زمان معقولی به دست می‌آید. با این حال، چالش اصلی، ابعاد بالای داده‌ها است.