HNSW Explorer: عالم صغير قابل للتنقل هرمي، مُصوَّر

شاهد مسار البحث عبر الرسم البياني متعدد الطبقات — من الطبقة العليا المتفرقة (الطرق السريعة) وصولاً إلى الطبقة السفلية الكثيفة (الطرق المحلية). اسحب نقطة الاستعلام في الطبقة 0 واضبط M / ef لمشاهدة كيف يتغير الرسم البياني.

الحد الأقصى لعدد الجيران لكل عقدة

ef8

مجموعة المرشحين من الطبقة 0

السرعة450ms

لكل خطوة

الخطوة الحالية

14 / 14

اكتمل البحث. Top-3: [3, 10, 4].

إحصائيات البحث

تمت زيارتها

17 / 30

الطبقات

المدخل

العقدة 0

Top-3

[3, 10, 4]

توزيع الطبقات

كيف يعمل كتاب « HNSW »

الرسم البياني الطبقي: يتم تعيين طبقة قصوى لكل عقدة عشوائيًا باستخدام توزيع أسي. توجد معظم العقد في الطبقة 0 فقط؛ وقليل جدًّا منها يصل إلى القمة.
داخل كل طبقة: ترتبط كل عقدة بأقرب جيرانها ( M ). الطبقات العليا متفرقة (عدد قليل من العقد، حواف طويلة = «الطرق السريعة»). الطبقة 0 كثيفة (جميع العقد، حواف قصيرة = «الطرق المحلية»).
يبدأ البحث من الأعلى: من نقطة دخول ثابتة، تتحرك بشراهة نحو الجار الأقرب إلى الاستعلام، وتكرر ذلك حتى لا يحدث أي تحسن.
انزل طبقة واحدة وكرر العملية: يصبح الموضع من الطبقة السابقة نقطة البداية لمسار الطبقة التالية. كل انخفاض يحسن النتيجة بحواف أكثر دقة.
الطبقة 0 مع « ef »: في الطبقة السفلية، بدلاً من التوقف عند أول حد أدنى محلي، يحافظ « HNSW » على مجموعة من ef أفضل المرشحين وتوسع مجالاتهم المجاورة. أكبر ef → أكثر دقةً لكن أبطأ.

لماذا هو سريع: تعمل الطبقات العليا كفهرس فوق الفهرس — فأنت تقطع مسافات شاسعة في بضع قفزات فقط، ثم تقوم بالتكبير. بالنسبة لـ N نقطة، يزور البحث ما يقارب O(log N) عقدة بدلاً من N.

ما هو « HNSW »؟

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

HNSW هو فهرس المتجهات الأكثر استخدامًا في الذاكرة، وهو فهرس الرسم البياني الافتراضي في Milvus. كما يقدم موقع Milvus HNSW_SQ و HNSW_PQ تقوم بتكمية المتجهات المخزنة لتقليل استهلاك الذاكرة بتكلفة بسيطة على الاسترجاع.

HNSW المعلمات في Milvus

M (وقت البناء): الحد الأقصى لعدد الحواف لكل عقدة، وهو نفس زر الضبط الموجود في شريط التمرير أعلاه. تتراوح القيم النموذجية بين 8 و64. يؤدي ارتفاع قيمة M إلى تحسين الاسترجاع واتصال الرسم البياني، ولكنه يزيد من استهلاك الذاكرة بشكل خطي ويبطئ عملية البناء.
efConstruction (وقت الإنشاء): حجم مجموعة المرشحين المستخدم أثناء إدراج العقد. تؤدي القيم الأعلى إلى إنشاء رسم بياني ذي جودة أفضل (استرجاع أعلى يمكن تحقيقه) على حساب بطء إنشاء الفهرس. تتراوح القيم النموذجية بين 100 و500.
ef / ef_search (وقت الاستعلام): مجموعة المرشحين التي يتم الاحتفاظ بها أثناء مسار الطبقة 0 — وهي أداة التحكم الرئيسية في الاسترجاع/الكمون في وقت البحث. يجب أن تكون على الأقل top-K. قم بزيادتها حتى يستقر الاسترجاع؛ حيث يزداد الكمون بشكل خطي تقريبًا معها.

