>

• الباحثون
   
• الملخص باللغة العربية
   
• الملخص باللغة الإنكليزية
   
• المقدمة
   
  
   
• دراسة مرجعية
   
• مواد البحث وطرائقه
   
• الخلاصة
   
• كلمات مفتاحية
   
• مراجع

م. علاء الدين زين
د. صلاح الدوه جي
د. محمد إياد الخياط

الملخص

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

up

       Abstract

Efficient processing of "Big Geospatial Data" requires the partitioning of the dataset to a number of partitions suitable for parallel processing paradigms. General "Big Data" processing frameworks lack the capability of effective partitioning when handling spatial data which drove researchers to develop new partitioning techniques based mainly on the use of spatial indexing instead of traditional indexing. This paper contains a technical review of spatial data partitioning techniques. The review aims at categorizing the techniques and offers a conceptual and mathematical description of a generic spatial partitioning technique. It defines criterion to evaluate performance. It also includes a definition of main objectives and parameters for a new design

up

     المقدمة:

البيانات الكبيرة أو الضخمة Big Data هي البيانات التي تصعب معالجتها باستخدام النظم المعلوماتية التقليدية بسبب حجمها الكبير Volume، أو الوتيرة العالية لانتاجها Velocity، أو الاختلاف الكبير في صيغها وأشكالها Veracity. تتطلب معالجة البيانات الكبيرة تعديلات تضمن قدرة النظام المعلوماتي من حيث التصميم والموارد الحاسوبية المادية (مثال: العناقيد الحاسوبية) والبرمجية (مثال: نماذج البرمجة التفرعية) على استيعاب هذا النوع من البيانات، وتصميم خوارزميات وبنى معطيات جديدة للتعامل معها.
تعرف البيانات المكانية (Geo)Spatial Data بأنها بيانات تصف مكان أوغرض أو كائن معين اعتماداً على الإحداثيات الجغرافية لتواجده باستخدام جملة إحداثيات مناسبة ونموذج رقمي للكرة الأرضية. تتضمن البيانات المكانية واصفات مكانية (نظام اسقاط، احداثيات، شكل هندسي)، وواصفات غير مكانية (ملاحظات وقياسات مرتبطة بالكائن). إن تحليل البيانات المكانية يختلف عن البيانات التقليدية من حيث استخدامه لوظائف تأخذ الموقع الجغرافي بعين الاعتبار مثل وظائف التقاطع والتماس والتجاور والاحتواء.
تهدف عملية تجزئة أو تقسيم البيانات Partitioning إلى تحويل مجموعة البيانات الكبيرة إلى مجموعة من الكتل التخزينية كإجراء تحضيري لتوزيع هذه البيانات على عدة عمليات برمجية تعمل بشكل تفرعي أو عدة نوى معالجات أو عُقد حاسوبية متصلة لتتم تنفيذ عمليات التحليل عليها بشكل تفرعي (على التوازي) مما يحقق تسريعاً في الأداء بالمقارنة مع نظم تحليل البيانات التقليدية، ويسمح بتحقيق استجابة للنظام ضمن القيود الزمنية المفروضة من التطبيق[1].
تتضمن هذه الورقة البحثية مراجعة للأعمال المتعلقة بتجزئة البيانات المكانية الكبيرة بهدف صياغة نموذج نظري مفاهيمي ووظائفي رياضي وبرمجي لمسألة التجزئة يمكن الاستفادة منه في توصيف وتصميم وبناء طرق جديدة، نظراً لعدم وجود هذا النموذج في الأعمال ذات الصلة. كما تستخدم نتائج الاختبارات التي تم إجراؤها في هذا السياق في استخلاص المحددات الأساسية المستخدمة في تقييم الأداء ومواصفات البيئية الحاسوبية المناسبة للاختبار. يستفيد البحث من الأعمال ذات الصلة في توصيف وتوضيح المحددات التصميمية و التقنية الأساسية لطرق التجزئة وسياق استخدامها والأدوات المطلوبة لتنجيز واختبار التوصيف النظري، وقياسات الأداء التي يمكن الاستفادة منها في التقييم.

