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

کلید واژه ها:

نقشه برداری مجدد شبکه، شبکه بدون ساختار ; درخت KD ; مرز چرخه ای

1. مقدمه

سیستم شبیه سازی زمین [ 1 ] از یک مدل منفرد (مثلاً مدل جوی، مدل اقیانوس) به یک سیستم جفت شده (مثلاً سیستم جفت شده اقیانوس-اتمسفر) توسعه یافته است، و در پیش بینی تغییرات آب و هوا و هشدار اولیه اهمیت زیادی دارد. از بلایای طبیعی برای سیستم‌های جفت شده، فناوری نقشه‌برداری مجدد شبکه یک پل حیاتی برای تعامل داده‌ها بین مدل‌های مؤلفه است.
در اصل، نگاشت مجدد شبکه نوعی درون یابی داده است. از نظر بقای روش های درون یابی را می توان به درون یابی محافظه کارانه و درون یابی غیر محافظه کارانه تقسیم کرد. درون یابی محافظه کارانه [ 2 ] نیاز به در نظر گرفتن سطح شبکه و حتی انحنای زمین برای اطمینان از بقای شار (به عنوان مثال، شار تکانه، شار حرارتی) دارد، در حالی که درون یابی غیر محافظه کار معمولاً فقط مکان نقاط شبکه را در نظر می گیرد. برای درون یابی غیر محافظه کارانه، مقدار داده در شبکه هدف در واقع میانگین وزنی مقدار داده در شبکه منبع است. به عنوان مثال، درون یابی وزن فاصله معکوس [ 3] از فاصله متقابل از نقطه مبدا تا نقطه هدف به عنوان وزن هر نقطه منبع استفاده می کند. سایر روش‌های درونیابی غیرمحافظه‌کار سنتی شامل درونیابی نزدیکترین همسایه [ 4 ]، درونیابی دوخطی [ 5 ] و غیره است. می تواند به سرعت کشف شود به طور مستقیم تأثیر مستقیمی بر کارایی درون یابی دارد.
تعداد زیادی روش برای جستجوی داده ها در فضای چند بعدی توسعه داده شده است [ 6 ، 7 ، 8 ]. با این حال، بیشتر این روش‌ها نمی‌توانند با داده‌های بی‌نظم مقابله کنند، به این معنی که به سختی می‌توانند با مشکلات شبکه بدون ساختار مقابله کنند. با ظهور مدل‌های شبکه بدون ساختار (به عنوان مثال، FVCOM)، تقاضا برای الگوریتم‌های جستجوی درون‌یابی عمومی قوی‌تر و قوی‌تر می‌شود. در حال حاضر، ابزارهای درون یابی اصلی (به عنوان مثال، SCRIP [ 9]) روش مسدود کردن را برای جستجوی داده اتخاذ کنید، یعنی فضای جستجو به چندین بلوک تقسیم می شود و شبکه هدف از جستجوی خشونت آمیز در بلوک ها استفاده می کند. با این حال، کارایی و صحت این روش تا حد زیادی به تنظیم اندازه بلوک و توزیع داده ها بستگی دارد. اگر بلوک خیلی بزرگ باشد، جستجوی خشونت آمیز زمان زیادی طول می کشد، در حالی که اگر بلوک خیلی کوچک باشد، ممکن است نقطه درست پیدا نشود. بنابراین، یک الگوریتم جستجوی داده های عمومی تر و قوی تر مورد نیاز است.
اجرای یک جستجوی کلی داده بر اساس درخت KD، که ابتدا توسط بنتلی [ 10 ] پیشنهاد شد، یک انتخاب بالقوه است. درخت KD را می توان به عنوان یک درخت باینری خاص در نظر گرفت. تمایز یک درخت KD و یک درخت باینری معمولی در این است که یک درخت باینری معمولی همیشه داده های خود را بر یک بعد ثابت تقسیم می کند، در حالی که درخت KD را می توان بر اساس نیازها بر هر بعد در هر لایه تقسیم کرد. بعد با بیشترین واریانس یا وسیع ترین پراکندگی معمولاً برای تقسیم بندی انتخاب می شود تا فضای جستجو تا حد امکان به طور مساوی تقسیم شود. نقطه میانه معمولاً به عنوان نقطه پارتیشن انتخاب می شود تا یک درخت KD متعادل ساخته شود که ارتفاع درخت را کاهش دهد و زمان جستجو را کوتاه کند [ 11 ]]. پس از اتمام ساخت درخت KD، کل فضای جستجو بر اساس ترتیب تقسیم به شکل درخت دودویی سازماندهی می شود. جستجوی داده بر اساس درخت KD شامل دو مرحله است. اولین مرحله مقایسه مقدار در بعد پارتیشن مشخص شده با نقطه پارتیشن انتخابی از سطح بالا به سطح پایین است تا زمانی که گره برگ پیدا شود. این بدان معنی است که نقطه هدف در فضای فرعی که توسط گره برگ نشان داده شده است قرار دارد. مرحله دوم این است که لایه به لایه پشت سر را ردیابی کنید و قضاوت کنید که آیا درخت فرعی دیگری ممکن است دارای نقاط مرتبط باشد. هنگامی که چنین امکانی وجود دارد، درخت فرعی دیگر بلافاصله به همان روش جستجو می شود. بنابراین، جستجوی داده‌ها بر اساس درخت KD معمولاً توسط الگوریتم بازگشتی پیاده‌سازی می‌شود.
تلاش زیادی برای بهبود کارایی تحقیقات داده بر اساس درخت KD انجام شده است. براون [ 12 ] برای یافتن نقطه میانه سریعتر در طول فرآیند ساخت، روشی را بر اساس نتایج از پیش مرتب شده پیشنهاد کرد، که مشکل روش انتخاب سریع را که در معرض چیدمان داده است حل کرد. کائو و همکاران [ 13 ، 14 ] با معرفی ساختارهای داده اضافی، کارایی خود را بیشتر بهبود بخشید. روش نمونه‌گیری می‌تواند برای تخمین نقطه میانه [ 15 ] استفاده شود که آن را برای مجموعه‌های داده در مقیاس بزرگ مناسب می‌کند. علاوه بر این، فناوری موازی به طور گسترده در ساخت و جستجوی داده های درخت KD استفاده می شود [ 16 ، 17 ، 18]. از منظر دانه بندی موازی، طرح های موازی جریان اصلی را می توان به دو دسته تقسیم کرد. یکی موازی سازی سطح داده و دیگری موازی سازی سطح وظیفه است. تعامل داده‌ای بین هسته‌ها در موازی‌سازی سطح داده وجود خواهد داشت (به عنوان مثال، انتخاب نقطه پارتیشن موازی)، در حالی که داده‌ها در هر هسته در موازی‌سازی سطح وظیفه (مثلاً ساخت زیر درخت موازی) نسبتاً مستقل خواهند بود.
درخت KD به طور گسترده در جستجوی داده های حیاتی چند بعدی، به ویژه در جستجوی نزدیکترین همسایه و جستجوی محدوده استفاده شده است. هو و همکاران [ 19 ] از درخت KD برای بهبود کارایی طبقه‌بندی داده‌ها، که یک زمینه حیاتی در داده‌کاوی است، استفاده کرد. بهبود دیگری در درخت KD توسط هاوران و همکاران انجام شد. [ 20 ] در زمینه ردیابی پرتو. Guo [ 21 ] درخت KD را در قسمت ثبت ابر نقطه اعمال کرد. او و همکاران [ 22 ] یک روش جدید نمایه سازی داده های ابری را بر اساس درخت KD پیشنهاد کرد. به منظور مقابله با مشکلات تغییر شکل بزرگ در زمینه دینامیک سیالات محاسباتی (CFD)، یک روش درون یابی جدید برای مش بدون ساختار بر اساس درخت KD توسط Guo و همکاران پیاده سازی شده است. [ 23 ]. گوو و همکاران [ 24] همچنین یک روش مبتنی بر درخت KD را برای یافتن نزدیکترین فاصله از یک نقطه جریان تا دیوار در میدان CFD توسعه داد. کائو و همکاران [ 25 ] حتی پتانسیل درخت KD را در نقشه‌برداری مجدد شبکه در سیستم‌های شبیه‌سازی زمین آزمایش کرده‌اند، و نتایج نشان داد که همیشه می‌تواند بدون توجه به نوع شبکه به عملکرد معقولی دست یابد.
در حال حاضر، مطالعات کمی در مورد کاربرد درخت KD در نقشه‌برداری مجدد شبکه در سیستم‌های شبیه‌سازی زمین در ادبیات وجود دارد. یکی از دلایل احتمالی این است که درخت KD اصلی نمی تواند با مرز چرخه ای مقابله کند. درخت KD از ابرصفحه‌ها برای تقسیم فضای جستجو استفاده می‌کند و پیش‌فرض به‌دست آوردن فضاهای فرعی مستقل، منحصربه‌فرد و غیر همپوشانی این است که هر بعد از فضا غیر چرخه‌ای است. با این حال، بسیاری از موارد در سیستم‌های شبیه‌سازی زمین جفت شده باید با نقشه‌برداری مجدد شبکه با مرزهای چرخه‌ای، مانند شبیه‌سازی جهانی (طول جغرافیایی شبکه جهانی چرخه‌ای است) و برخی آزمایش‌های ایده‌آل منطقه‌ای با مرزهای چرخه‌ای سروکار داشته باشند. هنگامی که مرزهای چرخه ای در فضای جستجو وجود داشته باشد، بسیاری از نتایج حاصل از فرآیند جستجوی داده اصلی دیگر قابل تحمل نخواهد بود. از این رو،
با در نظر گرفتن نزدیکترین جستجوی همسایه به عنوان مثال، با توجه به ویژگی‌های مرزهای چرخه‌ای، این مقاله دو روش جستجوی جدید را پیشنهاد می‌کند که قادر به مدیریت مشکلات مرز چرخه‌ای بر اساس درخت KD هستند، که تا حد زیادی دامنه کاربرد فعلی درخت KD را گسترش می‌دهد. یک روش مبتنی بر تکرار نقاط هدف است و روش دیگر بر اساس تکرار نقاط مبدا است. با توجه به دانش نویسندگان، این اولین بار است که درخت KD برای انجام جستجوی داده در فضای چرخه ای استفاده شده است. علاوه بر این، پیچیدگی زمانی و مکانی این دو روش مورد تجزیه و تحلیل قرار گرفته و با توجه به عملکرد آنها در آزمایش‌ها، پیشنهادات کلی ارائه شده است.
بقیه بخش‌های این مقاله به شرح زیر سازماندهی شده‌اند: شرح مفصل و تجزیه و تحلیل پیچیدگی این دو روش جدید در بخش 2 ارائه شده است، تجزیه و تحلیل آزمایش‌ها و تأیید در بخش 3 نشان داده شده است ، و نتیجه‌گیری در بخش 4 ارائه شده است.

