در سال‌های اخیر چندین زمینه کاربردی نیاز به تجزیه و تحلیل حجم عظیمی از داده‌ها دارند و اغلب ابعاد مورد علاقه شامل ویژگی‌های فضایی است. از این رو، تلاش‌های بسیاری توسط محققین به پیاده‌سازی راه‌حل‌هایی برای انجام کارآمد چنین محاسباتی انجام شده است. پارادایم MapReduce همچنین با موفقیت برای پیاده سازی راه حل موازی برای آن دسته از عملیات فضایی که معمولاً برای انجام تجزیه و تحلیل داده های مکانی مورد نیاز هستند، استفاده شده است. به طور خاص، عملیات شناخته شده محدوده، اتصال فضایی و k -نزدیکترین همسایه در حال حاضر در بسیاری از چارچوب های MapReduce موجود است. به عنوان مثال، SpatialHadoop [ 1 ]، توسعه فضایی Apache Hadoop [ 2 ]]، همه این عملیات را در برخی موارد در انواع مختلف ارائه می دهد که می تواند با تکنیک های پارتیشن بندی مختلف که معمولاً استراتژی های نمایه سازی جهانی نامیده می شوند ترکیب شوند.

اصل اساسی پارادایم MapReduce تقسیم ورودی به تکه های مستقل (پارتیشن بندی مجموعه داده) است که بر روی آنها می توان همان عملیات را به صورت موازی انجام داد (فاز نقشه)، احتمالاً نتایج جزئی را در پایان در یک کار متوالی (فاز کاهش) ترکیب می کند. ). بنابراین، یکی از جنبه های اصلی که می تواند تأثیر زیادی بر اثربخشی اجرای موازی داشته باشد، پارتیشن بندی مجموعه داده ورودی است. یک استراتژی پارتیشن بندی خوب باید تکه های یکنواختی تولید کند تا از وظایف نقشه متعادل اطمینان حاصل شود، یعنی کارهایی که اجرای آنها باید کم و بیش به همان مقدار منابع برای پردازش نیاز داشته باشد.

بسیاری از فریم ورک‌های MapReduce، از جمله Hadoop، به طور بومی از یک روش پارتیشن بندی پیش‌فرض بر اساس اندازه داده پشتیبانی می‌کنند، یعنی در این مورد هدف تولید تکه‌هایی است که split نامیده می‌شوند و دارای اندازه تقریباً یکسان در بایت هستند. این تکنیک آسپتیک می تواند برای پردازش داده های سنتی (متن) موثر باشد، اما ممکن است بهترین انتخاب برای پارتیشن بندی داده های مکانی نباشد. در واقع، در مواردی که داده های ورودی باید با توجه به موقعیت مکانی آن هرس یا فیلتر شوند، عملکرد ضعیفی ایجاد می کند. برعکس، تکنیک‌های پارتیشن‌بندی مناسب‌تر می‌توانند رکوردهای فضایی مجاور را در پارتیشن‌های مختلف جدا کنند [ 3 ]، که به نفع تجزیه و تحلیل داده‌های بعدی است.

به همین دلیل، چندین روش پارتیشن بندی فضایی در پسوندهای خاص چارچوب های MapReduce به منظور تقسیم هندسه ها بر اساس ویژگی های فضایی آنها به دو بخش اجرا شده است. به عنوان مثال، شاخص‌های مبتنی بر یک شبکه منظم، درخت‌های چهارگانه و درخت‌های R در SpatialHadoop [ 4 ] موجود هستند و می‌توانند قبل از اجرای یک عملیات معین، برای پارتیشن بندی یک مجموعه داده اعمال شوند. با این حال، در این مقاله نشان می‌دهیم که همه تکنیک‌های پارتیشن بندی فضایی به یک شکل عمل نمی‌کنند و در موارد مختلف بهترین تکنیک برای استفاده می‌تواند با توجه به ویژگی‌های فضایی مجموعه‌های داده در دست تغییر کند و در نهایت عملیاتی که باید روی آن انجام شود. مجموعه داده های پارتیشن بندی شده

به عنوان اولین نمونه از نوع موضوعی که می خواهیم در این مقاله در نظر بگیریم، در جدول 1 نتایج اجرای اتصال توزیع شده (DJ) [ 5 ]، محدوده پرس و جو (RQ) و k را در SpatialHadoop نشان دادیم. -عملیات نزدیکترین همسایه ( k -NN) هنگامی که در موقعیت‌های مختلف اعمال می‌شود. موارد زیر را در نظر می گیریم:

• عملیات DJ روی دو مجموعه داده اعمال می شود که هر دو به طور یکنواخت توزیع شده اند. به ویژه، اولی (به عنوان D1UD) با استفاده از یک شبکه معمولی ( GR ) پارتیشن بندی می شود، در حالی که شبکه دوم (به عنوان نشان داده شده است D2UD) با استفاده از تکنیک های مختلف، یعنی شبکه منظم ( GR )، Quadtree ( QT ) و R-tree ( RT ) پارتیشن بندی شده است.
• عملیات DJ به یک مجموعه داده توزیع شده یکنواخت اعمال می شود (به عنوان D1Uن) و یک اریب (نشان داده شده است D2اسکدبلیو). به خصوص، D1Uندر حالی که با استفاده از یک شبکه معمولی پارتیشن بندی شده است D2Uنبا چندین تکنیک پارتیشن بندی ممکن پارتیشن بندی شده است.
• عملیات RQ به یک مجموعه داده اریب اعمال می شود ( D1اسکدبلیو) با چندین تکنیک پارتیشن بندی ممکن پارتیشن بندی شده است.
• عملیات k -NN به یک مجموعه داده اریب اعمال می شود ( D1اسکدبلیو) با چندین تکنیک پارتیشن بندی ممکن پارتیشن بندی شده است.

