البحث المتجهي بدون القوة الغاشمة: كيف يعمل IVF و HNSW

البحث المتجهي بدون القوة الغاشمة: كيف يعمل IVF و HNSW

عندما تحتوي قاعدة بيانات متجهية على ملايين التضمينات، يصبح البحث عن متجهات متشابهة باستخدام القوة الغاشمة مستحيلاً. خوارزميتان - IVF و HNSW - تحل هذه المشكلة من خلال البحث التقريبي، وإيجاد الإجابات في أجزاء من الثانية بدلاً من الدقائق. مقالة تفصيلية جديدة على Habr تشرح كلا النهجين من النظرية الرياضية إلى التطبيق في لغة Python.

لماذا البحث الدقيق لا يعمل

في الأبعاد المنخفضة (ثنائي الأبعاد، ثلاثي الأبعاد)، يمكنك بناء الفهارس المكانية - أشجار k-d، أشجار R. تستخدم الهندسة: إذا كان الاستعلام بعيداً عن جزء من الفضاء، يمكن استبعاده من البحث دون فقدان النتائج. لكن في الأبعاد العالية (768D لـ BERT، 3072D لـ GPT-4 Turbo)، تنهار هذه الفكرة. المسافات تصبح غير محلية - تقريباً جميع النقاط على مسافة متقاربة جداً من بعضها البعض. تسمى هذه الظاهرة لعنة البعدية. تفقد الفهارس التقليدية فعاليتها، تتوقف عن تقليل فضاء البحث، وعدنا إلى القوة الغاشمة - مقارنة الاستعلام مع جميع ملايين المتجهات في قاعدة البيانات.

IVF: التجميع يأتي للإنقاذ

يحل IVF (Inverted File Index) المشكلة من خلال التجميع المسبق. تستخدم الخوارزمية k-means الكلاسيكية لتقسيم الفضاء إلى "دلو"-تجمعات شرطية. الحدس بسيط: إذا كانت المتجهات قريبة في الفضاء، يجب أن تكون في نفس التجمع، وأثناء البحث نحتاج فقط إلى فحص عدة تجمعات ذات صلة، وليس كل قاعدة البيانات. تعمل العملية على مرحلتين. أثناء الفهرسة، يتم تعيين كل متجه في قاعدة البيانات إلى أقرب تجمع له (مركزه الثقلي). أثناء البحث، يجد النظام أولاً K تجمعات أقرب للاستعلام من خلال البحث السريع، ثم يبحث عن التطابقات الدقيقة فقط داخلها. هذا يقلل بشكل كبير من عدد المقارنات - بدلاً من ملايين المقارنات، نحتاج فقط إلى بضعة آلاف.

• المرحلة الأولى: يقسم k-means الفضاء إلى مئات أو آلاف من التجمعات
• المرحلة الثانية: يتم فهرسة كل متجه من قاعدة البيانات في تجمعه (معرّف المركز الثقلي محفوظ)
• أثناء البحث: ابحث عن K تجمعات أقرب، ثم البحث الكامل فقط داخلها

يتوسع IVF بشكل جيد إلى مليارات المتجهات ويتطلب ذاكرة قليلة نسبياً. يشرح Habr التطبيق في Python مع أمثلة على الأكواد الملموسة ومقاييس الأداء.

HNSW: العالم الصغير القابل للملاحة الهرمية

يستخدم HNSW (Hierarchical Navigable Small World) منهجاً مختلفاً تماماً - بناء رسم بياني للجوار بدلاً من التجمعات. يصبح كل متجه عقدة في الرسم البياني، والحواف تربط المتجهات المجاورة (القريبة). يتم بناء الرسم البياني على نحو هرمي: في المستويات السفلية يكون هناك حي محلي كثيف لكل متجه، في المستويات العليا توجد اتصالات متفرقة بعيدة المدى للنزول التقريبي العام السريع. أثناء البحث، تبدأ الخوارزمية من نقطة دخول في المستوى الأعلى وتنزل عبر الهرمية، واختيار في كل خطوة الجيران الأقرب للاستعلام المستهدف. هذا مثل الملاحة في مدينة كبيرة: أولاً تسافر على الطرق السريعة الرئيسية، ثم تنتقل إلى الشوارع المحلية حتى تجد العنوان الذي تبحث عنه.

"يعمل HNSW مثل الملاح في مدينة غير مألوفة: تبدأ بالطرق السريعة الرئيسية، ثم تنزل إلى الشوارع المحلية"، كما يشرح مؤلفو المقالة على

Habr.

في الممارسة العملية، HNSW عادة ما يكون أسرع من IVF للبحث منخفض الكمون، لكنه يتطلب ذاكرة أكثر لتخزين هيكل الرسم البياني والاتصالات بين العقد.

ماذا يعني هذا

تُستخدم كلا الخوارزميتين في قواعس البيانات المتجهية الحديثة: Pinecone, Weaviate, Qdrant, Milvus. بالنسبة لتطبيقات LLM - أنظمة RAG، البحث في المستندات، التوصيات الدلالية، والدردشة الذكية - فإن اختيار خوارزمية البحث يؤثر بشكل مباشر على سرعة الاستجابة وتجربة المستخدم. من الأفضل اختيار IVF لقواعس البيانات الضخمة ذات الذاكرة المحدودة، HNSW يوفر ميزة عندما يكون الكمون الأدنى مطلوباً وعند العمل مع مجموعات بيانات أكثر إحكاماً.