2. الگوریتم

2.1. ایده پایه

هنگام در نظر گرفتن فضای چرخه ای، معمولاً یک مرز مصنوعی برای تقسیم فضای پیوسته پیشنهاد می شود که به آن مرز چرخه ای یا مرز دایره ای می گویند. به این ترتیب، دو مرز محدود مجازی در بعد چرخه ای ظاهر می شوند و تمام داده ها در یک بخش حلقه مشخص قرار می گیرند. این مقاله با اشاره به روش تنظیم نقاط هاله در اطراف مرزهای محلی به منظور تحقق ارتباط بین نقاط مجاور در فرآیند محاسبات موازی، روش‌های آینه‌ای مشابهی را برای انجام جستجوی داده‌های حیاتی در فضای چرخه‌ای چند بعدی بر اساس درخت KD پیشنهاد می‌کند.
با در نظر گرفتن نزدیکترین جستجوی همسایه در فضای دوبعدی با تنها یک مرز چرخه ای در امتداد جهت عمودی به عنوان مثال (نگاه کنید به شکل 1 )، روش آینه دارای دو طرح اساسی بر اساس انتخاب اشیاء تکرار شده است. طرح اول عبارت است از کپی کردن نقاط منبع مرتبط به عنوان نقاط آینه ای، یعنی کپی کردن نقاط مبدا در نزدیکی مرز چرخه ای A در سمت راست مرز چرخه ای B، و کپی کردن نقاط مبدا در نزدیکی مرز چرخه ای B در سمت چپ مرز چرخه ای A. حداکثر مساحت برای هر تکرار نیمی از کل فضای جستجو است ( شکل 1 را ببینیدآ). هزینه این طرح این است که فضای ذخیره سازی بیشتری برای ذخیره آن نقاط آینه ای مورد نیاز است. در عین حال، با افزایش مقیاس داده های منبع، زمان ساخت درخت KD نیز افزایش می یابد. علاوه بر این، زمان جستجو نیز به دلیل عمیق شدن درخت تا حدی افزایش می یابد. اگر توزیع داده های منبع دارای ویژگی هایی باشد که می توان از آنها بیشتر استفاده کرد، مانند حداکثر فاصله بین هر موقعیتی در فضای جستجو و نزدیک ترین نقطه منبع آن، تعداد نقاط تکراری را می توان بیشتر کنترل کرد. طرح دوم انتخاب نقطه هدف برای تکرار است. پس از جستجوی کامل با روش اصلی، نقطه هدف به خارج از مرز چرخه ای که دورتر از نقطه هدف قرار دارد کپی می شود (با فرض اینکه مرز چرخه ای B باشد).شکل 1ب). نزدیکترین نقطه همسایه نهایی از این دو نتیجه جستجو انتخاب می شود. اگرچه این روش فقط به مقدار کمی سربار ذخیره سازی بیشتری نیاز دارد، زمان جستجو تقریباً دو برابر شده است. اگر بهینه‌سازی بیشتر فرآیند جستجو برای کاهش زمان جستجو مورد نیاز است، باید مکانیسم‌های جدیدی را برای هرس بیشتر در طول فرآیند جستجو با استفاده از ویژگی‌های درخت KD و ویژگی‌های توزیع داده‌های منبع و داده‌های هدف معرفی کنیم. به عنوان مثال، قبل از تکرار نقطه هدف، اگر فاصله از نقطه هدف تا نزدیکترین مرز چرخه ای آن (با فرض اینکه مرز چرخه ای A باشد) بیشتر از نتیجه جستجوی اول باشد، عملیات تکرار و جستجوی دوم را می توان لغو کرد. زیرا در این زمان هیچ نقطه منبع نزدیک تری در نزدیکی مرز چرخه ای دیگر وجود نخواهد داشت. علاوه بر این،

