كيفية الترميز الجغرافي مليون نقطة على سبارك بطريقة سريعة؟

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

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

كمدخلات ، كان لدينا حوالي 100 أو 200 ألف نقطة عند المدخلات التي تكمن في كتلة Hadoop كجدول Hive. هذا هو توضيح حجم المهمة.

تم اختيار Spark في النهاية كأداة للمعالجة ، على الرغم من أننا في هذه العملية جربنا كلاً من MapReduce و Apache Crunch. لكن هذه قصة منفصلة ، ربما تستحق هذا المنصب.

حل مباشر مع وسائل بأسعار معقولة

بادئ ذي بدء ، حاولنا التعامل مع المشكلة ، إذا جاز التعبير. كأداة ، كان هناك خادم ArcGIS يوفر خدمة ROD للترميز الجغرافي العكسي. استخدامه بسيط للغاية ، ولهذا نقوم بإجراء طلب HTTP GET بعنوان URL التالي:

http://-url/GeocodeServer/reverseGeocode?<> 

من بين العديد من المعلمات ، يكفي تعيين الموقع = x ، y (الشيء الرئيسي هو عدم الخلط بين أيٍّ منها هو خط العرض وأي خط طول ؛). والآن لدينا بالفعل JSON مع النتائج: البلد ، المنطقة ، المدينة ، الشارع ، رقم المنزل. مثال من الوثائق:

 { "address": { "Match_addr": "Beeman's Redlands Pharmacy", "LongLabel": "Beeman's Redlands Pharmacy, 255 Terracina Blvd, Redlands, CA, 92373, USA", "ShortLabel": "Beeman's Redlands Pharmacy", "Addr_type": "POI", "Type": "Pharmacy", "PlaceName": "Beeman's Redlands Pharmacy", "AddNum": "255", "Address": "255 Terracina Blvd", "Block": "", "Sector": "", "Neighborhood": "South Redlands", "District": "", "City": "Redlands", "MetroArea": "Inland Empire", "Subregion": "San Bernardino County", "Region": "California", "Territory": "", "Postal": "92373", "PostalExt": "", "CountryCode": "USA" }, "location": { "x": -117.20558993392585, "y": 34.037880040538894, "spatialReference": { "wkid": 4326, "latestWkid": 4326 } } } 

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

للتحقق بسرعة من جودة الاستجابة ، يمكنك تقدير المسافة بين نقطة البداية في معلمات الطلب والنقطة المستلمة - موقع استجابة الخدمة.

يبدو أن كل شيء الآن سيكون على ما يرام. ولكن كان هناك. كان مثيل ArcGIS الخاص بنا بطيئًا جدًا ، وتم تخصيص الخادم لـ 4 مراكز ، وحوالي 8 غيغابايت من ذاكرة الوصول العشوائي. نتيجة لذلك ، يمكن للمهمة على الكتلة قراءة 200 ألف نقطة لدينا بسرعة كبيرة ، ولكن تعتمد على أداء REST و ArcGIS. والتكويد الجغرافي جميع النقاط استغرق ساعات. في الوقت نفسه ، خصصنا حوالي 8 مراكز فقط على Hadoop ، وقليلًا من الذاكرة ، ولكن نظرًا لأن تحميل خادم ArcGIS كان قريبًا من 100٪ لعدة ساعات ، فإن الموارد الإضافية في المجموعة لم تعطنا أي شيء.

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

التقريب الثاني ، ونحن نقدم ذاكرة التخزين المؤقت

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

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

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

حسنًا ، أخبرنا عميلنا في هذا الوقت ، إذا لم نتمكن من معرفة العناوين بشكل أسرع ، فهل يمكننا تحديد مدينة على الأقل بسرعة؟ وتناولنا ...

حل مبسط ، وتنفيذ Geomerty API

ماذا لدينا لتحديد المدينة؟ كان لدينا هندسة المناطق الروسية ، التقسيم الإداري الإقليمي ، تقريبا دقيقة لمناطق المدينة.

يمكنك أن تأخذ هذه البيانات على سبيل المثال هنا . ما هو هناك؟ هذه قاعدة بيانات للحدود الإدارية للاتحاد الروسي ، للمستويات من 2 (البلد) إلى 9 (المناطق الحضرية). التنسيق إما geojson أو CSV (بينما تكون الهندسة نفسها بتنسيق wkt). في المجموع ، قاعدة البيانات حوالي 20 ألف سجل.

بدا حل مبسط جديد للمشكلة كما يلي:

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

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