up

 الدراسة المرجعية والأعمال ذات الصلة:

يتجاهل نظام Hadoop [2]وهو من أشهر نظم معالجة البيانات الكبيرة الخصائص المكانية للبيانات نظراً لاستخدامه طريقة تجزئة معتمدة على خوارزميات التهشير Hashing والتي تقوم بتقسيم البيانات إلى كتل متساوية في نظام الملفات الموزع HDFS [9] وهذا يسبب عدم الانتظام في توزيع البيانات نظراً لتوزعها الجغرافي مما يؤدي لعدم توازن في توزيع الحمل على مهمات المعالجة وزيادة في زمن الاستجابة.
تعتمد معظم نظم معالجة البيانات المكانية الكبيرة على ما يسمى بالفهرس المكاني Spatial Index كطريقة لفهرسة الكائنات المكانية قبل أن تتم تجزئتها وتوزيعها على مهام المعالجة التفرعية. تعتمد فكرة الفهرسة المكانية [3]على تجزئة الفضاء إلى قطاعات وتجزئة كل قطاع بشكل عودي واسناد معرف إلى كل كائن مكاني حسب القطاع الذي يقع الكائن جغرافياً ضمنه. هذا الإجراء يؤدي إلى تسريع عمليات الترتيب والاستعلام عن الكائنات المكانية نظراً لوقوع الكائنات المتقاربة جغرافياً ضمن نفس القطاع من الفهرس المكاني. تندرج طرق الفهرسة المكانية ضمن مجموعتين رئيسيتين الأولى هي الفهرسة المساقة بالفضاء Space Driven وفيها تتم تجزئة الفضاء بغض النظر عن الكائنات الموجودة في مجموعة البيانات ومن الأمثلة على الفهارس المساقة بالفضاء الفهرس Quad-Tree، والثانية هي الفهرسة المساقة بالبيانات Data Driven وفيها يتم بناء الفهرس بالاعتماد على الخصائص المكانية للكائنات الموجودة في مجموعة البيانات ومن الأمثلة على الفهارس المساقة بالبيانات الفهرس R-Tree.
نظام Hadoop-GIS [4]هو نظام تم تطويره لمعالجة البيانات المكانية الكبيرة بالاعتماد على إطار العمل Hadoop. الفكرة الأساسية للتجزئة في هذا النظام هي تقسيم البيانات مكانياً إلى كتل لتتم معالجتها بشكل تفرعي من خلال توزيع هوية فريدة لكل كائن مكاني ناتج عن عملية التجزئة (أي بناء فهرس) بعد ذلك القيام بالمعالجة التفرعية للبيانات. أما نظام SpatialHadoop [5] فهو إطار عمل متكامل مفتوح المصدر مبني على نموذج MapReduce مع دعم لبنى المعطيات والعمليات المكانية ليصبحHadoop قادراً على التعامل مع البيانات المكانية والفهارس المكانية من أجل تحقيق توزيع مناسب للبيانات على عقد المعالجة مع التقليل قدر الإمكان من عدم التوازن في الحمل. تتم تجزئة البيانات في SpatialHadoop باستخدام آلية مبنية على فهرسين عام ومحلي. الفهرس العامGlobal Index يقوم بفهرسة الأجزاء على مستوى الملف وتوزيعها على عقد المعالجة. أما الفهرس المحليLocal Index فيستخدم لتنظيم الكائنات داخل كل عقدة.  تم تقييم طرق التجزئة المختلفة المستخدمة في SpatialHadoop [15] والتي تعتمد أحد انواع الفهرسة المكانية الأساسية الثلاثة: الفهرسة المعتمدة على البيانات والفهرسة المعتمدة على تجزئة الفراغ والفهرسة المعتمدة على منحنيات ملء الفراغ حيث أظهرت النتائج تفوق الفهارس من النوعين R-tree, Quad-tree. ولتطوير عملية التجزئة في SpatialHadoop تم اقتراح طريقة جديدة تحاول التغلب على المشاكل الناجمة عن تمثيل الأشكال الهندسية بشكل مبسط كنقاط والتي تؤدي إلى نتائج غير دقيقة في الاستعلامات أو في إيجاد الجوار الأقرب [12].
تم تطوير إطار العمل Spark [19] لمعالجة البيانات الكبيرة. يتفوق Spark على Hadoop بشكل كبير في سرعة معالجة وتنفيذ الاستعلامات على البيانات الكبيرة. تتجاهل عملية تجزئة البيانات في Spark البعد المكاني للبيانات. ولمواجهة هذه المشكلة تم تطوير إطار العمل GeoSpark أو Apache Sedona  [6]والذي يقدم تطويراً لإطار العمل Spark من خلال إضافة بنية معطيات مكانية تستطيع تخزين كائنات من الشكل الهندسي النقطي أو المستقيم أو المضلع كما تسمح بتنفيذ العمليات والاستعلامات المكانية عليها. حيث يستخدم للتجزئة خوارزميات فهرسة مكانية مثل QuadTree و R-Tree . تأخذ عملية التجزئة بعين الاعتبار التوزع المكاني من أجل تجميع الكائنات المتجاورة في نفس القسم ما أمكن وهذا يسرع من عمليات الاستعلام من خلال تخفيض عمليات المعالجة غير الضرورية والمحافظة على التوازن في الحمل.
تستخدم معظم النظم التي تم تطويرها لمعالجة البيانات المكانية الكبيرة طرق ساكنة Static لتجزئة البيانات أي أنها لا تستجيب للتغيرات على مستوى البيانات و لذلك تم تطوير طرق تأخذ بعين الاعتبار الحمل الملقى على الاستعلام من حيث حجم الحسابات فعلى سبيل المثال يجب تنفيذ عملية التقسيم على البيانات التي يتم الاستعلام عنها بشكل مكثف بطريقة أكثر سرعة من باقي البيانات [11]. تم تطوير تابع تكلفة Cost function لمعرفة حجم الحمل على الاستعلام من حيث عدد النقاط وعمليات التجميع والتحصيل[14]. بما أن أهداف عملية التجزئة الأساسية هي الحصول على أجزاء تتضمن كائنات مكانية متجاورة وتوزيع الحمل بالتساوي على العقد، فإن هذه الأهداف تتناقض مع نموذج التكلفة المستخدم في الحوسبة السحابية ولذلك تم اقتراح طريقة جديدة لتجزئة البيانات المكانية بحيث كلما ازداد الحمل أو استخدام مخدم افتراضي معين تم تقليل عدد المخدمات التي تحمل نفس العبء مما يخفف التكاليف بشكل عام حيث تم البرهان على أن التكاليف قد انخفضت عند استخدام خدمة الحوسبة السحابية Amazon EC2 بنسبة 40%[10]. تم اقتراح حل لتجزئة البيانات معتمد على الترميز Coding [13] يتم الاستفادة من مجموعة البيانات في بناء مصفوفة تقسيم مكاني تأخذ بعين الاعتبار الرمز المكاني وحجم كتلة البيانات في نظام الملفات الموزع وتقوم بحساب هوية القسم لكل كائن مكاني. كما يمكن تنفيذ عملية التجزئة باستخدام فهرس هجين مكاني/نصي حيث يتم تمرير البيانات إلى مرحلة ما قبل المعالجة لاستخلاص الموقع الجغرافي والواصفة النصية ثم بناء فهارس ضمن الذاكرة اعتماداً على الواصفات المكانية والنصية[18].
يلعب انتظام توزيع مجموعة البيانات دوراً هاماً في تجزئة البيانات المكانية حيث أن البيانات الموزعة جغرافياً بشكل منتظم في الفراغ يمكن تجزئتها بطرق مختلفة عن البيانات التي تعاني من انحراف مكاني. يمكن اختيار طريقة التجزئة المناسبة في SpatialHadoop من خلال تقييم درجة انحراف مجموعة البيانات واستخدام أشجار القرار Decision Tree. وقد برهنت النتائج على صحة هذا الطرح [8]. كما تم استخدام الشبكات العصبونية ونظم التعلم العميق Deep Learning في اختيار الطريقة الأفضل للتجزئة في SpatialHadoop [16]حيث تم تدريب شبكة عصبونية لبناء نموذج للعلاقة بين طريقة توزيع البيانات المكانية ونوعية طريقة التجزئة المكانية المستخدمة ، ثم تم استخدام الشبكة للتنبؤ بطريقة التجزئة الأفضل من بين ستة طرق مختلفة. كما تم تطوير نظام خاص لبناء الطريقة المثالية لتجزئة البيانات يعتمد هذا النظام على بناء تابع تكلفة لجميع خطوات عملية التجزئة واستخدامه في اختيار المسار الأمثل للعملية [17].
من خلال مراجعة الأعمال السابقة نلاحظ أن التجزئة باستخدام الفهارس المكانية هي الحل المقترح لمعالجة نقاط الضعف الموجودة في طرق التجزئة المعتمدة في نظم معالجة البيانات الكبيرة مثل Hadoop,Spark. ولذلك أصبحت وظيفة بناء وتخزين الفهرس المكاني بأنواعه المختلفة مكوناً رئيسياً من مكونات أطر العمل التي تم تطويرها بهدف معالجة البيانات المكانية الكبيرة. إن استخدام الفهرس المكاني يجعل من زمن بناء الفهرس وسرعة الاستعلام عن بياناته محدد أساسي في زمن تنفيذ عملية التجزئة المكانية وبالتالي زمن الاستجابة الاجمالي للتطبيق. كما أن التجزئة باستخدام الفهارس المكانية يمكن ان تقود إلى توليد أجزاء ذات تباين عالي من حيث الحجم وكثافة الاستخدام مما يعيق تحقيق توازن الحمل في التنفيذ التفرعي للاستعلامات. كما أن إهمال الشكل الهندسي وطبيعته ودرجة تعقيده يسبب خلل في عمل خوارزميات التجزئة مما يستدعي اعتماد نظريات هندسية ورياضية وتطوير بنى معطيات جديدة من أجل معالجة البيانات المكانية. من العيوب الأساسية في عملية التجزئة المكانية المعتمدة على الفهرسة المكانية عدم أخذ الواصفات الموضوعية للكائنات بعين الاعتبار والتي قد تكون ذات تأثير هام في تسريع عملية التجزئة وجعلها أكثر فعالية. يمكن تلخيص المحددات الأساسية لعملية التجزئة المكانية الواردة بالجدول التالي:
الجدول (1) – محددات أساسية في عملية التجزئة المكانية
رقم    وصف المحدد
1    استخدام كامل مجموعة البيانات أو عينة فقط في عملية التجزئة
2    الترابط بين عملية التجزئة ودرجة التفرعية المتاحة في النظام
3    التجزئة ساكنة سابقة للاستعلام أو ديناميكية مرتبطة بحجم الحمل على الاستعلام وكثافة الوصول للكائن
4    أخذ الخصائص المكانية الذاتية للكائنات والترابط بين الخصائص بعين الاعتبار في التجزئة
5    استخدام الواصفات النصية والترميز المكاني إلى جانب الخصائص الجغرافية للكائن
6    توزيع الحمل بشكل متجانس على عقد المعالجة واستخدام قدرات المعالجات بشكل متوازن
إن زمن التنفيذ الإجمالي للتطبيق مع استخدام التجزئة المكانية ومقارنته مع زمن التنفيذ باستخدام النظم التقليدية لمعالجة البيانات الكبيرة والتي لا تستخدم التجزئة المكانية، والكفاءة في استخدام الموارد الحاسوبية من معالج وذاكرة وقرص وشبكة هما محددين أساسيين في تقييم أداء طريقة التجزئة المكانية.

