باختصار
الـ HNSW اختصار لـ Hierarchical Navigable Small World، وهي خوارزمية رسم بياني متعدد الطبقات تبحث عن أقرب الجيران بشكل تقريبي وسريع داخل ملايين المتجهات.
بالتفصيل
لما تحوّل نصوصك إلى متجهات، السؤال العملي يصبح: كيف تجد أقرب 10 متجهات لمتجه السؤال بين مليون متجه من غير ما تقارنه بكل واحد؟ ده ما يسمى بالبحث عن أقرب جار تقريبي Approximate Nearest Neighbor.
ورقة «Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs» ليوري مالكوف ودميتري ياشونين المنشورة عام 2016 تقترح بناء «بنية متعددة الطبقات تتألف من مجموعة هرمية من الرسوم البيانية التقاربية»، دون الحاجة لبنى بحث إضافية.
الفكرة أن كل عنصر يُسند إلى طبقة قصوى تُختار عشوائيًا وفق توزيع احتمالي متناقص أسّيًا — أسلوب يشبه بنية قائمة التخطي skip list. النتيجة طبقات مفصولة بمقاييس المسافة: الطبقات العليا فيها روابط طويلة تقفز بك بعيدًا بسرعة، والطبقات الدنيا فيها روابط قصيرة تضبط النتيجة بدقة. البحث يبدأ من الأعلى وينزل تدريجيًا.
الورقة تذكر أن التعقيد يتدرّج لوغاريتميًا مقارنة بأساليب العوالم الصغيرة السابقة بفضل التنظيم الهرمي، وأن الطريقة «تتفوق بقوة على أفضل الأساليب مفتوحة المصدر السابقة القائمة على المتجهات وحدها»، خصوصًا عند معدلات استرجاع عالية ومع بيانات متجمّعة عند استخدام أسلوب اختيار الجيران التقاربي. ومن معاملات البناء المذكورة معامل efConstruction.
مثال عملي
لو بتبني بحثًا دلاليًا على 500 ألف مقال عربي، المقارنة الشاملة مع كل متجه هتاخد ثوانٍ لكل استعلام. مع فهرس HNSW، نفس الاستعلام بيرجع في أجزاء من الثانية بدقة استرجاع تقترب من الشاملة. ده الفهرس الافتراضي في أغلب قواعد بيانات المتجهات، ورفع معامل البناء بيزيد جودة الفهرس على حساب وقت البناء والذاكرة.
مصطلحات مرتبطة
التضمين (Embedding)، المتجه (Vector)، البحث الدلالي (Semantic Search)، الاسترجاع المعزز للتوليد (RAG)، مُعيد الترتيب (Reranker).
المصادر: arXiv — 2016-03-30
