چگونه الگوریتم HNSW جستجوی سریع و تقریبی نزدیک‌ترین همسایه را در پایگاه‌های داده برداری ممکن می‌کند

معماران سنتی پایگاه‌های داده اغلب تاکید می‌کنند که یافتن مرتبط‌ترین بخش از اطلاعات، نیازمند بررسی تک‌تک رکوردهای موجود است تا دقت مطلق تضمین شود. در یک پایگاه داده رابطه‌ای استاندارد، این رویکرد جستجوی فراگیر (brute-force) به خوبی کار می‌کند. اما در فضای با ابعاد بالای هوش مصنوعی مدرن، جایی که یک قطعه متن ساده با برداری متشکل از ۱۵۳۶ عدد مجزا نشان داده می‌شود، جستجوی دقیق به یک فلج محاسباتی می‌انجامد. الگوریتم HNSW (دنیای کوچک قابل‌هدایت سلسله‌مراتبی) ثابت می‌کند که با کنار گذاشتن تضمین دقت مطلق و در عوض پیمایش یک گراف احتمالی چندلایه، سیستم‌ها می‌توانند پاسخ درست را با دقت حدود ۹۹ درصد بازیابی کنند و در عین حال، تاخیر جستجو را از چند دقیقه به چند میلی‌ثانیه کاهش دهند.[5][8]

برای درک ضرورت وجود HNSW، ابتدا باید با مفهوم «نفرین ابعاد» (curse of dimensionality) آشنا شد. وقتی یک مدل هوش مصنوعی سندی را به یک امبدینگ برداری (vector embedding) تبدیل می‌کند، در واقع آن سند را به عنوان یک مختصات در فضایی با صدها یا هزاران بُعد ترسیم می‌کند. برای یافتن شبیه‌ترین اسناد به پرسش کاربر، سیستم باید بردارهایی را پیدا کند که از نظر فیزیکی نزدیک‌ترین فاصله را با بردار پرسش دارند. روش دقیق برای این کار، الگوریتم k-نزدیک‌ترین همسایه (k-NN) است که فاصله بین پرسش و تک‌تک نقاط موجود در پایگاه داده را محاسبه می‌کند.[4][7]

اگر یک پایگاه داده حاوی یک میلیارد بردار باشد، یک جستجوی ساده k-NN نیازمند یک میلیارد محاسبه پیچیده فاصله است. پیچیدگی زمانی در این حالت خطی است و از نظر ریاضی با O(N) بیان می‌شود. با رشد مجموعه داده، زمان جستجو نیز دقیقاً با همان نرخ افزایش می‌یابد. برای کاربردهای بی‌درنگ مانند چت‌بات‌ها یا موتورهای توصیه‌گر، انتظار چند ثانیه‌ای - چه رسد به چند دقیقه‌ای - برای اسکن یک میلیارد رکورد توسط پایگاه داده، کاملاً غیرقابل‌قبول است.[1][5]

راه‌حل این مشکل، جستجوی تقریبی نزدیک‌ترین همسایه (ANN) است؛ دسته‌ای از الگوریتم‌ها که کسر کوچکی از دقت را فدای افزایش چشمگیر سرعت می‌کنند. در میان الگوریتم‌های ANN، الگوریتم HNSW به عنوان استاندارد صنعت شناخته شده است. این الگوریتم که در مقاله‌ای در سال ۲۰۱۶ توسط پژوهشگرانی به نام‌های یوری مالکوف (Yury Malkov) و دیمیتری یاشونین (Dmitry Yashunin) معرفی شد، به پیچیدگی زمانی لگاریتمی یا O(log N) دست می‌یابد. این بدان معناست که اگر مجموعه داده از یک میلیون به یک میلیارد رکورد افزایش یابد، زمان جستجو هزار برابر نمی‌شود؛ بلکه تنها به چند مرحله محاسباتی اضافی نیاز خواهد داشت.[1][2]

الگوریتم HNSW سرعت خود را بر پایه دو مفهوم بنیادین در علوم کامپیوتر بنا می‌کند: شبکه «دنیای کوچک» (small world) و «لیست پرشی» (skip list). شبکه دنیای کوچک گرافی است که در آن بیشتر گره‌ها مستقیماً به هم متصل نیستند، اما هر گرهی می‌تواند با تعداد کمی گام از هر گره دیگری در دسترس قرار گیرد - معادل ریاضی مفهوم «شش درجه جدایی». در یک پایگاه داده برداری، هر بردار یک گره است و توسط یال‌هایی به نزدیک‌ترین همسایگان خود متصل می‌شود.[2][4]