up

 منهجية جديدة لبناء طريقة لتجزئة البيانات المكانية الكبيرة:

3.1 تحديد الأهداف
من خلال دراسة الأعمال ذات الصلة يمكن وضع الأهداف الرئيسية التالية لتجزئة البيانات المكانية الكبيرة:
- تجزئة مجموعة البيانات إلى عدة كتل من البيانات يمكن معالجتها بشكل تفرعي.
- الاستفادة من الواصفات المكانية لكائنات مجموعة البيانات في تنفيذ عملية التجزئة.
- تخزين البيانات المتجاورة جغرافياً في أجزاء متقاربة تخزينياً بغرض التقليل من استخدام الشبكة في تبادل البيانات.
- تحقيق توازن في حجم الكتل بحيث تكون متقاربة في الحجم تفادياً لزيادة العبء في عُقد حاسوبية معينة على حساب العُقد الأخرى.
- تنفيذ الاستعلامات المكانية على البيانات بسرعة أكبر مع الحفاظ على دقة نتائج لاستعلام.
- زيادة كفاءة استخدام الموارد الحاسوبية وفعالية الخوارزميات المكانية في الوصول إلى الأهداف المطلوبة من قبل التطبيق.
3.2 توصيف عام لعملية التجزئة المكانية
عملية التجزئة المكانية هي عملية يتم تنفيذها على مجموعة بيانات. يمتلك كل كائن من مجموعة البيانات واصفات مكانية متعلقة بالموقع الجغرافي والشكل الهندسي، وأخرى وصفية (قياسات وملاحظات متعلقة بالكائن). ينتج عن تنفيذ عملية التجزئة عدة مجموعات بيانات جزئية يحتوي كل منها مجموعة من الكائنات الموجودة في المجموعة الأساسية.
إن الحصول على أجزاء متوازنة يقتضي ان يكون عدد الكائنات أو عب المعالجة للكائنات موزعاً بشكل متوازن على مجموعات البيانات الجزئية. تعمل عملية التجزئة على توليد معرف خاص بكل كائن لتحديد الجزء أو مجموعة البيانات الجزئية التي سيتم ضم الكائن إليها وهذا يمكن تسميته بمخطط التجزئة Partitioning Scheme.
إن الشكل الهندسي ودرجة تعقيده والكفاءة في استخدام الفراغ الجغرافي يلعب دوراً في التجزئة المكانية، وبالتالي لا يمكن اعتبار عمليات التجزئة التي تستخدم طرق لا تعتمد على الفهرسة المكانية أو لا تأخذ بعين الاعتبار الواصفات المكانية من إحداثية وشكل هندسي أو الواصفات النصية المعبرة عن المكان من ضمن خوارزميات التجزئة المكانية بل هي خوارزميات للتجزئة التقليدية للبيانات.
تهدف عملية التجزئة المكانية إلى جعل الاستعلامات المكانية أكثر سرعة أي ان الوظائف الجغرافية مثل الاحتواء والتجاور والتداخل والتراكب يتم تنفيذها على مجموعة البيانات المجزأة بشكل أسرع من تنفيذها على مجموعة البيانات الأصلية مع شرط لازم وغير كافي هو الحفاظ على دقة وصحة النتائج. إن سرعة الاستعلام ودقة النتائج محددات أساسية لتقييم فعالية طريقة التجزئة. اما كفاءة عملية التجزئة فهي مرتبطة بحجم الموارد الحاسوبية المستهلكة في تنفيذ العملية مثل دورات المعالج وحجم الذاكرة وحجم التخزين على القرص وحجم استخدام الحزمة الشبكية.
3.3 نموذج رياضي لعملية التجزئة المكانية
لدينا مجموعة بيانات DS تحتوي على مجموعة من الكائنات المكانية SO المتجانسة من حيث الشكل الهندسي.
عدد الكائنات في مجموعة البيانات n
أو n=|DS|
حجم التخزين لكل كائن SO هو s
نستخدم الرمز SO=DSi للتعبير عن الكائن ذو الترتيب i في مجموعة البيانات.
يأخذ SO الشكل العام التالي:
SO= {x,y,z,geometry,crs│att1,att2…}
حيث تمثل x,y,z,geometry,crs الواصفات المكانية للكائن وatti مجموعة الواصفات غير المكانية (الواصفات الغرضية) للكائن. تهدف عملية تجزئة البيانات إلى تقسيم مجموعة البيانات إلى عدد من الأجزاء k يتضمن كل جزء عدد من الكائنات SO نعبر عن كل جزء بالرمز SubDSi
وبحيث يتحقق الشرط:
∀i ∈[1,k]:SubDSi ⊆DS
ويكون حجم كل جزء
n=|SubDSi|
لبناء عملية التجزئة يجب أن يتم توليد مجموعة من المعرفات الفريدة عددها k نعبر عنها بالرمز PartID بحيث يتحقق الشرط:
∀SO ∈SubDSi:SO.PartID= PartIDi
في التجزئة المكانية يتم توليد PartID باستخدام تابع للمتحولات الممثلة للواصفات المكانية:
PartID= f(SO.x,SO.y,SO.z,SO.Geometry)
في التجزئة المكانية المتوازنة تكون المجموعات الجزئية SubDS متساوية تقريباً من حيث عدد العناصر أو الحجم. أي أنه من أجل أي مجموعتين جزئيتين p,q يتحقق أحد أو كلا الشرطين التاليين:
الشرط الأول