تحميل ADT

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

 kite-tools csv-schema admin_level_2.csv --class al --delimiter \; >adminLevel.avrs kite-tools create dataset:hive:/default/levelswkt -s adminLevel.avrs kite-tools csv-import admin_level_2.csv dataset:hive:/default/levelswkt --delimiter \; ... kite-tools csv-import admin_level_10.csv dataset:hive:/default/levelswkt --delimiter \; 

ماذا فعلنا هنا؟ قام الفريق الأول ببناء نظام Avro لـ csv ، والذي حددنا له بعض معلمات المخطط (الفئة ، في هذه الحالة) ، وفاصل حقل لـ CSV. بعد ذلك ، يجدر النظر إلى المخطط الذي تم الحصول عليه بأعينك ، ومن الممكن إجراء بعض التصحيحات ، لأن Kite لا ينظر في جميع سطور ملفنا ، ولكن في بعض العينات فقط ، لذلك يمكن أن يقوم في بعض الأحيان بافتراضات غير صحيحة حول نوع البيانات (رأيت ثلاثة أرقام - لقد رأيت ذلك العمود العددي ، ثم ذهب السطر).

حسنًا ، بناءً على المخطط ، نقوم بإنشاء مجموعة بيانات (هذا هو المصطلح العام Kite ، تعميم الجداول في Hive ، الجداول في HBase ، وشيء آخر). في هذه الحالة ، تكون قاعدة البيانات الافتراضية (بالنسبة لخلايا Hive فهي نفس قاعدة البيانات) ، و levelswkt هو اسم جدولنا.

حسنًا ، تقوم أحدث الأوامر بتحميل ملفات CSV إلى مجموعة البيانات الخاصة بنا. بعد اكتمال التنزيل بنجاح ، يمكنك بالفعل إكمال الطلب:

 select * from levelswkt; 

في مكان ما في هوى.

العمل مع الهندسة

للعمل مع الهندسة في Java ، اخترنا Esri Java Geometry API (مطور ArcGIS). من حيث المبدأ ، كان من الممكن اتخاذ أطر أخرى ، فهناك بعض الخيارات من Open Source ، على سبيل المثال ، JTS Topology Suite المعروفة أو Geotools .

المهمة الأولى تسمح لنا بالتعامل مع إطار آخر من نفس شركة Esri ، وتسمى Spatial Framework for Hadoop ، وعلى أساس الأول. في الواقع ، نحن بحاجة إلى ما يسمى SerDe منه ، وحدة إلغاء تسلسل التسلسل لـ Hive ، والذي يسمح لنا بتقديم مجموعة من ملفات geojson كجدول في Hive ، والتي يتم أخذ أعمدة منها من سمات geojson. وتصبح الهندسة نفسها عمودًا آخر (مع البيانات الثنائية). نتيجة لذلك ، لدينا جدول ، أحد أعمدةه هو هندسة منطقة معينة ، والباقي سماته (الاسم ، المستوى في ADT ، إلخ). هذا الجدول متاح لتطبيق Spark.

إذا قمنا بتحميل قاعدة البيانات بتنسيق CSV ، فلدينا عمود حيث تكون الأشكال الهندسية في شكل نص ، بتنسيق WKT . في هذه الحالة ، يمكن لـ Spark إنشاء كائن هندسي في وقت التشغيل باستخدام واجهة برمجة تطبيقات Geometry.

اخترنا تنسيق CSV (و WKT) ، لسبب واحد بسيط - كما يعلم الجميع ، تحتل روسيا على خريطة المنطقة بتنسيقات Chukotka تتجاوز 180 خط الطول. يحتوي تنسيق geojson على قيود - يجب أن تقتصر جميع المضلعات الموجودة داخله على 180 درجة ، ويجب قطع تلك المضلعات التي تعبر خط الطول 180 إلى جزأين على طوله. نتيجة لذلك ، عند استيراد الهندسة إلى واجهة برمجة تطبيقات الهندسة ، نحصل على كائن يقوم واجهة برمجة تطبيقات الهندسة (Geometry API) بتعريفه بشكل غير صحيح (Bounding Box) (مرفق المستطيل) للحدود الروسية. اتضح أن الجواب هو -180.180 في خط الطول. وهذا بالطبع ليس صحيحًا - في الواقع ، روسيا تأخذ حوالي 20 إلى -170 درجة. هذه مشكلة في واجهة برمجة تطبيقات الهندسة ، فقد تكون هذه المشكلة ثابتة بالفعل ، ولكن كان علينا حلها.

WKT لا يوجد لديه مثل هذه المشكلة. قد تسأل ، لماذا نحتاج إلى صندوق ملزمة؟ ثم سأقول ؛)

يبقى لحل مشكلة ما يسمى PIP ، نقطة في poligon. يمكن لـ Java Geometry API القيام بذلك مرة أخرى ، بالنسبة إلينا ، هندسة بسيطة من النوع Point ، ومضلع ثانٍ (Multipoligon) للمنطقة ، وواحد يحتوي على طريقة.