2.2. توصیف همراه با جزئیات

در این قسمت روند این دو روش را به تفصیل شرح خواهیم داد. فرض بر این است که فضای جستجو دارای ابعاد K با مرزهای چرخه ای C است. بدون از دست دادن کلیت، D[1] را روی D[c] به عنوان ابعاد چرخه‌ای قرار می‌دهیم، جایی که D[i] نمایانگر بعد i است.
فرآیند روش آینه بر اساس تکرار نقاط مبدا در شکل 2 نشان داده شده است. اولین مرحله انجام پیش پردازش داده است، یعنی قرار دادن تمام نقاط مبدا و نقاط هدف در یک بخش حلقه مشخص برای هر بعد چرخه ای. متعاقباً، نقاط مبدأ نزدیک یک مرز چرخه‌ای به خارج از مرز چرخه‌ای متناظر دیگر برای هر بعد چرخه‌ای کپی می‌شوند. دامنه تکرار را می توان با ویژگی های توزیع داده های منبع تعیین کرد. به عنوان مثال، اگر حداکثر فاصله بین هر موقعیتی در فضای جستجو و نزدیکترین نقطه منبع آن L باشد، فقط نقاط منبع در محدوده L از مرز چرخه ای باید کپی شوند. در واقع، پیش شرط را می توان بیشتر تضعیف کرد. تا زمانی که چگالی نقطه منبع نزدیک به مرز چرخه ای به چنین شرایطی برسد، روش تکرار محدود همچنان کار می کند. با این حال، اگر ویژگی های توزیع داده های منبع ناشناخته یا نامطمئن باشند، حداکثر ناحیه تکراری برای هر مرز چرخه ای نیمی از فضای جستجوی اصلی خواهد بود. لازم به ذکر است که تمامی موارد تکراری باید بر اساس محل اصلی داده های منبع باشد. پس از کپی کردن نقاط منبع مربوطه برای هر بعد چرخه‌ای، درخت KD را می‌توان ساخت و نزدیک‌ترین نقطه را طبق الگوریتم کلاسیک پیدا کرد (جزئیات بیشتر در مورد این الگوریتم‌های کلاسیک را می‌توانید در [25 ]). مرحله آخر این است که نتایج جستجو را به منطقه اصلی یا شماره نقطه اصلی، مشابه پیش پردازش داده، نگاشت کنید.
فرآیند روش آینه بر اساس تکرار نقاط هدف در شکل 3 نشان داده شده است . کارهای اولیه، از جمله پیش پردازش داده ها، ساخت درخت KD، و جستجوی کلی نزدیکترین نقطه، مشابه جستجوی معمولی نزدیکترین همسایه بر اساس درخت KD هستند. کوتاهترین فاصله اولیه T 0معمولاً روی یک عدد منفی یا یک مقدار به اندازه کافی بزرگ تنظیم می شود. پس از دور اول جستجوی داده ها، کوتاه ترین فاصله نهایی بین نقطه هدف و نزدیک ترین نقطه منبع آن به عنوان T به دست می آید. متعاقباً باید با روش خاصی به هر بعد چرخه ای نزدیک شویم. به خاطر سادگی، این ابعاد چرخه ای می توانند به نوبه خود پردازش شوند. هنگام برخورد با بعد چرخه ای پردازش نشده i، مقایسه بین فاصله از نقطه هدف تا نزدیکترین مرز چرخه ای آن در بعد i- ام S و کوتاهترین فاصله فعلی T باید در ابتدا انجام شود. اگر S کمتر از T نباشد، به این معنی است که منبع نزدیک به مرز چرخه‌ای دیگری در i استبعد -ام نمی تواند نزدیکتر از نقطه فعلی باشد. بنابراین، نیازی به جستجوی دوباره برای مرز چرخه‌ای دیگر نیست، و اکنون می‌توانیم بعد چرخه‌ای بعدی را پردازش کنیم. در غیر این صورت، به جستجوی بیشتر در بعد چرخه ای فعلی نیاز خواهید داشت. قبل از شروع جستجوی جدید، باید نقطه هدف را در همان موقعیت نسبی خارج از مرز چرخه ای مربوطه کپی کنیم. جستجوی زیر می‌تواند کوتاه‌ترین فاصله فعلی T را به عنوان مقدار اولیه کوتاه‌ترین فاصله اتخاذ کند، زیرا ممکن است به ما کمک کند شاخه‌های غیرضروری بیشتری را در جستجوی جدید قطع کنیم. با فرض اینکه نزدیکترین فاصله جدید t باشد، باید بین t و T مقایسه کنیم و کوچکترین نتیجه را به عنوان آخرین نتیجه انتخاب کنیم. شایان ذکر است اگر نزدیکترین فاصله نهایی و نزدیکترین نقطه نهایی از مکانیسم آدرس عبور در برنامه نویسی استفاده شود. عملیات به روز رسانی را می توان حذف کرد. پس از اینکه تمام ابعاد چرخه ای تحت عملیات توصیف شده در بالا قرار گرفتند، کوتاه ترین فاصله و نقطه منبع مربوطه به دست آمده نتیجه نهایی خواهد بود.