الشرط الثاني:
|SubDSp|= |SubDSq|
نعبر عن عدد المهام التي يستطيع النظام تنفيذها في نفس الوقت بالرمز P من الممكن أن تمثل P عدد العمليات البرمجية التفرعية Processes أو عدد المسارات المتاحة في نواة المعالجة Threads أو عدد نوى المعالج Cores أو عدد العقد الحاسوبية المتصلة شبكياً في العنقود Cluster Nodes.
f:DS→{SubDSi}:i[1..k]& k=P
تأخذ التجزئة المكانية الديناميكية بعين الاعتبار حجم استخدام أو معدل الوصول إلى كائنات البيانات وبالتالي يتم استخدام بنية معطيات خاصة لتخزين احصاءات عن عدد مرات ونسبة ظهور كل كائن من مجموعة البيانات في نتائج الاستعلامات خلال فترة زمنية محددة يمكن ان تكون فترة سابقة أو في الزمن الحقيقي. حيث يمكن إضافة معامل للتعبير عن حجم الوصول إلى كائن معين.
Ui=(Count(SOi)) / (Total Count)
يمكن استخدام الحمل الحالي Work Load لكل
عقدة معالجة في لحظة زمنية معينة لتعريف تابع تكلفة Cost Function استخدامه في التجزئة المكانية الدينايميكة للبيانات.
WL(t,i):f(CPU,Memory,DiskIO,Network)
3.4 نموذج برمجي لعمية التجزئة المكانية
المتطلب الوظيفي الأساسي لعملية التجزئة المكانية هو قراءة مجموعة بيانات مكانية كبيرة وتخزينها في بنية معطيات مناسبة ثم تنفيذ طريقة للتجزئة لإنتاج معرفات فريدة تسمح بتجزئة مجموعة البيانات إلى مجموعات جزئية. يمثل الشكل (1) نموذج لطريقة عامة لتجزئة البيانات المكانية حيث يمكن بناء على هذا النموذج تصميم صف برمجي Class لتحقيق عملية التجزئة المكانية وفق شبه الترميز التالي:

 
الشكل (1) – مخطط طريقة عامة لتجزئة البيانات المكانية
 