اگر یک گراف «قابل‌هدایت» (navigable) باشد، الگوریتم جستجو می‌تواند از هر گره تصادفی شروع کرده و حریصانه (greedily) به سمت گره مجاوری حرکت کند که به پرسش هدف نزدیک‌تر است. این فرآیند با پرش از گرهی به گره دیگر تکرار می‌شود تا جایی که به نقطه‌ای برسد که هیچ گره مجاوری نزدیک‌تر از گره فعلی به هدف نباشد. این نقطه یک کمینه محلی (local minimum) است و در یک گراف دنیای کوچک که به خوبی ساخته شده باشد، به احتمال بسیار زیاد همان نزدیک‌ترین همسایه واقعی است.[5][6]

با این حال، یک گراف مسطح دنیای کوچک یک نقص مهلک دارد: اگر نقطه شروع از هدف دور باشد، الگوریتم باید گام‌های کوچک بسیاری برای عبور از گراف بردارد که فرآیندی کند است. علاوه بر این، به راحتی می‌تواند در یک خوشه محلی از گره‌ها گرفتار شود و نزدیک‌ترین همسایه واقعی را به کلی از دست بدهد. اینجاست که مالکوف و یاشونین با الهام از لیست‌های پرشی، عنصر «سلسله‌مراتبی» (Hierarchical) را معرفی کردند.[1][5]

الگوریتم HNSW لایه‌های متعددی از گراف‌ها را می‌سازد که روی هم قرار گرفته‌اند. لایه پایینی، یعنی لایه ۰، شامل تک‌تک بردارهای موجود در پایگاه داده و اتصالات بسیار متراکم و کوتاه‌برد است. لایه بالاتر از آن تنها شامل کسری از آن گره‌ها با اتصالات دوربردتر است. این الگو به سمت بالا ادامه می‌یابد. لایه بالایی ممکن است تنها شامل تعداد انگشت‌شماری گره باشد که با پیوندهای عظیم و سراسری به هم متصل شده‌اند.[3][6]

هنگامی که یک پرسش وارد شاخص HNSW می‌شود، جستجو از بالاترین لایه آغاز می‌گردد. از آنجا که لایه بالایی گره‌های بسیار کم و پیوندهای بسیار بلندی دارد، الگوریتم می‌تواند جهش‌های عظیمی در فضای برداری انجام دهد و به سرعت روی همسایگی کلی هدف متمرکز شود. به محض اینکه کمینه محلی را در لایه بالایی پیدا کرد، به همان گره در لایه پایینی سقوط می‌کند.[4][7]

در این لایه پایین‌تر، اتصالات کوتاه‌تر و گره‌ها متراکم‌تر هستند. الگوریتم جستجوی حریصانه خود را از سر می‌گیرد و گام‌های کوچک‌تر و دقیق‌تری به سمت هدف برمی‌دارد. کمینه محلی جدید را پیدا می‌کند، یک لایه دیگر پایین می‌رود و این فرآیند را تکرار می‌کند. تا زمانی که به لایه ۰ برسد، از قبل در مجاورت نزدیک‌ترین همسایه واقعی قرار گرفته است و برای یافتن دقیق‌ترین تطابق‌ها تنها به چند تنظیم خرد نهایی نیاز دارد.[5][6]

این نزول سلسله‌مراتبی همان چیزی است که سرعت O(log N) را به HNSW می‌بخشد. پیوندهای طولانی در لایه‌های بالایی، نیاز به اسکن میلیون‌ها بردار نامربوط را دور می‌زنند و عملاً بخش اعظم پایگاه داده را در عرض چند میکروثانیه از دایره بررسی خارج می‌کنند. این ساختار مانند یک قیف پرسرعت عمل کرده و پرسش را مستقیماً به خوشه صحیح هدایت می‌کند.[1][3]

ساخت این گراف چندلایه نیازمند هماهنگی دقیق در طول درج داده‌هاست. وقتی بردار جدیدی به پایگاه داده اضافه می‌شود، الگوریتم باید تصمیم بگیرد که این بردار تا چه حد در سلسله‌مراتب بالا برود. HNSW با استفاده از یک توزیع احتمال با فروپاشی نمایی، یک لایه حداکثر را به صورت تصادفی به هر گره جدید اختصاص می‌دهد. این کار تضمین می‌کند که در حالی که هر گره در لایه ۰ وجود دارد، تنها تعداد نادری از آن‌ها به لایه‌های بالایی راه می‌یابند تا به عنوان «بزرگراه‌های» دوربرد عمل کنند.[2][5]