2.3. تحلیل پیچیدگی

برای تسهیل تجزیه و تحلیل، ما فرض می کنیم که تعداد نقاط مبدا N و تعداد نقاط هدف M است. سپس، پیچیدگی فضایی روش اصلی جستجوی مبتنی بر درخت KD O (N + M) خواهد بود. و میانگین پیچیدگی زمانی ساخت KD و جستجوی داده روش اصلی به ترتیب O (Nlog 2 N) و O (Mlog 2 N) است. علاوه بر این، برای سهولت توضیح در تحلیل زیر، از SPD و TPD برای نشان دادن روش تکرار نقاط مبدا و روش تکرار نقاط هدف استفاده می‌کنیم و به ترتیب از CP و SP برای نمایش فرآیند ساخت و فرآیند جستجو استفاده می‌کنیم.

در مورد روش آینه‌ای مبتنی بر تکرار نقاط مبدا، در بدترین حالت، تمام نقاط منبع باید برای هر فضای چرخه‌ای کپی شوند. در چنین شرایطی، پیچیدگی فضا O (N + CN + M) خواهد بود. زمان مصرف شده برای ساخت درخت KD خواهد بود:

T SPD،CP = O ((C + 1)Nlog 2 ((C + 1)N))

میانگین زمان صرف شده برای جستجوی داده ها خواهد بود:

T SPD,SP = O (Mlog 2 ((C + 1)N))

در مورد روش آینه ای بر اساس تکرار نقاط هدف، سربار ذخیره سازی اضافی برای نقطه هدف تکرار شده ناچیز است. بنابراین، پیچیدگی فضا را می توان به صورت O (N + M) نوشت که همان جستجوی سنتی نزدیکترین همسایه بر اساس درخت KD است. زمان مصرف شده برای ساخت درخت KD یکسان باقی می ماند که می توان آن را به صورت زیر نوشت:

T TPD,CP = O (Nlog 2 N)

میانگین پیچیدگی زمانی فرآیند جستجوی داده ها تغییر کرده است که می تواند به صورت زیر نوشته شود:

T TPD,SP = O ((βC + 1) Mlog 2 N)

که β میانگین نسبت تکرار است و بین 0 و 1 متغیر است. در بدترین حالت، هر نقطه هدف باید در هر بعد چرخه‌ای یک جستجوی جدید انجام دهد، به این معنی که β 1 است. در چنین شرایطی، پیچیدگی زمانی جستجوی داده‌ها فرآیند O ((CM + M) log 2 N) خواهد بود. با این حال، در اکثر مسائل عملی، تنها بخش کوچکی از نقاط هدف نزدیک به مرز چرخه ای باید دو بار یا چند بار جستجو شوند (یعنی β به 0 تمایل دارد). بنابراین، زمان جستجوی مصرف شده در عمل معمولاً بسیار کمتر از بدترین تخمین است. شایان ذکر است که در صورت عدم اتخاذ قضاوت همانندسازی، پیچیدگی زمانی این روش بدترین نتیجه خواهد بود.

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

