عالم صغير قابل للتنقل هرميًا

خوارزمية العالم الصغير القابل للتنقل الهرمي ( HNSW ) هي خوارزمية للبحث التقريبي عن أقرب جار . تُستخدم هذه الخوارزمية للعثور على العناصر المشابهة لعنصر الاستعلام في مجموعة كبيرة، دون مقارنة الاستعلام بكل عنصر على حدة. ^{[ 1 ]}

تُستخدم هذه الخوارزمية عادةً للبحث في بيانات المتجهات . في هذه الأنظمة، يُمثَّل كل عنصر، مثل مستند أو صورة أو أغنية أو ملف تعريف مستخدم، بقائمة من الأرقام تُسمى متجهًا. تُعامل العناصر ذات المتجهات المتشابهة على أنها متشابهة وفقًا للنموذج الذي أنتج هذه المتجهات. يوفر نظام HNSW طريقةً للبحث السريع في هذه المتجهات، لا سيما في مجموعات البيانات الكبيرة.

يخزن HNSW المتجهات في رسم بياني . كل متجه هو عقدة ، وتربطه روابط ببعض المتجهات المجاورة. يتكون الرسم البياني من عدة طبقات: تحتوي الطبقات العليا على عدد أقل من العقد وتعمل كخريطة تقريبية، بينما تحتوي الطبقة السفلى على جميع العقد وتوفر عرضًا أكثر تفصيلًا. يبدأ البحث في طبقة عليا، ويتبع الروابط نحو العقد الأقرب إلى الاستعلام، ثم يكرر العملية في الطبقات السفلى حتى يعثر على مجموعة من أقرب الجيران المحتملين. ^{[ 1 ]}

تُعنى مسألة البحث عن أقرب جار بتحديد العناصر الأقرب إلى عنصر الاستعلام في مجموعة البيانات. يمكن للبحث المباشر مقارنة عنصر الاستعلام بكل عنصر في مجموعة البيانات، إلا أن هذه العملية تصبح بطيئة عند التعامل مع مجموعات بيانات كبيرة. كما أن طرق البحث الدقيق القائمة على الأشجار المكانية، مثل شجرة kd وشجرة R ، قد تصبح أقل فعالية مع البيانات عالية الأبعاد، وهي مشكلة غالباً ما تُعرف بلعنة الأبعاد .

تُضحي طرق الجوار الأقرب التقريبية ببعض الدقة مقابل السرعة أو تقليل استهلاك الموارد. فبدلاً من ضمان الحصول على العنصر الأقرب بدقة تامة، تسعى هذه الطرق إلى إرجاع العناصر القريبة بسرعة. ومن الطرق التقريبية الأخرى التجزئة الحساسة للموقع وتكميم المنتج . ^{[ 1 ]}

يستند مشروع HNSW إلى أبحاثٍ في شبكات العالم الصغير والرسوم البيانية القابلة للتصفح. في الرسم البياني ذي العالم الصغير، يمكن الوصول إلى معظم العقد من عقد أخرى عبر سلسلة قصيرة من الروابط. أما في الرسم البياني القابل للتصفح، فيمكن لعملية البحث استخدام المعلومات المحلية للوصول إلى الهدف. يُعدّ عمل جون كلاينبرغ حول التصفح في شبكات العالم الصغير مثالًا هامًا في هذا المجال البحثي. ^{[ 2 ]} وقد تناولت دراسات لاحقة طرقًا لإضافة روابط تُسهّل تصفح الرسوم البيانية بطريقة جشعة. ^{[ 3 ]}

تُوسّع خوارزمية HNSW أساليب البحث عن التشابه في العالم الصغير القابلة للتصفح، وذلك بإضافة تسلسل هرمي من طبقات الرسم البياني. يُساعد هذا التسلسل الهرمي الخوارزمية في إيجاد منطقة جيدة في الرسم البياني قبل إجراء بحث أكثر تفصيلاً في الطبقة السفلية. ^{[ 4 ]}

تعتمد خوارزمية HNSW على رسم بياني للتقارب. في هذا الرسم البياني، ترتبط المتجهات المتقاربة بحواف. تستخدم الخوارزمية هذه الحواف للتنقل عبر مجموعة البيانات ، بدلاً من مسح كل متجه على حدة.

