شجرة ذات موقع استراتيجي

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

يُطلق على أحد التعميمات اسم شجرة نقاط الرؤية المتعددة (أو شجرة MVP ): وهي بنية بيانات لفهرسة الكائنات من مساحات مترية كبيرة لاستعلامات البحث عن التشابه . وتستخدم أكثر من نقطة واحدة لتقسيم كل مستوى. ^{[ 2 ]}^{[ 3 ]}

تاريخ

ادّعى بيتر يانيلوس أن شجرة نقطة المراقبة اكتُشفت بشكل مستقل من قِبَله (بيتر يانيلوس) وجيفري أولمان . ^{[ 1 ]} مع ذلك، نشر أولمان هذه الطريقة قبل يانيلوس في عام 1991. ^{[ 4 ]} أطلق أولمان على بنية البيانات اسم " شجرة مترية" ، بينما اقترح يانيلوس اسم "شجرة نقطة المراقبة". وقد عُممت أشجار نقطة المراقبة لتشمل الفضاءات غير المترية باستخدام تباعد بريغمان بواسطة نيلسن وآخرون. ^{[ 5 ]}

تُشبه عملية التقسيم التكرارية هذه عملية تقسيم شجرة $k$ -d ، ولكنها تستخدم تقسيمات دائرية (أو كروية، أو فائقة الكروية، إلخ) بدلاً من التقسيمات المستقيمة. في الفضاء الإقليدي ثنائي الأبعاد، يمكن تصور ذلك على أنه سلسلة من الدوائر التي تفصل البيانات.

تُعد شجرة نقطة المراقبة مفيدة بشكل خاص في تقسيم البيانات في فضاء متري غير قياسي إلى شجرة مترية.

فهم شجرة نقاط المراقبة

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

البحث من خلال شجرة ذات موقع استراتيجي

يمكن استخدام شجرة نقاط المراقبة لإيجاد أقرب جار لنقطة $x$ . خوارزمية البحث تكرارية. في كل خطوة، نتعامل مع عقدة في الشجرة لها نقطة مراقبة $v$ ومسافة عتبة $t$ . تقع النقطة $x على مسافة معينة من نقطة المراقبة$ $v$ . إذا كانت هذه المسافة $d$ أقل من $t$ ، نستخدم الخوارزمية بشكل تكراري للبحث في الشجرة الفرعية للعقدة التي تحتوي على النقاط الأقرب إلى نقطة المراقبة من مسافة العتبة $t$ ؛ وإلا، ننتقل إلى الشجرة الفرعية للعقدة التي تحتوي على النقاط الأبعد عن نقطة المراقبة من مسافة العتبة $t$ . إذا وجد الاستخدام التكراري للخوارزمية نقطة مجاورة $n$ بمسافة إلى $x$ أقل من $| t - d |، فلا داعي للبحث في الشجرة الفرعية الأخرى لهذه العقدة؛ تُعاد العقدة$ $n$ المكتشفة . وإلا، يجب البحث في الشجرة الفرعية الأخرى بشكل تكراري أيضًا.

يُمكن اتباع نهج مماثل لإيجاد أقرب $k$ جار لنقطة $x$ . في التكرار، يتم البحث في الشجرة الفرعية الأخرى عن أقرب $k - k'$ جار للنقطة $x عندما يكون$ $k'$ فقط $(<$ $k$ $)$ من أقرب الجيران الذين تم العثور عليهم حتى الآن لديهم مسافة أقل من $| t - d |$ .

مزايا شجرة نقطة المراقبة

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

تعقيد

تبلغ تكلفة الوقت اللازم لبناء شجرة نقاط المراقبة تقريبًا $O (n log n)$ . لكل عنصر، يتم إنزال الشجرة بمقدار $log n$ مستوى للعثور على موقعه. ومع ذلك، يوجد عامل ثابت $k$ حيث $k$ هو عدد نقاط المراقبة لكل عقدة في الشجرة. ^{[ 3 ]}

تبلغ تكلفة الوقت اللازم للبحث في شجرة نقاط المراقبة للعثور على أقرب جار واحد $O (log n)$ . يوجد $log n$ مستوى، يتضمن كل منها $k$ عملية حسابية للمسافة، حيث $k$ هو عدد نقاط المراقبة (العناصر) في ذلك الموضع في الشجرة.

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

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

مع وجود $n نقطة$ $،$ يكون عدد المسافات بين كل زوج من النقاط $O (n²)$ . ومع ذلك، يتطلب إنشاء شجرة نقاط المراقبة حساب $O (n log n)$ مسافة فقط بشكل صريح، ويتطلب البحث حساب $O (log n)$ مسافة فقط. على سبيل المثال، إذا كانت $x$ و $y$ نقطتين، وكان معروفًا أن المسافة $d (x, y)$ صغيرة، فإن أي نقطة $z$ بعيدة عن $x$ ستكون بالضرورة بعيدة تقريبًا عن $y، لأن$ متباينة المثلث في الفضاء المتري تعطي $d (y, z) \geq d (x, z) - d (x, y)$ .