در جدول 1 ، ستون دوم تکنیک پارتیشن بندی اعمال شده را گزارش می کند، ستون سوم شامل کل زمان انجام عملیات بر حسب میلی ثانیه است، در حالی که ستون آخر برخی از آمار مربوط به وظایف نقشه را گزارش می دهد. به طور خاص، تعداد وظایف نقشه نمونه، میانگین زمان صرف شده توسط آنها و انحراف استاندارد نسبی (RSD) بین زمان‌های اجرای آنها را نشان می‌دهیم. مقدار RSD بیشتر به این معنی است که بین زمان اجرای وظایف مختلف نقشه تفاوت زیادی وجود دارد، در حالی که مقدار کمتر به این معنی است که اساساً برای تکمیل آنها زمان یکسانی می‌گیرد.

همانطور که انتظار می رود، زمانی که هر دو مجموعه داده به طور یکنواخت توزیع می شوند، زمان پاسخ DJ بدون توجه به شاخص استفاده شده مشابه است، در حالی که، زمانی که یک مجموعه داده توزیع شده اریب در نظر گرفته می شود، تفاوت ها قابل توجه است و در این مورد خاص به نفع R است. -درخت این عمدتاً به این دلیل است که وقتی توزیع کج است، تقسیم‌بندی هندسه‌ها بر اساس یک شبکه منظم شکاف‌های متعادلی ایجاد نمی‌کند (یعنی RSD حدود 90٪ است، در حالی که شاخص‌های Quadtree و R-tree عملکرد بهتری دارند. و تقسیم‌های متعادل‌تری ایجاد می‌کند (یعنی RSD حدود 28٪ برای درخت R است). رفتار مشابهی را می توان برای دو عملیات دیگر، RQ و KNN مشاهده کرد، جایی که دوباره تکنیک های پارتیشن بندی Quadtree و R-tree بهتر عمل می کنند. به خصوص، همچنین در این مورد بهترین تکنیک تکنیکی است که کمترین انحراف را بین زمان اجرای وظایف نقشه داشته باشد. بنابراین، می‌توانیم مشاهده کنیم که متعادل کردن هزینه وظایف نقشه برای بهره‌برداری مؤثر از پتانسیل موازی ارائه شده توسط یک چارچوب MapReduce بسیار مهم است.

هدف این مقاله ارائه راهی برای تشخیص آسان برخی نکات در مورد توزیع مجموعه داده و بر اساس آنها انتخاب روش پارتیشن بندی موثرتر برای اعمال است. به این ترتیب پارتیشن بندی عمدتا بر اساس ویژگی های فضایی هندسه های موجود در مجموعه داده خواهد بود و نه تنها بر اساس اندازه آن در بایت.

در ادبیات، تکنیک‌های آماری زیادی برای ارائه شرح خلاصه‌ای از مجموعه داده‌ها پیشنهاد شده‌اند. این توصیف کننده ها که اغلب طرح ها نامیده می شوند، برای سرعت بخشیدن به پردازش پرس و جو با ارائه پاسخ های تقریبی بر اساس آنها استفاده می شوند [ 6 ]. یکی از کاربردهای اصلی آنها در تجزیه و تحلیل داده های بزرگ فضایی می تواند تخمین گزینش پذیری برای عملیات اتصال باشد. می‌توانیم تکنیک‌های ترسیم مرتبط را به دو دسته اصلی طبقه‌بندی کنیم : روش‌های مبتنی بر نمونه‌برداری [ 1 ، 4 ، 7 ، 8 ] و روش‌های مبتنی بر هیستوگرام [ 9 ، 10 ]]. به طور کلی، روش های مبتنی بر هیستوگرام برای تخمین گزینش پذیری مکانی دقیق نشان داده شده است [ 11 ، 12 ].

این مقاله یک تکنیک جدید را پیشنهاد می‌کند که به صورت داخلی چندین هیستوگرام یکنواخت می‌سازد. با این حال، نیازی به ذخیره و نگهداری همه آنها نیست، زیرا آنها را در یک مدل رگرسیونی جمع می کند. مدل رگرسیون تنها دو عدد را تولید می کند که به عنوان شاخص توزیع مجموعه داده در فضای مرجع استفاده می شود. به طور خاص، تکنیک پیشنهادی مبتنی بر مفهوم شمارش جعبه است که برای اولین بار در مرجع [ 13 ] برای محاسبه بعد فراکتالی مجموعه داده‌ای از نقاط ارائه شد. رفتار تابع شمارش جعبه اندازه گیری شده در محدوده محدودی از مقادیر (نماینده سمت سلول شبکه) را می توان با قانون توان توصیف کرد و در مرجع [ 14 ] استفاده شد.] برای تخمین گزینش پذیری خود پیوستگی و پرس و جوی محدوده، سپس در مرجع [ 15 ] به پیوستگی فضایی در مجموعه داده های مجزا گسترش یافت. ما کاربرد آن را در زمینه داده‌های فضایی بزرگ به دلایل زیر پیشنهاد می‌کنیم: (i) یک تکنیک کارآمد برای تشخیص اطلاعات در مورد توزیع مجموعه داده است. (ii) فقط یک عدد تولید می کند که توزیع داده را مشخص می کند و نیازی به ذخیره سازه های کمکی مانند هیستوگرام ندارد. (iii) تابع شمارش جعبه را می توان به صورت موازی محاسبه کرد، زیرا یک هیستوگرام یکنواخت را محاسبه می کند که شمارش ها را ذخیره می کند و این می تواند به راحتی در MapReduce پیاده سازی شود.