يبين الشكل (2) نموذج عملي عن اعتماد النموذج البرمجي في بناء وظيفة للتجزئة المكانية ضمن بيئة Dask_Geopandas [20] للمعالجة التفرعية للبيانات المكانية الكبيرة بلغة Python كبديل لوظيفة التجزئة التقليدية المتوفرة مع البيئة للتحقق عن إمكانية استخدام النموذج في بناء تنفيذ عملية تجزئة مكانية ساكنة باستخدام فهرس مكانية لكامل مجموعة البيانات مع تحقيق الترابط بين عملية التجزئة ودرجة التفرعية المتاحة في النظام.
 
الشكل (2) – مثال عملي عن استخدام النموذج
3.5 تصميم بيئة الاختبار
يتطلب تقييم أداء طريقة التجزئة تنفيذ الاختبارات اللازمة للحصول على نتائج موثوقة تسمح باتخاذ القرار التصميمي الصحيح. يتطلب بناء بيئة الاختبار اختيار مجموعة البيانات Dataset ومواصفات النظام الحاسوبي والوظائف المستخدمة في الاختبار والقياسات الكمية والنوعية Metrics المطلوبة للتقييم.
يرتبط اختيار مجموعة البيانات المستخدمة في تنفيذ الاختبار بمجموعة من القرارات التصميمية نذكر منها:
- استخدام مجموعة بيانات حقيقية أو مجموعة بيانات مولدة حاسوبياً Synthetic.
- حجم مجموعة البيانات من حيث عدد السجلات أو من حيث حجم السجل الواحد وعادة ما يتم تنفيذ الاختبار على عدة مجموعات بيانات متجانسة من حيث البنية ومختلفة من حيث عدد السجلات.
- الشكل الهندسي للكائنات المخزنة في مجموعة البيانات (نقطة، مضلع)، ونموذج التوزيع الجغرافي والترابط المكاني الذاتي لكائنات مجموعة البيانات.
يجب أن يتمتع النظام الحاسوبي المستخدم في الاختبار بقابلية تنفيذ عدة عمليات على التوازي سواء كان ذلك على مستوى نوى المعالجات أو من خلال استخدام العنقود الحاسوبي. ويتضمن النظام الحاسوبي إلى جانب المكونات المادية، المكونات البرمجية التي تسمح بإدارة موارد النظام وجدولة وتوزيع المهام على المعالجات المتوفرة وإضافة وحذف العقد من العنقود. من الممكن أيضاً استخدام بيئة الحوسبة السحابية لتنفيذ الاختبارات المتعلقة بالبيانات المكانية.
أبرز العمليات المكانية المستخدمة في اختبار نظم معالجة البيانات المكانية هي استعلامات المجال الجغرافي Range Query واستعلامات الدمج المكاني Spatial Join واستعلامات إيجاد الجوار الأقرب Nearest Neighbor. أما بالنسبة لأكثر المقاييس الكمية والنوعية المستخدمة في تقييم الأداء فهي سرعة تنفيذ عملية التجزئة، وسرعة تنفيذ الاستعلام بعد تنفيذ التجزئة مقارنة بسرعة تنفيذه بدون التجزئة، وحجم استخدام الموارد من زمن المعالج والذاكرة وعمليات القراءة/الكتابة على الأقراص وحجم المرور الشبكي، والانحراف المعياري لتوزيع البيانات على الأجزاء ومن الممكن تطوير محددات نوعية جديدة تتضمن عدة قياسات كمية.