نتيجة لذلك ، بدا الحل الثاني ، وكذلك على الجبهة ، كما يلي: يقوم تطبيق Spark بتحميل ADT ، بما في ذلك الهندسة. تم بناء شيء مثل اسم الخريطة-> الهندسة منها (في الواقع أكثر تعقيدًا قليلاً ، نظرًا لأن ADTs مضمنة في بعضها البعض ، ونحن بحاجة للبحث فقط في تلك المستويات السفلية المضمنة في المستوى العلوي الموجود بالفعل. ونتيجة لذلك ، هناك نوع من شجرة الهندسة التي وفقا لبيانات المصدر لا تزال بحاجة إلى أن تبنى). ثم نقوم بإنشاء مجموعة بيانات Spark باستخدام نقاطنا ، ولكل نقطة نطبق UDF الخاص بنا ، والذي يتحقق من إدخال النقطة في جميع الأشكال الهندسية (في الشجرة).

تستغرق كتابة نسخة جديدة حوالي يوم عمل ، لأن إطار عمل المكاني لحزمة Hadoop تضمن أمثلة جيدة مباشرة لحل مهمة PIP (وإن كان ذلك باستخدام عدة وسائل أخرى).

نبدأ ، و ... أوه ، رعب ، شيء ما لم يصبح أسرع. مشاهدة مرة أخرى. حان الوقت للتفكير في التحسين.

تبسيط الحل ، QuadTree

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

فيما يلي وصف من الويكي .



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

لهذا ، شجرة رباعي مناسبة لنا. لحسن الحظ ، يتم تنفيذ كل شيء في نفس واجهة برمجة تطبيقات الهندسة (وغيرها الكثير).



يبدو الحل المستند إلى شجرة شيئًا مثل هذا:

1. تحميل ATD الهندسة
2. لكل هندسة نحدد مستطيل مرفق
3. وضعناها في QuadTree ، وحصلنا على المؤشر ردا
4. يتم تذكر الفهرس

بعد ذلك ، عند معالجة النقاط:

1. نسأل QuadTree أي من الأشكال الهندسية التي يعرفها قد تتضمن نقطة
2. الحصول على مؤشرات الهندسة
3. فقط بالنسبة لهم نحن نتحقق من الحدوث عن طريق حل مشكلة PIP

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

ملخص

إذن ماذا انتهى بنا المطاف؟ حصلنا على آلية الترميز الجغرافي العكسي التي تتوازى بشكل فعال مع مجموعة Hadoop ، والتي تحل مشكلتنا الأولية بـ 200 ألف نقطة في حوالي دقيقة. أي يمكننا بسهولة تطبيق هذا الحل على ملايين النقاط.

ما هي حدود هذا الحل؟ أولاً ، الأمر الواضح - يعتمد على بيانات ADT المتاحة لنا ، والتي قد لا تكون ذات صلة ب) تقتصر على روسيا فقط.

والثاني - لسنا قادرين على حل مشكلة الترميز الجغرافي العكسي لكائنات أخرى غير المضلعات المغلقة. وهذا يعني - للشوارع كذلك.

التنمية

ما الذي يمكن القيام به مع هذا؟

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

ما الذي يمكن عمله للشوارع والمنازل؟ من حيث المبدأ ، الشوارع في نفس OSM. ولكن هذه ليست هياكل مغلقة ، ولكن الخطوط. لتحديد أن النقطة "قريبة" من شارع معين ، سيتعين عليك إنشاء مضلع للشارع من نقاط متساوية الطول منه ، والتحقق مما إذا كانت قد دخلت فيه أم لا. نتيجة لذلك ، يتحول نوع من النقانق ... يبدو مثل هذا:



ما مدى قرب النقطة؟ هذه معلمة ، وتتوافق تقريبًا مع نصف القطر الذي يبحث فيه ArcGIS عن الكائنات ، والتي ذكرتها في البداية.

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

المشكلة الواضحة هي أنه من المستحيل حساب هذه المخازن المؤقتة المزعومة مسبقًا - حجمها معلمة للخدمة. يجب أن تكون مبنية على الطاير ، بعد أن حددنا المنطقة المطلوبة في المدينة ، واخترنا من قاعدة OSM الشوارع التي تمر عبر هذه المنطقة. ومع ذلك ، يمكن اختيار الشوارع مسبقًا.

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

بمعنى أنه يجب عليك أولاً إنشاء فهرس للنموذج "city city" -> قائمة بالمنازل التي تحتوي على روابط إلى الأشكال الهندسية ، وقائمة مشابهة لقائمة الشوارع.

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

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