T TPD,SP -T SPD,SP = (βC + 1) Mlog 2 N-Mlog 2 ((C + 1)N) > 0

پس از ساده سازی می توان آن را به صورت زیر نوشت:

β > آستانه β = log 2 (C + 1) / (Clog 2 N)، C > 0
از رابطه (6) می توان دریافت که آستانه β با افزایش N و C کاهش می یابد. در عمل، سربار فرآیند جستجو برای نقاط هدف تکراری کمتر از جستجوی سنتی خواهد بود، زیرا جستجوی جدید قبلاً یک کوتاه‌ترین فاصله قابل اعتماد در ابتدا، که تا حد زیادی شاخه‌های جستجوی غیر ضروری را در طول فرآیند عقب‌گردی کاهش می‌دهد. به این معنی که، به طور کلی، تنها زمانی که β بسیار بیشتر از مقدار آستانه محاسبه‌شده در بالا باشد، روش آینه‌ای مبتنی بر تکرار نقاط هدف بدتر از روش مبتنی بر تکرار نقاط منبع عمل می‌کند.

3. آزمایشات

این دو روش آینه ای در آزمایشات ما به زبان C پیاده سازی شده اند. بعد تقسیم به ترتیب طبیعی انتخاب شده است، و روش انتخاب سریع [ 26 ، 27 ] برای یافتن داده های میانه در طول ساخت درخت KD استفاده می شود. اولین عنصر همیشه به عنوان عنصر محوری در روش انتخاب سریع ما برای سادگی انتخاب می شود. جزئیات بیشتر در مورد فرآیند اساسی ساخت درخت KD و جستجوی داده ها بر اساس درخت KD را می توان در [ 25 ] مشاهده کرد. دو مجموعه داده پایه، با 2 24داده های واقعی 6 بعدی به طور تصادفی تولید شده در هر یک، در آزمایش های زیر استفاده می شود. هر عنصر در داده های 6 بعدی دارای مقداری بین 0 تا 100 با 6 رقم اعشار معتبر است. در آزمایش‌های زیر، از مجموعه داده‌های تصادفی 1 به عنوان داده منبع و از مجموعه داده‌های تصادفی 2 به عنوان داده هدف استفاده می‌شود. از آنجایی که ویژگی های توزیع داده های منبع برای داده های تولید شده به طور تصادفی نامشخص است، تمام نقاط منبع برای هر بعد چرخه ای در روش آینه ای بر اساس تکرار نقاط منبع کپی می شوند. صحت این دو روش با اعتبارسنجی متقاطع با استفاده از داده‌های یکسان تأیید می‌شود و نتایج مرتبط برای تأیید صحت در این مقاله نشان داده نشده است.