up

Reference

1, Mohammad Mahmud, Joshua Huang, Salman Salloum et al,2020,A Survey of Data Partitioning and Sampling Methods to Support Big Data Analysis, Big Data Mining and Analytics, 3(2): 85-101.
2, Hadoop,https://hadoop.apache.org, last accessed 08/06/2022
3, Claudia Dolci, Dante Salvini, Michael Schrattner, Robert Weibel,2010, Spatial Partitioning and Indexing, Information Technology Training Alliance (GITTA) http://www.gitta.info 8.11.2010
4,AblimitAji,FushengWang,HoangVo , Rubao Lee, Qiaoling Liu,XiaodongZhang,JoelSaltz,2013, Hadoop GIS: A High Performance Spatial DataWarehousing System over MapReduce,Proceedings of the VLDB Endowment 21508097/13/09, Vol. 6, No. 2013
5, Ahmed Eldawy, Mohamed F. Mokbel, SpatialHadoop: A MapReduce Framework for Spatial Data
6, Apache Sedona,https://Sedona.apache.org, last accessed 08/06/2022
7,Jia Yu, Jinxuan Wu, Mohamed Sarwat, GeoSpark: A Cluster Computing Framework forProcessing Spatial Data, NationalGeospatial-Intelligence Agency (NGA) Foresight Project
8, Alberto Belussi , Sara Migliorini and Ahmed Eldawy,2020,Skewness-Based Partitioning in SpatialHadoop,ISPRS Int. J. Geo-Inf. 2020, 9, 201; doi:10.3390/ijgi9040201
9, Nikolaos Niopas,2019,Benchmarking data partitioning techniques in HDFS for big real spatial data, University of Amsterdam
10, Afsin Akdogan,2015, Partitioning, Indexing and Querying Spatial Data on Cloud, A PhD Dissertation ,  Faculty of the USC graduate school  University of Southern California ,December 2015
11, Karen D. Devine, Erik G. Boman, George Karypis,2008, Partitioning and Load Balancing for Emerging Parallel Applications and Architectures, DOI: 10.1137/1.9780898718133.ch6
12, Ahmed Elashry, Abdulaziz Shehab, Alaa. M. Riad, Ahmed Aboul-fotouh, An Efficient Partitioning Technique in SpatialHadoop, IJICIS, Vol.18, No. 1
13, Xiaochuang Yao, Mohamed F. Mokbel, LouaiAlarabi, Ahmed Eldawy, Jianyu Yang,
Wenju Yun, Lin Li, Sijing Ye, Dehai Zhu,2017, Spatial coding-based approach for partitioning big spatial data in Hadoop, Elsevier Computers & Geosciences 106 (2017) 60–67 0098-3004/2017
14, Ahmed M. Aly, Ahmed R. Mahmood, Mohamed S. Hassan, Walid G. Aref, MouradOuzzani, HazemElmeleegy, ThamirQadah,2016, AQWA: Adaptive Query Workload Aware Partitioning of Big Spatial Data, . Proceedings of the VLDB Endowment, Vol. 8, No. 13, New Delhi,India
15, Ahmed EldawyLouaiAlarabi Mohamed F. Mokbel,2015, Spatial Partitioning Techniques in SpatialHadoop ,41st International Conference on VLDB,31/8 to 4/9 2015, Kohala Coast,Hawaii
16, Tin Vu,Alberto Belussi, Sara Migliorni, Ahmed Eldway,2020, Using Deep Learning for Big Spatial Data Partitioning , ACM Trans. Spatial Algorithms Syst., Vol. 1, No. 1, Article 1.  
17, Qifa Ke, Vijayan Prabhakaran, Yinglian Xie, Yuan Yu,Jingyue Wu, Junfeng Yang,2011, Optimizing Data Partitioning for Data-Parallel Computing,HotOS
18, Amr Magdy, Louai Alarabi, Saif Al-Harthi, Mashaal Musleh,Thanaa M. Ghanem, Sohaib Ghani, Mohamed F. Mokbel,2014, Taghreed: A System for Querying, Analyzing, and Visualizing Geotagged Microblogs, SIGSPATIAL ’14, November 04-07 2014, Dallas/Fort Worth, TX, USA
19, SPARK, spark.apache.org, Last accessed 12/06/2022
20,DASK_GEOPANDAS, https://github.com/geopandas/dask-geopandas, , Last accessed 16/08/2022

up