سهم اصلی مقاله عبارتند از: (1) گسترش تابع شمارش جعبه به همه انواع هندسه. قبلاً فقط می‌توانست برای مجموعه‌ای از نقاط اعمال شود. (ب) تعریف یک الگوریتم MapReduce برای محاسبات کارآمد آن، احتمالاً بر روی نمونه‌ای از مجموعه داده در نظر گرفته شده. (iii) تعریف اکتشافی برای انتخاب بهترین تکنیک پارتیشن بندی برای یک مجموعه داده معین که توزیع آن با استفاده از تابع شمارش جعبه توصیف شده است. زیر مجموعه ای از این نتایج قبلاً در مرجع [ 16 ] ارائه شده است. به ویژه، این مقاله به طور قابل توجهی کار انجام شده در مرجع [ 16 ] را با ارائه:

(آ)

ارائه تحلیلی تابع شمارش جعبه همراه با چند مثال که رویکرد پیشنهادی را توجیه می کند ( بخش 3 )،

(ب)

شرح مفصلی از اجرای MapReduce از الگوریتم برای محاسبه نماهای قانون توان که تابع شمارش جعبه را مشخص می کند ( بخش 4 )،

(ج)

ارائه گسترده ای از اکتشافی پیشنهادی برای انتخاب تکنیک های پارتیشن بندی مناسب همراه با اثبات ویژگی های تعریف شده ( بخش 5 )،

(د)

مجموعه ای جامع از آزمایش ها بر روی مجموعه داده های واقعی و مصنوعی ( بخش 6 ) انجام شده است که شامل سه نوع عملیات است: اتصال فضایی، پرس و جوی محدوده و k- نزدیک ترین همسایه.

در این بخش، ویژگی اصلی اجرای MapReduce عملیات فضایی مانند اتصال فضایی، پرس و جوی محدوده و K-نزدیکترین همسایه را به همراه تکنیک پارتیشن بندی اصلی که معمولاً در سیستم های خوشه ای اختصاص داده شده به داده های مکانی مانند SpatialHadoop موجود است، خلاصه می کنیم.

با توجه به مطالعه موردی نشان داده شده در جدول 1 ، واضح است که یک روش آسان و کارآمد برای ارزیابی چولگی یک مجموعه داده فضایی می تواند برای انتخاب تکنیک پارتیشن بندی مناسب بسیار مهم باشد. این بخش تعریف تابع شمارش جعبه را ارائه می دهد بسیDq(r)برای یک مجموعه داده معین D حاوی هندسه های دوبعدی از نوع نقطه، خط یا چندضلعی که در صفحه اقلیدسی تعبیه شده است. این اولین مشارکت مقاله است، زیرا توسعه تابع شمارش جعبه پیشنهاد شده در مرجع [ 14 ] است که در اصل فقط برای مجموعه محدودی از نقاط کاربرد دارد. پیامدهای چنین گسترشی بر صحت تخمین مورد بحث قرار گرفته و جایگزین‌های احتمالی ارزیابی می‌شوند. بعداً خواهیم دید که چگونه تجزیه و تحلیل این تابع می تواند نکاتی در مورد چولگی مجموعه داده ارائه دهد.

در مرجع [ 14 ] نویسنده نشان می دهد که تابع شمارش جعبه برای محاسبه بعد فراکتال تعمیم یافته مجموعه محدودی از نقاط مفید است، جایی که q نشان دهنده توان در معادله ( 1 ) و r مقیاس در نظر گرفته شده است (یعنی سلول). سمت شبکه). به طور مستقیم، با توجه به شبکه ای با سلول های سمت r ، تابع شمارش جعبه با q=0پیشنهاد شده در مرجع [ 14 ] تعداد سلول هایی را می شمارد که حداقل با یک نقطه از D قطع شده اند، به طور مشابه در اینجا تابع بسیD0(r)تعداد سلول هایی را می شمارد که حداقل با یک هندسه D قطع می شوند. به این ترتیب، وقتی توان های q بزرگتر از 1 باشد، جعبه شمارش مجموع تعداد هندسه هایی است که یک سلول را به q قطع می کنند. همانطور که نشان خواهیم داد، این تابع می تواند برای تشخیص چولگی یک مجموعه داده با محاسبه آن استفاده شود q=0و q=2در حالی که مقدار r را تغییر می دهد . به طور خاص تر، سطح چولگی یک مجموعه داده به نحوه تغییر این مقدار در حین افزایش r بستگی دارد .

توجه داشته باشید که با توجه به تعریف ارائه شده در مرجع [ 14 ]، که فقط برای مجموعه نقاط اعمال می شود و تعداد نقاط موجود در یک سلول را می شمارد، در تعریف 1 پیشنهاد می کنیم تعداد هندسه هایی را که یک سلول را قطع می کنند، بشماریم. این گسترش تابع شمارش جعبه از مجموعه نقاط به هندسه های عمومی را می توان به سه روش به دست آورد، همانطور که در زیر مورد بحث قرار می گیرد.

(من)

اولین گزینه می تواند انتخاب یک نقطه نماینده برای هر هندسه مجموعه داده (مثلاً مرکز آن) و سپس اعمال تابع شمارش جعبه کلاسیک باشد. این می تواند ساده ترین راه حل باشد، اما تضمین نمی کند که همیشه رفتار واقعی مجموعه داده را تشخیص دهد. به عنوان مثال این مورد در مورد مجموعه داده ای است که شامل مجموعه ای از چند ضلعی های بزرگ است که کل فضای مرجع را پوشش می دهد، اگر آنها با مرکز آنها تقریب شوند، نقاط حاصل همه در یک منطقه کوچک از همان فضا جمع می شوند، بنابراین مجموعه نقطه ای تولید می شود که به هیچ وجه طرح داده اصلی را توصیف نمی کند.

(II)

راه حل دیگر می تواند جایگزینی هندسه ها با رئوس آنها باشد. باز هم، ممکن است مناطقی با هندسه‌هایی پوشیده شده باشند که توسط رئوس آنها پوشیده نشده‌اند، با همان اثری که در مورد قبلی توضیح داده شد.