HNSW vs IVF vs DiskANN

HNSW عادةً ما يوفر أفضل زمن استجابة للاستعلام مع دقة استرجاع عالية للبحث داخل الذاكرة — ولهذا السبب يُعد الخيار الافتراضي عندما تتناسب مجموعة البيانات (بالإضافة إلى الحمل الإضافي للرسم البياني) مع RAM. تكاليفه تتمثل في الذاكرة ووقت الإنشاء: يضيف الرسم البياني حملًا إضافيًا ملحوظًا لكل متجه، كما أن عمليات الإدراج تكون أبطأ من عملية تخصيص k-means في IVF. اختر IVF عندما تحتاج إلى إنشاء فهارس سريع أو تكمية مكثفة، و DiskANN عندما تكون مجموعة البيانات كبيرة جدًا بحيث لا تتسع لـ RAM ولكنك لا تزال بحاجة إلى استرجاع عالٍ.

الأسئلة المتكررة

ما الذي يتحكم فيه المعامل M في HNSW ؟

يحدد M عدد الحواف التي تحتفظ بها كل عقدة في كل طبقة. كلما زاد M، زادت ترابطية الرسم البياني — مما يؤدي إلى استرجاع أعلى وتوجيه أكثر قوة — لكن الذاكرة تزداد خطيًّا مع M، وتبطئ عملية إنشاء الفهرس. تغطي القيم بين 8 و64 معظم أحمال العمل؛ وتعد القيم بين 16 و32 النقطة المثلى الشائعة.

ما الفرق بين ef و efConstruction ؟

كلاهما يمثلان حجمي مجموعتي المرشحين، ويتم تطبيقهما في أوقات مختلفة. تُستخدم « efConstruction » أثناء إنشاء الفهرس: فهي تحدد مدى شمولية بحث كل عقدة مُدرجة عن الجيران، وبالتالي تتحكم في جودة الرسم البياني. تُستخدم « ef » (ef_search) في وقت الاستعلام: فهي تتحكم في مدى اتساع نطاق البحث في الطبقة صفر (Layer-0)، حيث تُوازن بين زمن الاستجابة ودقة الاسترجاع في كل استعلام.

ما مقدار الذاكرة التي يحتاجها فهرس « HNSW »؟

تقريبًا المتجهات الأولية بالإضافة إلى الرسم البياني: حوالي d × 4 بايت لكل متجه لبيانات float32، بالإضافة إلى ما يقارب M × 2 × 8 بايت من الحواف لكل عقدة. بالنسبة لعمليات النشر ذات الذاكرة المحدودة، يقدم موقع Milvus خدمات HNSW_SQ و HNSW_PQ ، التي تقوم بتكمية المتجهات المخزنة، أو DiskANN ، التي تنقل المتجهات الكاملة إلى SSD.

متى يجب عليّ استخدام « HNSW » بدلاً من « IVF »؟

استخدم « HNSW » عندما تكون أولوية زمن استجابة الاستعلام عند دقة استرجاع عالية، ويكون الفهرس متسعًا في الذاكرة — فعادةً ما يكون هو الخيار الأفضل في هذه الحالة. وافضل « IVF » عندما تعيد بناء الفهارس بشكل متكرر (عملية بناء أسرع بكثير)، أو عند دمجه مع تكمية « SQ8 » / «PQ » لتناسب ميزانية ذاكرة محدودة.

لمزيد من التفاصيل: اقرأ وثائق «HNSW » (معلمات الفهرس) لمعرفة معلمات الفهرس الدقيقة، أو راجع «Index Explained» (شرح الفهرس) للحصول على دليل القرار الكامل.