پس از تعیین حداکثر لایه یک گره، الگوریتم آن را لایه به لایه از بالا به پایین درج می‌کند. در هر لایه، جستجویی برای یافتن نزدیک‌ترین همسایگان گره انجام می‌دهد و اتصالاتی (یال‌هایی) با آن‌ها برقرار می‌کند. دو پارامتر حیاتی این فرآیند را کنترل می‌کنند: 'M' که حداکثر تعداد اتصالات یک گره در هر لایه را دیکته می‌کند، و 'efConstruction' که تعیین می‌کند الگوریتم در هنگام جستجوی همسایگان در طول درج، تا چه حد تور خود را گسترده پهن کند.[5][6]

مقدار بالاتر برای 'M' گراف متراکم‌تری ایجاد می‌کند که دقت جستجو را بهبود می‌بخشد، اما حافظه بیشتری مصرف کرده و فرآیند درج را کند می‌کند. مقادیر معمول برای 'M' بسته به ابعاد داده‌ها و الزامات خاص بازیابی در برنامه، بین ۱۶ تا ۶۴ متغیر است. پارامتر 'efConstruction' زمان ساخت را کنترل می‌کند؛ تنظیم آن روی مقادیر بالاتر منجر به گرافی با کیفیت بهتر و بازیابی بالاتر می‌شود، اما به قیمت زمان‌های نمایه‌سازی بسیار طولانی‌تر.[4][5]

در زمان پرسش، پارامتر سومی وارد بازی می‌شود: 'efSearch'. این پارامتر اندازه لیست پویای نزدیک‌ترین همسایگانی را کنترل می‌کند که الگوریتم در حین پیمایش گراف نگه می‌دارد. مقدار بزرگتر برای 'efSearch' الگوریتم را مجبور می‌کند مسیرهای جایگزین بیشتری را کاوش کند، که احتمال یافتن نزدیک‌ترین تطابق مطلق (بازیابی بالاتر) را به قیمت تاخیر اندکی بیشتر افزایش می‌دهد. دانشمندان داده دائماً این سه پارامتر را تنظیم می‌کنند تا تعادل بهینه را برای بارهای کاری خاص خود بیابند.[3][7]

اگرچه HNSW در ترکیب سرعت و بازیابی بی‌رقیب است، اما بدون محدودیت هم نیست. اشکال اصلی آن مصرف حافظه است. برخلاف نمایه‌های مسطح یا روش‌های کوانتیزه‌سازی که بردارها را فشرده می‌کنند، HNSW نیازمند آن است که کل ساختار گراف - شامل تمام گره‌ها و اتصالات چندلایه آن‌ها - برای پیمایش سریع در حافظه دسترسی تصادفی (RAM) ذخیره شود. برای پایگاه‌های داده‌ای که میلیاردها بردار با ابعاد بالا را در خود جای داده‌اند، این سربار حافظه می‌تواند به یک هزینه زیرساختی قابل‌توجه تبدیل شود.[5][8]

برای کاهش این مشکل، پایگاه‌های داده برداری مدرن اغلب HNSW را با کوانتیزه‌سازی محصول (PQ) یا کوانتیزه‌سازی اسکالر ترکیب می‌کنند. این تکنیک‌ها خود بردارها را فشرده کرده و ردپای حافظه را کاهش می‌دهند، در حالی که برای مدیریت مسیریابی به ساختار گراف HNSW متکی هستند. این رویکرد ترکیبی به پلتفرم‌هایی مانند Milvus و Pinecone اجازه می‌دهد تا بدون نیاز به مقادیر غیرمنطقی از حافظه سرور، تا میلیاردها بردار مقیاس‌پذیر شوند.[5][6]

ظرافت ریاضی HNSW آن را به الگوریتم نمایه‌سازی پیش‌فرض برای عصر هوش مصنوعی مولد تبدیل کرده است. این الگوریتم با ساختاردهی داده‌ها نه به عنوان یک لیست مسطح برای اسکن، بلکه به عنوان یک توپولوژی چندلایه و قابل‌هدایت، محدودیت‌های محاسباتی فضای با ابعاد بالا را دور می‌زند. این همان موتور خاموشی است که به یک هوش مصنوعی اجازه می‌دهد تا یک پرامپت را بخواند، در لحظه زمینه مرتبط را از دریای میلیاردها سند بازیابی کند و پیش از آنکه کاربر حتی پلک بزند، پاسخی آگاهانه تولید نماید.[1][8]