(iii)

آخرین راه حلی است که توسط این مقاله اتخاذ شده است، یعنی شمارش تعداد هندسه هایی که یک سلول را قطع می کنند، که معادل فرض این است که هر هندسه g در مجموعه ای از نقاط تبدیل شده است. پ(g)پوشاندن همان فضا با دانه بندی که فرضیه زیر را برآورده می کند: اگر g یک سلول i را قطع کند، حداقل یک نقطه وجود دارد. پ∈پ(g) به طوری که p سلول i را قطع می کند. با این فرضیه، می‌توانیم تابع شمارش جعبه را از مجموعه‌های نقطه‌ای به مجموعه‌ای از هندسه‌ها گسترش دهیم و نتایج مرجع [ 14 ] را در مورد خود اعمال کنیم. توجه داشته باشید که حتی اگر این راه حل بتواند یک تخمین بیش از حد برای انتخابی ایجاد کند، برای مسئله در نظر گرفته شده در این مقاله، یعنی تخمین توزیع مجموعه داده، اثرات منفی ندارد، برعکس به نتیجه دقیق تری منجر می شود.

همانطور که در مثال 1 خواهیم دید، نمودار شمارش جعبه برای محاسبه توان حیاتی است. Eqبرای یک مجموعه داده داده شده D ، زیرا این توان به شیب خط مستقیمی تبدیل می شود که تقریبی بسیDq(r)در طیفی از مقیاس ها (r1،r2)، بنابراین می توان آن را با روش رگرسیون خطی محاسبه کرد. توان Eqتوزیع مجموعه داده را همانطور که با مجموعه خصوصیات زیر توضیح داده شده است، مشخص می کند.

• برای q=0، E0منفی است و قانون توان، با توجه به طول ضلع سلول r ، تعداد سلول هایی را که با مجموعه داده D قطع می شوند محاسبه می کند . توجه داشته باشید که اگر D به طور یکنواخت در فضای مرجع توزیع شود (صفحه اقلیدسی در مورد ما)، آنگاه تعداد سلول هایی که D را قطع می کنند با تعداد کل سلول های شبکه منطبق است، بنابراین هر چه r بیشتر افزایش یابد، این عدد کاهش می یابد. به ناحیه سلول ها در نتیجه در صورت توزیع یکنواخت، E0در مورد ما برابر با منهای بعد فضای جاسازی است E0=-2.
• برای مجموعه داده‌هایی که فراکتال‌ها را نشان می‌دهند (مانند مثلث Sierpinski)، از این نظریه مشخص است که Eqمنطبق بر ابعاد فراکتال فرکتال برای هر q است (این نتیجه خاصیت مشابهت خود است)، بنابراین برای مثلث سیرپینسکی E0=-1.585.
• در نهایت، ما می توانیم آن را مشاهده کنیم E0و E2می تواند به عنوان توصیف کننده مرجع برای مجموعه داده D با هدف داشتن نکاتی در مورد توزیع هندسه ها در فضای مرجع D انتخاب شود. در واقع، E0می تواند نشانگر مواردی باشد که مجموعه داده برخی از مناطق فضای مرجع را خالی می گذارد، در حالی که E2همچنین می تواند تحت تأثیر تمرکز مجموعه داده ها در برخی مناطق نسبت به مناطق دیگر قرار گیرد، یعنی موقعیت هایی که در آن مناطق خالی وجود ندارد، اما غلظت های متفاوت در مناطق مختلف وجود دارد.

به منظور استفاده عملی E0و E2به عنوان شاخص های توزیع برای مجموعه داده های واقعی، یافتن راه آسان و کارآمد برای محاسبه آنها با توجه به مجموعه داده D ضروری است. بخش بعدی پیاده سازی MapReduce را در SpatialHadoop یک الگوریتم برای محاسبات کارآمد ارائه می کند. E0و E2.

این بخش سهم دوم مقاله، یعنی یک الگوریتم MapReduce برای محاسبه توان ها را ارائه می کند. E0و E2از قوانین قدرت معرفی شده در معادله ( 2 ). در فضایی فضایی پیاده‌سازی شد، بنابراین برخی از توابع فضایی اساسی در سیستم هدف در دسترس هستند.

