فهرسة HNSW في قواعد بيانات المتجهات لتحسين الأداء

التحدي المتمثل في البحث في مجموعات البيانات الكبيرة

فهرسة لتسريع عمليات البحث

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

تستخدم قواعد البيانات التقليدية أساليب فهرسة مثل أشجار B وجداول التجزئة ، وهي مناسبة تمامًا لأنواع البيانات العددية. صُممت أساليب الفهرسة هذه لإجراء عمليات بحث فعالة عن التطابق التام والاستعلامات النطاقية. من ناحية أخرى، تستخدم قواعد بيانات المتجهات أساليب فهرسة متخصصة مُحسَّنة للمساحات عالية الأبعاد، مثل رسوم بيانية HNSW (العالم الصغير الهرمي القابل للتنقل) مالكوف، يو أ.، وديمتري أ. ياشونين. "بحث فعال وقوي عن أقرب جار تقريبي باستخدام رسوم بيانية هرمية قابلة للتنقل في العالم الصغير." معاملات IEEE في تحليل الأنماط والذكاء الآلي 42، العدد 4 (2018): 824-836. و أشجار KD KD_trees مع الأخذ في الاعتبار أن الطريقة الأخيرة هي الأنسب للاستخدام مع البيانات ذات الأبعاد المنخفضة إلى المتوسطة (حتى عشرة أبعاد). صُممت هذه الطرق للبحث عن التشابه، حيث يتمثل الهدف في إيجاد نقاط البيانات الأقرب إلى نقطة استعلام معينة في فضاء المتجهات. في هذا الدرس، سنتعمق في طريقة HNSW، وهي طريقة فهرسة متطورة تستخدمها العديد من قواعد بيانات المتجهات.

الرسم البياني الهرمي القابل للتنقل في العالم الصغير (HNSW)

تُعدّ رسوم HNSW البيانية هياكل بيانات متقدمة مصممة للبحث عن أقرب جار تقريبي (ANN). وهي تجمع بين مفاهيم الرسوم البيانية ذات العالم الصغير القابلة للتصفح وقوائم التخطي للبحث والتنقل بكفاءة في مجموعات البيانات الكبيرة.

رسم بياني للعالم الصغير قابل للتصفح (نيو ساوث ويلز)

تُعدّ رسوم بيانية العالم الصغير القابلة للتصفح (NSW) هياكل بيانات تُسهّل البحث والتصفح بكفاءة في مجموعات البيانات الكبيرة، وخاصةً في البحث باستخدام الشبكات العصبية الاصطناعية. ينبع مفهوم "العالم الصغير" في رسوم بيانية العالم الصغير القابلة للتصفح من "ظاهرة العالم الصغير" في نظرية الشبكات الاجتماعية، والتي تشير إلى ملاحظة إمكانية الوصول إلى معظم العقد في شبكة كبيرة من أي عقدة أخرى. العقدة تشير العقدة إلى شخص في سياق الشبكة الاجتماعية. أما في قواعد بيانات المتجهات، فتشير إلى متجه. من خلال عدد قليل نسبياً من الروابط الوسيطة. وقد شاع هذا المفهوم بفضل نظرية "ست درجات من التباعد" الشهيرة، والتي تشير إلى أن أي شخصين في العالم يفصل بينهما، في المتوسط، ست روابط اجتماعية فقط. واتس وستروغاتز واتس، دنكان جيه، وستيفن إتش. ستروغاتز. "الديناميكيات الجماعية لشبكات "العالم الصغير". الطبيعة 393، العدد 6684 (1998): 440-442. قام بإضفاء الطابع الرسمي على هذه الفرضية في نظرية الشبكات في عام 1998، مقدماً فكرة أن الشبكات في العالم الحقيقي غالباً ما يكون لها معاملات تجميع عالية وأطوال مسارات متوسطة قصيرة.

• يعني التكتل العالي أن العقد تتجمع بإحكام، ما يعني أنه إذا كانت ...