الرسم البياني هرمي. يظهر كل متجه في الطبقة السفلية. كما توجد بعض المتجهات في طبقات أعلى، ويقل عدد المتجهات كلما ارتفعنا في الطبقات. تسمح الطبقات العليا بالحركة بعيدة المدى عبر مجموعة البيانات، بينما تسمح الطبقات السفلى ببحث أكثر تفصيلاً بالقرب من المرشحين الواعدين. ^{[ 1 ]}

تتم عملية البحث النموذجية على النحو التالي:

1. يبدأ البحث من نقطة دخول في الطبقة العليا.
2. في كل خطوة، تنظر الخوارزمية إلى العقد المجاورة وتنتقل إلى عقدة مجاورة أقرب إلى الاستعلام.
3. عندما لا يتمكن من العثور على جار أقرب في تلك الطبقة، فإنه ينتقل إلى الطبقة التالية.
4. في الطبقة السفلية، تستكشف مجموعة أوسع من العقد المرشحة وتعيد أقرب المرشحين الذين تم العثور عليهم.

تُوصف استراتيجية البحث هذه غالبًا بأنها ملاحة جشعة. تختار الخوارزمية بشكل متكرر العقد الأفضل محليًا، مستخدمة بنية الرسم البياني للوصول إلى نقطة الاستعلام.

يتم بناء مخطط HNSW بشكل تدريجي. عند إدخال متجه جديد، تقوم الخوارزمية بتعيين طبقة قصوى له، وتبحث عن العقد الموجودة القريبة، وتربط العقدة الجديدة بجيران محددين في كل طبقة تظهر فيها. ^{[ 1 ]}

عادةً ما تُتيح التطبيقات معلماتٍ تتحكم في المفاضلة بين السرعة والدقة واستخدام الذاكرة ووقت الإنشاء. يُمكن لزيادة عدد اتصالات الرسم البياني تحسين الاسترجاع، لكنها تتطلب ذاكرةً أكبر. كما يُمكن لقائمة مرشحي البحث الأكبر تحسين الدقة، لكنها تُبطئ الاستعلامات. في المقابل، يُمكن لقائمة مرشحي الإنشاء الأكبر تحسين جودة الرسم البياني، لكنها تُبطئ بناء الفهرس.

نظرًا لأن خوارزمية HNSW تقريبية، فإن نتائجها لا تتطابق دائمًا مع نتائج البحث الدقيق الكامل. ويعتمد أداؤها العملي على مجموعة البيانات، ومقياس المسافة، والتنفيذ، وإعدادات المعلمات. وقد أظهرت دراسات المقارنة المعيارية أن المكتبات القائمة على HNSW تتمتع بأداء قوي بين طرق الجوار الأقرب التقريبية، على الرغم من أن أداءها في أسوأ الحالات قد يختلف عن أدائها على مجموعات البيانات المعيارية الشائعة. ^{[ 5 ] [ 6 ]}

يُستخدم HNSW كفهرس في الأنظمة التي تخزن وتبحث في المتجهات عالية الأبعاد. تشمل هذه الأنظمة قواعد بيانات المتجهات، ومحركات البحث، وامتدادات قواعد البيانات. ومن الاستخدامات الشائعة البحث الدلالي ، وأنظمة التوصية ، والبحث عن تشابه الصور، والتوليد المُعزز بالاسترجاع .

تُطبّق العديد من مشاريع البرمجيات أو تدعم HNSW. تشمل المكتبات hnswlib، المرتبطة بمؤلفي HNSW الأصليين، و FAISS . ^{[ 7 ]} تشمل قواعد البيانات وأنظمة البحث التي توثّق دعم HNSW كلاً من Apache Lucene و Chroma و ClickHouse و DuckDB و MariaDB و Milvus و pgvector و Qdrant و Redis . ^{[ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ]}

• البحث عن أقرب جار تقريبًا
• قاعدة بيانات المتجهات
• التجزئة الحساسة للموقع
• تحديد كمية المنتج