با توجه به مجموعه داده‌ای D که شامل هندسه‌هایی از انواع مختلف است، نماهای مورد نیاز را می‌توان با محاسبه ابتدا تابع شمارش جعبه به دست آورد. بسیDq(r)برای مقادیر مختلف r ، و سپس با استفاده از رگرسیون خطی برای تعیین شیب خط نشان دهنده نمودار بسیDq(r)همانطور که در شکل 1 نشان داده شده است. چنین شیب برابر با پارامتر است Eqکه باید تخمین بزنیم نتیجه این است که هدف اصلی محاسبه نمودار شمارش جعبه D برای است بسیD0(r)و بسیD2(r); رگرسیون خطی متوالی را می توان در زمان ثابت اعمال کرد، زیرا نمودارهای محاسبه شده همیشه دارای همان تعداد جفت خواهند بود. (لog(r)،لog(بسیD0(r))(یا (لog(r)،لog(بسیD2(r))).

برای محاسبه نمودارهای شمارش جعبه مورد نیاز، باید فضای مرجع D را بدانیم که با MBR آن نشان داده می شود. کاربر می تواند از قبل این MBR را بشناسد، بنابراین آن را به عنوان یک پارامتر ارسال می کند، یا ممکن است ناشناخته باشد. در مورد دوم، یک کار مقدماتی MapReduce را می توان برای محاسبه آن انجام داد، برای مثال با فراخوانی متد FILEMBR() SpatialHadoop. با توجه به MBR از D ، اکنون لازم است فهرستی از شبکه ها انتخاب شود (جی1،…،جیn)با افزایش اندازه سلول r1،…،rn، برای محاسبه سری استفاده می شود (r1،بسیD0(r1)،…)و (r1،بسیD2(r1)،…). راحت‌ترین انتخاب برای شبکه‌ها، انتخابی است که می‌تواند تولید نمودارهای شمارش جعبه با مقادیر توزیع شده همگن در مقیاس لگاریتمی را تضمین کند. بنابراین، شروع از یک مقدار r0، در هر مرحله i ما را استخراج می کنیم rمنمقادیر با ضرب rمن-1توسط 2. اولیه r0طوری انتخاب شده است که rnکمتر از سمت MBR است (برای ساده کردن ارائه، در اینجا فرض می کنیم که MBR مربع است) و حداقل تعداد شبکه می تواند تولید شود.

در روش MapReduce، هر کار نقشه یک تقسیم از D را پردازش می‌کند و برای هر هندسه g از تقسیم، سلول‌های شبکه دقیق‌تر را مشخص می‌کند. grمند0که آن را قطع می کند. تعداد هندسه هایی را که توسط هر سلول قطع شده است، شمارش می کند grمند0و در پایان مجموعه ای از جفت ها را می نویسد 〈من،پمن(D)〉، جایی که من سلول را مشخص می کند grمند0، در حالی که پمن(D)تعداد هندسه هایی است که در D سلول i را قطع می کنند. توجه داشته باشید که در این مرحله به دلیل مقدار، چنین شماری را به توان q افزایش نمی دهیمپمن(D)نهایی نیست زیرا باید با نتایج سایر وظایف نقشه در طول مرحله کاهش بعدی ادغام شود.

وظیفه نقشه در الگوریتم 1 ارائه شده است. شبکه دقیق تر grمند0در روش SETUP() (خط 4) تولید می شود. علاوه بر این، یک نقشه هش بجoتوnتی0ایجاد شده است (خط 5) که تعداد (فقط) سلول های خالی را ذخیره می کند grمند0. به این ترتیب ما از ذخیره کردن تمام سلول های آن جلوگیری می کنیم grمند0. در روش MAP() (خطوط 6-9)، برای هر هندسه ورودی gهoمتر، کارکرد grمند0.منnتیهrسهجتیس(gهoمتر)اجرا می شود (خط 7). این تابع فهرستی از شناسه‌ها را برمی‌گرداند که سلول‌های آن را نشان می‌دهند grمند0متقاطع شده توسط gهoمتر. در نهایت، برای هر یک از این سلول ها جj، نقشه هش بجoتوnتی0به روز شده است (خط 9). در روش CLEANUP() (خطوط 10-12)، محتوای بجoتوnتی0روی دیسک نوشته شده است که ورودی وظیفه کاهش پی در پی را تولید می کند.

الگوریتم 1: وظیفه نقشه

پیچیدگی هر کار نقشه است O(نسپلمنتی)، جایی که نسپلمنتیمیانگین تعداد هندسه های D در هر تقسیم است.

شبه کد وظیفه کاهش در الگوریتم 2 ارائه شده است. توجه داشته باشید که روش SETUP() آن لیستی از شبکه ها را تولید می کند. grمندسو لیست مربوطه از جداول هش بجoتوnتیس. شبکه ها از یک سمت سلول اولیه شروع می شوند r0، در حالی که متوالی است rمنمقادیر با ضرب به دست می آیند rمن-1توسط 2.

الگوریتم 2: کاهش کار

متد ()REDUCE نتایج جزئی تولید شده توسط وظایف نقشه را به عنوان ورودی دریافت می کند. به طور خاص، برای هر سلول جjاز grمند0لیستی از شمارش جزئی را دریافت می کند جjتوسط وظایف مختلف نقشه محاسبه می شود. بنابراین، در ابتدا این تعداد را جمع می کند و تعداد کل آن را تولید می کند (خط 13). این مقادیر کل در نقشه هش ذخیره می شوند بج0(خط 16). از همان مقادیر کل برای به روز رسانی سلول های شبکه های دیگر استفاده می شود جj(خط 20)، به طوری که هر نقشه هش بجمنرا می توان در طول همان تکرار پر کرد.

در متد CLEANUP() سری (r1،بسیD0(r1)،…)و (r1،بسیD2(r1)،…)با شروع از نقشه های هش محاسبه می شوند بجمن(خطوط 23-30). در نهایت، دامنه های نشان دهنده E0و E2با استفاده از روش محاسبه می شوند rهgrهسسمنonاسلoپه(خطوط 31-32). در این مرحله در صورت لزوم می توان محدوده مقیاس ها را در برخی فواصل تقسیم کرد تا شیب ثابتی به دست آید.

پیچیدگی هر وظیفه کاهش است O(nجهلل+ngrمند)، جایی که nجهللنشان دهنده تعداد کل سلول های grمند0با مجموعه داده D قطع می شود ، در حالی که ngrمند=∣grمندس∣.

جدول 3 نتایج به کارگیری کار MapReduce پیشنهادی را برای مجموعه داده های مصنوعی و واقعی نشان می دهد. ستون اول مجموعه داده را از نظر توزیع و تعداد هندسه ها (یعنی کاردینالیته) توصیف می کند، در حالی که ستون دوم زمان مصرف شده را بر حسب میلی ثانیه گزارش می دهد و ستون آخر حاوی مقادیر به دست آمده است.

با توجه به روش MapReduce که در بخش قبل نشان داده شد، اکنون زمان آن است که معیارهایی را برای انتخاب تکنیک پارتیشن بندی مناسب بر اساس مقادیر محاسبه شده معرفی کنیم. به طور خاص، ما باید معیارهایی را برای ارزیابی کیفیت تکنیک های پارتیشن بندی با توجه به عملیاتی که می خواهیم بر روی مجموعه داده های نمایه شده انجام دهیم، معرفی کنیم. با در نظر گرفتن اتصال فضایی، پرس و جوی محدوده و k -nn، ما دو توصیفگر کیفیت را تعریف می کنیم که برای بهبود اثربخشی یک شاخص روی مجموعه داده D باید حداقل شوند .

• د1(D): %RDS (انحراف استاندارد نسبی با توجه به میانگین) کاردینالیته تقسیم (یعنی تعداد هندسه ها).
• د2(D): درصد فضای مرجع تحت پوشش شبکه که فضای مرده را نشان می دهد، یعنی فضایی که داده ای ندارد.

توجه کنید که، د1بر هزینه یک تکلیف نقشه تاثیر می گذارد، در حالی که د2بر تعداد کل وظایف نقشه که باید توسط عملیات مورد نظر نمونه برداری شوند، تأثیر دارد.

اجازه دهید دوباره پارتیشن‌هایی را که با استفاده از تکنیک‌های نشان‌داده‌شده در بخش 2 در مجموعه داده‌های مصنوعی و واقعی، و به‌ویژه شبکه‌های به‌دست‌آمده در جدول 2 نشان داده شده‌اند، در نظر بگیریم . برای هر یک از آنها جدول 3 مقادیر محاسبه شده را گزارش می کند E0و E2. چنین نتایج به دست آمده توانایی E0و E2در تشخیص مواردی که به تکنیک های پارتیشن بندی مختلف نیاز دارند. در واقع، برای توزیع یکنواخت ( E0∼-2.0و E2∼2.0) پارتیشن های به دست آمده برای همه تکنیک ها بسیار شبیه هستند. در این حالت شبکه معمولی می تواند بهترین انتخاب باشد، زیرا هزینه ایجاد آن کمتر است. برای مورب با بافر ( E0∼-1.0و E2∼1.0) شبکه های مبتنی بر Quadtree و Rtree به بهترین وجه با توزیع داده تطبیق می یابند. با این حال، پارتیشن بندی تولید شده توسط شبکه مبتنی بر Rtree دارای سلول های متعادل تری در پارتیشن مبتنی بر Quadtree از نظر تعداد هندسه در هر سلول است. در نهایت، وقتی یک مجموعه داده خوشه‌ای در نظر گرفته می‌شود ( E0∼0.0و E2∼0.0ما بهترین پارتیشن بندی را با شبکه مبتنی بر Quadtree به دست می آوریم، در حالی که شبکه مبتنی بر Rtree پارتیشنی با فضای مرده زیادی تولید می کند.

در این مرحله ایده بهره برداری است E0و E2به منظور انتخاب شبکه مناسب برای پارتیشن بندی داده ها، بدون ساخت انواع شاخص ها. این هدف را می توان به لطف ویژگی های زیر به دست آورد E0و E2.

اکنون برخی از مشاهدات تجربی را به ویژگی های رسمی ارائه شده در بالا اضافه می کنیم. با توجه به مجموعه داده D :

• وقتی محاسبه شد E0همین اطراف است 1.0، سپس مجموعه داده کج شده است، مقداری فضای مرده دارد و در اطراف یک منحنی قرار دارد، بنابراین معمولاً به هم متصل می شود. در این حالت، شبکه معمولی مقادیر بالایی برای توصیفگرها خواهد داشت د1و د2، از آنجایی که مجموعه داده را نمی توان به طور یکنواخت به سلول هایی با مساحت مساوی تقسیم کرد، در حالی که شبکه مبتنی بر Rtree کمترین مقدار را برای د2، زیرا این تکنیکی است که از هندسه ها شروع می شود و نه از فضای خوشه بندی داده ها، بلکه ارزش خوبی برای د1، زیرا داده ها یک منطقه متصل را پوشش می دهند. در نهایت، شبکه مبتنی بر Quadtree ارزش خوبی برای خواهد داشت د1، اما یک مقدار بالاتر برای د2شبکه مبتنی بر Rtree.
• وقتی محاسبه شد E0همین اطراف است 0.0، سپس مجموعه داده کج می شود، فضای مرده زیادی دارد و در اطراف دو یا چند نقطه قرار دارد، بنابراین معمولاً متصل نیست. در این حالت، شبکه معمولی مقادیر بالایی از د1و د2، مثل قبل؛ شبکه مبتنی بر Rtree کمترین مقدار را برای خواهد داشت د2اما یک مقدار بالاتر برای د1به دلیل این واقعیت که اتصال از بین رفته است، در حالی که شبکه مبتنی بر Quadtree مقادیر بهتری برای هر دو خواهد داشت. د1و د2از مدل مبتنی بر Rtree، زیرا با مجموعه داده های خوشه ای سازگاری بهتری دارد.
• ملاحظات مشابهی برای مقادیر از معتبر است E2، جایی که به جای فضای مرده، مناطق با غلظت کمتر/بالاتر را تشخیص می دهد، بنابراین بر توصیفگر عمیق تر تأثیر می گذارد. د2.

با استفاده از ویژگی های 1 و 2 و مشاهدات ذکر شده در بالا، ما اکتشافی زیر را برای انتخاب بهترین تکنیک پارتیشن بندی سفارشی شده برای مجموعه داده D پیشنهاد می کنیم . این بر اساس درخت تصمیم نشان داده شده در شکل 2 است.

اولین تست تی1بر E0تعیین می کند که آیا مجموعه داده در سراسر فضای مرجع پخش شده است یا به نوعی متمرکز شده است. اگر تی1درست است، ما باید نوع توزیعی که استفاده می کند را بررسی کنیم E2. به ویژه، اگر تی2درست است، سپس مجموعه داده دارای توزیع یکنواخت است و بهترین شاخص شبکه منظم است. برعکس، اگر تی2نادرست است، ما به یک آزمایش اضافی نیاز داریم تی4بر E2برای بررسی اینکه آیا فضای اشغال شده متصل است یا خیر. اگر تی4درست است، سپس مجموعه داده را می توان متصل در نظر گرفت و شبکه مبتنی بر Rtree انتخاب می شود. در غیر این صورت، شبکه مبتنی بر Quadtree بهترین انتخاب خواهد بود.

برعکس، اگر تی1نادرست است، سپس مجموعه داده دارای یک توزیع اریب در فضای مرجع است. در این مورد آزمون تی3بر E0برای تعیین اینکه آیا مجموعه داده به نوعی خوشه بندی شده است یا خیر، اعمال می شود. به ویژه، اگر تی3درست است، سپس شبکه مبتنی بر Quadtree انتخاب خواهد شد. برعکس، آزمون نهایی تی5بر E2برای تعیین درجه ای از اتصال و انتخاب بین شاخص Quadtree یا Rtree استفاده می شود.

توجه کنید که در درخت از مقادیر آستانه برابر با استفاده می کنیم -1.5، -0.5برای انتخاب های مربوط به E0، در حالی که از مقادیر آستانه برابر با استفاده می کنیم 1.0، 1.5برای E2، از آنجایی که در نظر می گیریم E2تنها زمانی که مجموعه داده در سرتاسر فضای مرجع پخش شود یا زمانی که E0همین اطراف است 1.0، بنابراین در این مورد مقادیر نزدیک به 0.0قابل دسترسی نیست E2. اثربخشی اکتشافی پیشنهادی با استفاده از آزمایش‌هایی که در بخش بعدی نشان داده شده است، آزمایش شده است.

این بخش آزمایش‌هایی را ارائه می‌کند که بر روی یک خوشه Hadoop متشکل از 10 گره Slave و 1 Master Node انجام شده است که بر روی آن افزونه Hadoop 2.8 و SpatialHadoop 2.4 نصب شده است. هر گره با 4 هسته، 8 گیگابایت حافظه رم و 1 ترابایت SSD مشخص می شود، همه گره ها از طریق یک شبکه باند بی نهایت متصل می شوند. این آزمایش‌ها مجموعه‌ای از مجموعه داده‌ها را شامل داده‌های مکانی مصنوعی و واقعی در نظر می‌گیرند. جدول 4 ویژگی های آنها را نشان می دهد.

برای هر مجموعه داده، ما محاسبه کردیم E0و E2(ستون های 4 و 5 جدول) با اعمال الگوریتم ارائه شده در بخش 4 و با توجه به درخت تصمیم ارائه شده در قسمت قبل بهترین شاخص (ستون 6) را تعیین کردیم. ما سه نوع عملیات را روی این مجموعه داده ها در نظر گرفتیم: پرس و جو محدوده، فضایی joinan k -nn، با استفاده از هر سه شاخص تجزیه و تحلیل شده، یعنی سه تکنیک پارتیشن بندی را اعمال کردیم: شبکه منظم (RG)، شبکه مبتنی بر چهار درخت (QT) و Rtree. شبکه مبتنی بر (RT). با توجه به عملیات محدوده پرس و جو، ما 200 پرس و جو محدوده را برای همه مجموعه داده ها و برای همه انواع شاخص ها با تغییر طول سمت منطقه پرس و جو (از 0.001به 0.05با توجه به فضای مرجع نرمال شده به 1×1). نتایج به‌دست‌آمده در جدول 5 نشان داده شده است که در آن زمان‌های گزارش‌شده یک مقدار متوسط ​​بیش از 200 پرسش برای هر مورد است. توجه داشته باشید که بهترین عملکردها همیشه زمانی به دست می‌آیند که شاخص مورد استفاده همانی باشد که توسط اکتشافی پیشنهادی پیشنهاد می‌شود. به طور خاص، زمانی که مجموعه داده به طور یکنواخت توزیع می شود ( UD ) همه تکنیک ها عملکرد مشابهی دارند، در واقع تفاوت بین بهترین و بدترین راه حل حداکثر 5٪ است. برای سایر مجموعه‌های داده مصنوعی، همانطور که انتظار می‌رفت، به دست آوردیم که برای هر دو مجموعه داده که توزیع حول یک خط دارند، بهترین شبکه مبتنی بر Rtree است، با بهره بالاتر در مورد مجموعه داده DL . در عوض، وقتی شباهت بالاتری را با توزیع خوشه‌ای مشاهده کردیم، مانند DC بمجموعه داده، بهترین راه حل شبکه مبتنی بر Quadtree است. مجموعه داده های واقعی همان رفتار مجموعه داده های مصنوعی را نشان می دهد که کیفیت اکتشافی پیشنهادی را تأیید می کند. به ویژه، زمانی که مجموعه داده تقریباً به طور یکنواخت توزیع شده است، مانند WA ایالات متحده آمریکایا ST ایالات متحده آمریکاتفاوت های ناشی از تکنیک های مختلف پارتیشن بندی بسیار کم است.

برای عملیات اتصال فضایی، آزمایش‌هایی را روی مجموعه داده‌های مصنوعی با پیوستن به یک مجموعه داده توزیع‌شده یکنواخت، به نام UN ، انجام دادیم، با مجموعه داده دیگری D که یکی از انواع دیگر توزیع‌های در نظر گرفته شده را دارد. به طور خاص، برای هر نوع توزیع در جدول 4 ، 10 مجموعه داده مصنوعی به طور تصادفی تولید شده و به UN ملحق شده است. نتایج به دست آمده در جدول 6 گزارش شده است. همانطور که برای تست های قبلی، به جز مورد توزیع یکنواخت که در آن همه شاخص ها عملکرد یکسانی دارند، بهترین نتایج زمانی حاصل می شود که D با استفاده از نوع پیشنهادی شاخص تقسیم شود، همچنین کاهش قابل توجهی در زمان اجرا حاصل می شود.

برای مجموعه داده‌های واقعی، ما اولین پیوند بین مجموعه داده‌های روابط عمومی را انجام دادیم ایالات متحده آمریکاو WA ایالات متحده آمریکاو اتصال دوم بین روابط عمومی AUSو ST AUS. هر دو اتصال در 9 شرایط مختلف انجام شدند که با در نظر گرفتن تمام ترکیبات ممکن از نوع شاخص در مجموعه داده اول و دوم به دست می‌آیند. نتایج در جدول 7 و جدول 8 گزارش شده است. بهترین زمان اجرا زمانی به دست می آید که هر دو مجموعه داده با نوع پیشنهادی ایندکس تقسیم شوند. توجه داشته باشید که بدترین عملکردها زمانی به دست می‌آید که یک شبکه منظم برای هر دو مجموعه داده ساخته شود، که تأیید می‌کند که در مورد داده‌های ناهموار شاخص خوبی نیست.

در نهایت، برای عملیات k -nn، آزمایش‌هایی را روی داده‌های مصنوعی و واقعی انجام می‌دهیم. در مورد نمونه های مصنوعی، برای هر نوع توزیع در نظر گرفته شده 10 مجموعه داده مختلف تولید می کنیم و برای هر یک از آنها 40 آزمایش را با انتخاب تصادفی نقطه پرس و جو انجام می دهیم، نیمه اول آزمایش ها مقدار k برابر با 100 در نظر می گیرند، در حالی که دومی مقدار k برابر با 10000. آزمایش‌های مشابهی نیز برای مجموعه داده‌های واقعی، با تغییر مقدار k و نقطه مرجع، انجام شده است. نتایج در گزارش شده است جدول 9 گزارش شده است. همانطور که در مورد عملیات قبلی، در مورد مجموعه داده های توزیع شده یکنواخت، تفاوت بین بهترین و بدترین تکنیک نمایه سازی بسیار کم است. برعکس، در موارد دیگر، انتخاب تکنیک پارتیشن بندی مناسب تاثیر قابل توجهی بر عملکرد کلی دارد.

این مقاله تاثیر یک توزیع اریب را بر عملکرد سه عملیات فضایی، یعنی پرس و جو محدوده، پیوستن فضایی و k در نظر می گیرد.-nn، با توجه خاص به تأثیر آن بر تعادل کار انجام شده توسط وظایف نقشه در طول اجرای موازی آنها. ما به عنوان چارچوب مرجع SpatialHadoop و تکنیک های پارتیشن بندی آن را در نظر گرفتیم: شبکه منظم، شبکه مبتنی بر Quadtree و شبکه مبتنی بر درخت R. چنین تکنیک های پارتیشن بندی می توانند نتایج متفاوتی را بر اساس توزیع نشان داده شده توسط هر مجموعه داده تولید کنند و این نتایج می تواند منجر به تفاوت های بالقوه زیادی در عملکرد عملیات فضایی شود. بنابراین، انتخاب تکنیک پارتیشن بندی مناسب برای هر نوع مجموعه داده، به یک فعالیت مهم برای بهره برداری کامل از مزایای اجرای MapReduce تبدیل می شود. به همین دلیل، ما یک تکنیک جدید بر اساس تابع شمارش جعبه [ 14 ] پیشنهاد کردیم] برای تخمین موثر توزیع مجموعه داده و بر این اساس روش پارتیشن بندی مناسب تر را انتخاب کنید. برخی از آزمایش‌ها بر روی مجموعه داده‌های مصنوعی و واقعی برای نشان دادن اثربخشی اکتشافی پیشنهادی انجام شده است. چنین آزمایش‌هایی نشان می‌دهد که در همه موارد، تکنیک پارتیشن‌بندی پیشنهادی قادر به بهبود زمان اجرای عملیات فضایی زیر است. به طور خاص، در حالی که در حضور توزیع یکنواخت، همه تکنیک های پارتیشن بندی اساساً تأثیر یکسانی بر عملیات زیر دارند، هنگامی که مجموعه داده های اریب در نظر گرفته می شوند، انتخاب تکنیک پارتیشن بندی اشتباه می تواند زمان مورد نیاز برای یک تحلیل داده شده را دو برابر کند. علاوه بر این، زمانی که توزیع شبیه به یک غلظت خطی است، تکنیک‌های تقسیم‌بندی مبتنی بر داده (مانند درخت R) مناسب‌تر هستند. از آنجایی که آنها می توانند تقسیمات متعادل تری تولید کنند، در حالی که برای مجموعه داده های خوشه ای مناسب نیستند زیرا می توانند پارتیشن هایی با تعداد زیادی فضاهای مرده تولید کنند. در چنین شرایطی، پارتیشن بندی مبتنی بر فضا (مانند Quadtree) انتخاب مناسبی است.

کار آینده به استفاده از دانش در مورد توزیع مجموعه داده برای کاهش اتصالات جانبی، گسترش رویکرد پیشنهادی برای تخمین انتخاب‌پذیری، استفاده از تابع شمارش جعبه برای تخمین چولگی مجموعه‌های داده چند بعدی، همچنین خارج از بافت فضایی، مربوط می‌شود. توسعه مهم دیگر می تواند استفاده از روش پیشنهادی به منظور تعریف تکنیک های پارتیشن بندی ترکیبی جدید باشد. به طور خاص، این تکنیک می‌تواند برای شکستن مجموعه داده‌های معین به زیر مجموعه‌های همگن که تکنیک‌های پارتیشن‌بندی متفاوتی روی آن‌ها اعمال شود، اعمال شود. همچنین در کار آینده بررسی جهتی که پارتیشن بندی را بدون اکتشاف، صرفاً بر اساس توزیع شناسایی شده و با استفاده از مدل های یادگیری ماشینی تعیین می کند، ارزشمند خواهد بود.