شکل 4 و شکل 5 به ترتیب زمان ساخت و زمان جستجوی این دو روش آینه ای را با تعداد نقاط منبع متفاوت نشان می دهد. در این آزمایش، K = 4 (یعنی، هر دو نقطه منبع و هدف داده های 4 بعدی هستند). تعداد نقاط هدف M 2 21 و تعداد ابعاد چرخه ای C 4 است. تعداد نقاط منبع N از 2 18 تا 2 24 متغیر است که هر بار دو برابر می شود. همانطور که از شکل 4 مشاهده می شود ، زمان ساخت روش آینه بر اساس تکرار نقاط هدف متناسب با Nlog 2 است.N، که با پیچیدگی زمانی که در بالا تحلیل کردیم (معادله (3)) سازگار است. در حالی که زمان ساخت روش آینه بر اساس تکرار نقاط مبدأ بسیار بیشتر است (بیش از پنج برابر نسبت به تکرار نقاط هدف)، این با تحلیل ما از پیچیدگی زمانی آن مطابقت دارد (O (5Nlog 2 5N) با توجه به معادله 1)). از نظر عملکرد جستجوی داده ها، شکل 5 نشان می دهد که روش آینه ای مبتنی بر تکرار نقاط هدف هنوز بهتر از روش مبتنی بر تکرار نقاط منبع تحت پیکربندی فعلی است. رشد زمان جستجوی روش آینه بر اساس تکرار نقاط منبع تقریباً متناسب با Mlog 2 استN. با توجه به پیچیدگی زمانی جستجوی روش تکثیر نقاط منبع که در بالا استنتاج شد (معادله (2)، مشتق آن به Mlog 2 N برآورده می‌شود:

∂Mlog2((C+1)N)∂Mlog2N∝∂log2((C+1)N)∂N∂N∂log2N∝1=constant∂Mlog2C+1N∂Mlog2N∝∂log2C+1N∂N∂N∂log2N∝1=constant
فرمول استنباط شده در بالا نشان می دهد که روند رشد زمان جستجوی روش تکراری نقاط مبدا که در شکل 5 نشان داده شده است معقول است. علاوه بر این، به وضوح می توان مشاهده کرد که نرخ رشد زمان جستجوی روش تکراری نقاط هدف با افزایش تعداد نقاط منبع به طور قابل توجهی کاهش می یابد. این به این دلیل است که افزایش نقاط مبدا به طور کلی تعداد نقاط هدف تکراری را کاهش می دهد.
شکل 6 بیشتر تغییر میانگین نسبت تکرار واقعی β و آستانه میانگین بتا نسبت تکرار را با تعداد نقاط منبع مختلف در این آزمایش نشان می‌دهد. خط ثابت نشان می دهد که تنها بخش کوچکی از نقاط (کمتر از 6٪ به طور متوسط ​​برای هر بعد چرخه ای) در طول جستجو تکرار می شود، که اهمیت استراتژی قضاوت تکرار پیشنهاد شده در روش تکرار نقاط هدف را نشان می دهد. از نظر روند رشد، به وضوح می توان از تصویر مشاهده کرد که آستانه β و β وجود داردهر دو با افزایش نقاط منبع کاهش می یابند. نرخ کاهش میانگین نسبت تکرار واقعی ارتباط نزدیکی با تعداد و توزیع نقاط مبدا و نقاط هدف دارد. در این آزمایش، نرخ کاهش β بیشتر از آستانه β است . علاوه بر این، β بیشتر از آستانه β است که N < 222 باشد. بر اساس تجزیه و تحلیل قبلی، زمان جستجوی روش مبتنی بر تکرار نقاط هدف ممکن است بزرگتر از زمان جستجوی مبتنی بر تکرار نقاط منبع باشد. با این حال، این پدیده رخ نمی دهد ( شکل 5 را ببینید). این به این دلیل است که نقطه هدف کپی شده قبلاً دارای نزدیکترین فاصله مناسب قبل از جستجوی داده جدید بوده است، که باعث کاهش تعداد شاخه‌هایی می‌شود که باید در طول فرآیند عقب‌گردی به آنها دسترسی پیدا کرد و در نتیجه زمان کمتری را برای نقاط هدف کپی شده نسبت به جستجوی معمولی مصرف می‌کند. . در این آزمایش، β فقط کمی بالاتر از آستانه β است ، و سربار اضافی در تئوری با عملکرد عالی آن نقاط هدف کپی شده در عمل جبران می‌شود. بنابراین، هیچ موردی وجود ندارد که زمان جستجوی روش آینه ای بر اساس تکرار نقاط هدف بیشتر از زمان جستجوی مبتنی بر تکرار نقاط مبدا در آزمایش فعلی باشد.
به منظور تأیید بیشتر استنباط خود، تعداد گره‌هایی را که در فرآیند جستجو (یعنی تعداد دفعات محاسبه فاصله) از این دو روش به دست می‌آیند ( شکل 7 را ببینید ) شمارش کردیم، زیرا این زمان‌برترین بخش است. از کل فرآیند جستجو همانطور که از شکل مشاهده می شود، تعداد گره های دسترسی در روش تکراری نقاط مبدأ همیشه بیشتر از روش تکراری نقاط هدف است، که همچنین دلیل مستقیم این است که زمان جستجو بر اساس تکرار نقاط منبع همیشه بیشتر از که بر اساس نقاط هدف تکراری است.
شکل 8 زمان جستجوی این دو روش را با تعداد نقاط هدف متفاوت نشان می دهد. در این آزمایش، تعداد ابعاد داده‌ها و تعداد ابعاد چرخه‌ای مانند آزمایش قبلی است (یعنی K = 4، C = 4). تعداد نقاط منبع N روی 2 24 ثابت است ، در حالی که تعداد نقاط هدف M از 2 18 تا 2 24 متغیر است (هر بار دو برابر می شود). بدیهی است که زمان جستجوی هر دو روش به صورت خطی با تعداد نقاط هدف افزایش می یابد. علاوه بر این، زمان جستجوی روش تکراری نقاط هدف همچنان بهتر از روش تکراری نقاط مبدا است. شکل 9 تغییرات آستانه β و β را نشان می دهدبا تعداد متفاوتی از نقاط هدف در این آزمایش. همانطور که از تصویر مشخص است، آستانه β یک ثابت است و همیشه از β بیشتر است. بنابراین منطقی است که زمان جستجوی روش تکرار نقاط هدف کمتر از روش تکرار نقاط مبدا در این آزمایش باشد. علاوه بر این، اگرچه میانگین واقعی بتا نسبت تکرار کمی نوسان داشت، اما در کل ثابت ماند. به عبارت دیگر، برای مجموعه های داده با عناصر تولید شده به طور تصادفی، تا زمانی که M به اندازه کافی بزرگ باشد، تغییر M منجر به تغییر قابل توجهی در β نخواهد شد.

شکل 10 و شکل 11 به ترتیب مصرف زمان ساخت درخت KD و جستجوی داده این دو روش را با تعداد ابعاد چرخه ای متفاوت نشان می دهد. در این آزمایش، K = 6، N = M = 2 21 ، C از 0 تا 6 متغیر است و هر بار 1 افزایش می یابد. برای روش آینه ای مبتنی بر تکرار نقاط هدف، زمان ساخت درخت KD با تغییر تعداد ابعاد چرخه ای تغییر نمی کند. با این حال، زمان ساخت روش آینه ای بر اساس تکرار نقاط منبع کمی بیشتر از نرخ رشد خطی افزایش می یابد. با توجه به تجزیه و تحلیل قبلی در مورد پیچیدگی زمان ساخت روش تکرار نقاط منبع (معادله (1))، مشتق آن به بعد چرخه ای است:

∂(C+1)Nlog2((C+1)N)∂C=Nlog2((C+1)N)+N/ln2∂C+1Nlog2C+1N∂C=Nlog2C+1N+N/ln2

جمله اول در سمت راست معادله (8) با افزایش C به آرامی افزایش می یابد، در حالی که جمله دوم یک ثابت است. بنابراین روند زمان ساخت روش تکثیر نقاط مبدا منطقی است. شکل 11 نشان می دهد که زمان جستجوی روش تکرار نقاط هدف اساساً با تعداد ابعاد چرخه ای خطی است. این به این دلیل است که مشتق زمان جستجوی روش تکرار نقاط هدف (معادله (4)) به بعد چرخه ای است:

∂(βC+1)Mlog2N∂C∝∂β∂CC+β∂�C+1Mlog2N∂C∝∂�∂CC+�
در این آزمایش تعداد نقاط مبدا و نقاط هدف بدون تغییر باقی می‌مانند و همه این نقاط به طور مساوی توزیع می‌شوند و دامنه هر بعد یکسان است، بنابراین نسبت واقعی تکرار نقطه هدف برای هر بعد تقریباً یکسان است، یعنی β را می توان به عنوان یک ثابت در نظر گرفت. بنابراین منطقی است که زمان جستجوی روش تکرار نقاط هدف به صورت خطی با تعداد ابعاد چرخه ای در این آزمایش افزایش یابد. زمان جستجوی روش تکرار نقاط مبدا به طور نامنظم با بعد چرخه ای تغییر می کند و همیشه (به جز C = 0) از روش تکرار نقاط هدف بیشتر است.

4. نتیجه گیری

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

منابع

  1. لهنر، اف. جوس، اف. Raible، CC; میگنوت، جی. متولد، A. کلر، KM; Stocker، TF آب و هوا و دینامیک چرخه کربن در یک شبیه سازی CESM از 850 تا 2100 CE. سیستم زمین دین 2015 ، 6 ، 411-434. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
  2. جونز، PW طرح‌های نگاشت مجدد محافظه کارانه مرتبه اول و دوم برای شبکه‌ها در مختصات کروی. دوشنبه Weather Rev. 1999 , 127 , 2204-2210. [ Google Scholar ] [ CrossRef ]
  3. ژانگ، اف سی؛ Sun, XG کاربرد روش درون یابی وزنی با فاصله معکوس در میدان دمایی نقطه دمای محدود. Appl. مکانیک. ماتر 2014 ، 599-601 ، 1268-1271. [ Google Scholar ] [ CrossRef ]
  4. هوانگ، اچ. کوی، سی. چنگ، ال. لیو، کیو. وانگ، جی. الگوریتم درونیابی شبکه بر اساس جستجوی سریع نزدیکترین همسایه. علوم زمین به اطلاع رساندن. 2012 ، 5 ، 181-187. [ Google Scholar ] [ CrossRef ]
  5. کیم، K.-H. شیم، ص. Shin, S. یک روش درونیابی دوخطی جایگزین بین شبکه های کروی. Atmosphere 2019 ، 10 ، 123. [ Google Scholar ] [ CrossRef ] [ نسخه سبز ]
  6. گاتمن، A. R-Trees: یک ساختار شاخص پویا برای جستجوی فضایی. در خواندن در سیستم های پایگاه داده ; Morgan Kaufmann Publishers Inc.: Burlington, MA, USA, 1988; صص 599-609. [ Google Scholar ]
  7. امریش، تی. گراف، اف. کریگل، اچ. شوبرت، ام. Thoma، M. بهینه سازی پرس و جوهای نزدیکترین همسایه با هرس مثلثاتی. در مدیریت پایگاه های علمی و آماری ; Springer: برلین/هایدلبرگ، آلمان، 2010; صص 501-518. [ Google Scholar ]
  8. تائو، ی. ژانگ، جی. پاپادیاس، دی. Mamoulis, N. یک مدل هزینه کارآمد برای بهینه سازی جستجوی نزدیکترین همسایه در فضاهای با ابعاد کم و متوسط. IEEE Trans. بدانید. مهندسی داده 2004 ، 16 ، 1169-1184. [ Google Scholar ]
  9. Jones, PW A User’s Guide for SCRIP: A Spherical Coordinate Remapping and Interpolation Package ، نسخه 1.4. 1998; در دسترس آنلاین: https://forge.ipsl.jussieu.fr/igcmg/export/1677/CPL/oasis3/trunk/src/mod/oasis3/doc/SCRIPusers.pdf (دسترسی در 10 ژوئن 2022).
  10. بنتلی، JL درخت های جستجوی دوتایی چند بعدی که برای جستجوی انجمنی استفاده می شوند. اشتراک. ACM 1975 ، 18 ، 509-517. [ Google Scholar ] [ CrossRef ]
  11. فریدمن، جی اچ. بنتلی، جی ال. Finkel, RA الگوریتمی برای یافتن بهترین تطابق در زمان مورد انتظار لگاریتمی. ACM Trans. ریاضی. نرم افزار 1977 ، 3 ، 209-226. [ Google Scholar ] [ CrossRef ]
  12. براون، RA ساخت یک درخت k -d متعادل در زمان O( kn log n ). جی. کامپیوتر. نمودار. فنی 2015 ، 4 ، 50-68. [ Google Scholar ]
  13. کائو، ی. ژانگ، XJ؛ Duan، BH; ژائو، دبلیو. وانگ، اچ. یک روش بهبود یافته برای ساخت درخت KD بر اساس نتایج از پیش مرتب شده. در مجموعه مقالات یازدهمین کنفرانس بین المللی مهندسی نرم افزار و علم خدمات، پکن، چین، 16 تا 18 اکتبر 2020؛ صص 71-75. [ Google Scholar ]
  14. کائو، ی. وانگ، HZ; ژائو، WJ; دوان، بی. Zhang, X. روشی جدید برای ساخت درخت KD بر اساس نتایج از پیش مرتب شده. پیچیدگی 2020 ، 2020 ، 8883945. [ Google Scholar ] [ CrossRef ]
  15. آگاروال، پی کی; فاکس، ک. موناگالا، ک. Nath، A. الگوریتم های موازی برای ساخت ساختارهای داده جستجوی محدوده و نزدیکترین همسایه. در مجموعه مقالات سی و پنجمین سمپوزیوم ACM SIGMOD-SIGACT-SIGAI در اصول سیستم های پایگاه داده (PODS’ 16)، سانفرانسیسکو، کالیفرنیا، ایالات متحده آمریکا، 26 ژوئن تا 1 ژوئیه 2016. [ Google Scholar ]
  16. شیائو، بی. Biros، G. الگوریتم های موازی برای مسائل جستجوی نزدیکترین همسایه در ابعاد بالا. SIAM J. Sci. محاسبه کنید. 2016 ، 38 ، 667-699. [ Google Scholar ] [ CrossRef ]
  17. پاتواری، م. ساتیش، NR; ساندارام، ن. لیو، جی. سادوسکی، پ. راچه، ای. باینا، س. تول، سی. بهیمجی، دبلیو. Dubey، P. PANDA: مقیاس افراطی موازی K-نزدیکترین همسایه در معماری های توزیع شده. در مجموعه مقالات سمپوزیوم بین المللی پردازش موازی و توزیع شده (IPDPS)، شیکاگو، IL، ایالات متحده آمریکا، 23 تا 27 مه 2016. صص 494-503. [ Google Scholar ]
  18. هو، ال. نوش آبادی، س. احمدی، م. Linjia، H. الگوریتم‌های جست‌وجوی درخت KD به‌طور انبوه موازی و نزدیک‌ترین همسایه. در مجموعه مقالات سمپوزیوم بین المللی IEEE در مورد مدارها و سیستم ها (ISCAS)، لیسبون، پرتغال، 24-27 مه 2015. جلد 5، ص 2752–2755. [ Google Scholar ]
  19. هو، دبلیو. لی، دی. خو، سی. Li، T. یک الگوریتم طبقه‌بندی پیشرفته k نزدیکترین همسایه بر اساس KD-tree. در مجموعه مقالات کنفرانس بین المللی IEEE 2018 اطلاعات اطلاعات تولید ایمنی (IICSPI)، چونگ کینگ، چین، 10 تا 12 دسامبر 2018؛ ص 902-905. [ Google Scholar ]
  20. هاوران، وی. Bittner, J. در مورد بهبود KD-Trees برای تیراندازی با اشعه. در مجموعه مقالات دهمین کنفرانس بین المللی در اروپای مرکزی در زمینه گرافیک کامپیوتری، تجسم و چشم انداز کامپیوتری 2002 (WSCG 2002)، پیلسن، چک، 4 تا 8 فوریه 2002. [ Google Scholar ]
  21. Guo, J. تحقیق کاربردی الگوریتم ICP بهبود یافته بر اساس KD Tree در ثبت Cloud نقطه. میکروکامپیوتر. برنامه آن است. 2015 ، 34 ، 81-84. [ Google Scholar ]
  22. او، جی. وو، ی. یانگ، اف. یین، CL; ژو، W. شاخص ابر چند بعدی بر اساس درخت KD و درخت R. جی. کامپیوتر. Appl. 2014 ، 34 ، 3218-3221. [ Google Scholar ]
  23. Guo، ZZ; او، ZQ; ژائو، WW; Chen، WF تغییر شکل مش کارآمد و روش درونیابی میدان جریان برای مش های بدون ساختار. آکتا هوانورد. فضانورد. گناه 2018 ، 39 ، 132-143. [ Google Scholar ]
  24. Guo، ZZ; او، ZQ; Xia، CC; روش درخت چن، W. KD برای محاسبه فاصله دیواری کارآمد مش. J. Natl. دانشگاه Def. تکنولوژی 2017 ، 39 ، 21-25. [ Google Scholar ]
  25. کائو، ی. وانگ، بی. ژائو، WJ; ژانگ، ایکس. وانگ، اچ. تحقیق در مورد الگوریتم های جستجو برای نگاشت مجدد شبکه بدون ساختار بر اساس درخت KD. در مجموعه مقالات سومین کنفرانس بین المللی فناوری مهندسی کامپیوتر و ارتباطات، پکن، چین، 14 تا 16 اوت 2020؛ ص 29-33. [ Google Scholar ]
  26. Hoare, C. Quicksort. محاسبه کنید. J. 1962 , 5 , 10-15. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
  27. کورمن، تی. لیزرسون، سی. Rivest, R. Introduction to Algorithms , 3rd ed.; انتشارات MIT: کمبریج، MA، ایالات متحده آمریکا، 2009. [ Google Scholar ]
Ijgi 11 00392 g001 550
شکل 1. نمودارهای شماتیک روش های آینه ای. ( الف ) روش آینه ای مبتنی بر تکرار نقاط مبدأ است و ( ب ) روش آینه ای مبتنی بر تکرار نقاط هدف است.
Ijgi 11 00392 g002 550
شکل 2. فرآیند روش آینه بر اساس تکرار نقاط منبع.
Ijgi 11 00392 g003 550
شکل 3. فرآیند روش آینه بر اساس نقاط هدف تکراری.
Ijgi 11 00392 g004 550
شکل 4. زمان ساخت با تعداد نقاط منبع مختلف.
Ijgi 11 00392 g005 550
شکل 5. زمان جستجو با تعداد متفاوت نقاط منبع.
Ijgi 11 00392 g006 550
شکل 6. تغییر آستانه β و β با تعداد نقاط منبع متفاوت.
Ijgi 11 00392 g007 550
شکل 7. گره ای که در طول فرآیند جستجو با تعداد متفاوتی از نقاط منبع قابل دسترسی است.
Ijgi 11 00392 g008 550
شکل 8. زمان جستجو با تعداد متفاوت نقاط هدف.
Ijgi 11 00392 g009 550
شکل 9. تغییر آستانه β و β با تعداد نقاط هدف متفاوت.
Ijgi 11 00392 g010 550
شکل 10. زمان ساخت با تعداد متفاوت ابعاد چرخه ای.
Ijgi 11 00392 g011 550
شکل 11. زمان جستجو با تعداد متفاوت ابعاد چرخه ای.

مقالات داخلی و بین المللی

مطالب مرتبط ...

9 نظرات

دیدگاهتان را بنویسید