مراجع

1 2 يانيلوس (1993). هياكل البيانات والخوارزميات للبحث عن أقرب جار في الفضاءات المترية العامة . الندوة السنوية الرابعة لجمعية ACM-SIAM حول الخوارزميات المنفصلة. جمعية الرياضيات الصناعية والتطبيقية، فيلادلفيا، بنسلفانيا، الولايات المتحدة الأمريكية. الصفحات 311-321 .
↑ بوزكايا، تولغا؛ أوزسويوغلو، ميرال (سبتمبر 1999). "فهرسة المساحات المترية الكبيرة لاستعلامات البحث عن التشابه" . مجلة ACM لأنظمة قواعد البيانات . 24 (3): 361-404 . doi : 10.1145/328939.328959 . ISSN 0362-5915 . S2CID 6486308 .
1 2 3 برين، سيرجي (سبتمبر 1995). "البحث عن الجوار القريب في الفضاءات المترية الكبيرة" . وقائع مؤتمر VLDB '95، المؤتمر الدولي الحادي والعشرون لقواعد البيانات الكبيرة جدًا . زيورخ، سويسرا: دار مورغان كوفمان للنشر: 574-584 . ISBN 9781558603790.
↑ أولمان، جيفري (1991). "تلبية استعلامات التقارب/التشابه العامة باستخدام الأشجار المترية". رسائل معالجة المعلومات . 40 (4): 175-179 . doi : 10.1016/0020-0190(91)90074-r .
↑ نيلسن، فرانك (2009). "أشجار بريغمان لنقاط المراقبة لاستعلامات الجوار الأقرب الفعالة". وقائع المؤتمر الدولي للوسائط المتعددة والتجارب (ICME) . معهد مهندسي الكهرباء والإلكترونيات. الصفحات 878-881 .
1 2 3 4 5 فو، آدا واي تشي؛ بولي مي شوين تشان؛ ين لينغ تشيونغ؛ ييو سانغ مون (2000). "فهرسة شجرة vp الديناميكية للبحث عن أقرب $n$ جار مع مراعاة المسافات الزوجية" . مجلة VLDB - المجلة الدولية لقواعد البيانات الضخمة جدًا . سبرينغر-فيرلاغ نيويورك، سيكاوكوس، نيوجيرسي، الولايات المتحدة الأمريكية. الصفحات 154-173 . vp . تم الاسترجاع في 2 أكتوبر 2012 .

روابط خارجية

فهم أشجار VP

[pny93-1] 1 2 يانيلوس (1993). هياكل البيانات والخوارزميات للبحث عن أقرب جار في الفضاءات المترية العامة . الندوة السنوية الرابعة لجمعية ACM-SIAM حول الخوارزميات المنفصلة. جمعية الرياضيات الصناعية والتطبيقية، فيلادلفيا، بنسلفانيا، الولايات المتحدة الأمريكية. الصفحات 311-321 .

[2] بوزكايا، تولغا؛ أوزسويوغلو، ميرال (سبتمبر 1999). "فهرسة المساحات المترية الكبيرة لاستعلامات البحث عن التشابه" . مجلة ACM لأنظمة قواعد البيانات . 24 (3): 361-404 . doi : 10.1145/328939.328959 . ISSN 0362-5915 . S2CID 6486308 .

[brin-3] 1 2 3 برين، سيرجي (سبتمبر 1995). "البحث عن الجوار القريب في الفضاءات المترية الكبيرة" . وقائع مؤتمر VLDB '95، المؤتمر الدولي الحادي والعشرون لقواعد البيانات الكبيرة جدًا . زيورخ، سويسرا: دار مورغان كوفمان للنشر: 574-584 . ISBN 9781558603790.

[4] أولمان، جيفري (1991). "تلبية استعلامات التقارب/التشابه العامة باستخدام الأشجار المترية". رسائل معالجة المعلومات . 40 (4): 175-179 . doi : 10.1016/0020-0190(91)90074-r .

[nielsen2009-5] نيلسن، فرانك (2009). "أشجار بريغمان لنقاط المراقبة لاستعلامات الجوار الأقرب الفعالة". وقائع المؤتمر الدولي للوسائط المتعددة والتجارب (ICME) . معهد مهندسي الكهرباء والإلكترونيات. الصفحات 878-881 .

[vp-6] 1 2 3 4 5 فو، آدا واي تشي؛ بولي مي شوين تشان؛ ين لينغ تشيونغ؛ ييو سانغ مون (2000). "فهرسة شجرة vp الديناميكية للبحث عن أقرب $n$ جار مع مراعاة المسافات الزوجية" . مجلة VLDB - المجلة الدولية لقواعد البيانات الضخمة جدًا . سبرينغر-فيرلاغ نيويورك، سيكاوكوس، نيوجيرسي، الولايات المتحدة الأمريكية. الصفحات 154-173 . vp . تم الاسترجاع في 2 أكتوبر 2012 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]