نیازندیهای فایلی کرجی
دانلود انواع پایان نامه، مقاله، طرح، پروژه، جزوه، گزارش کار، پروپوزال، آزمون استخدامی، نمونه سوال و ...نیازندیهای فایلی کرجی
دانلود انواع پایان نامه، مقاله، طرح، پروژه، جزوه، گزارش کار، پروپوزال، آزمون استخدامی، نمونه سوال و ...ترجمه بخشی از کتاب Spatial Data Management به همراه کتاب اصلی
| دسته بندی | مقالات ترجمه شده |
| بازدید ها | 17 |
| فرمت فایل | docx |
| حجم فایل | 2681 کیلو بایت |
| تعداد صفحات فایل | 22 |
Spatial Data Management
&MC Morgan & Claypool Publishers
SYNTHESIS LECTURES ON DATA MANAGEMENT
M. Tamer Özsu, Series Editor
Spatial
Data Management
Nikos Mamoulis
کتاب اصلی 151 صفحه می باشد
مدل شبکه های فضایی (قسمتی از فصل 5 را بخوانید)
شبکه فضایی یک گراف است ، که در آن گره به اتصال (به عنوان مثال، محل اتصال) نقاط بین است بخش های پیوسته متناظر است. بخشها (لبه) که دو گره را اتصال میدهد دارای هندسه ساده هستند. به طور معمول، آنها به بخش خط مستقیم یا منحنی ساده میشوند. لبه اتصال دو گره A و B می تواند یک طرفه (به عنوان مثال، از A به B) و یا دو طرفه باشد. این امکان وجود دارد که لبه های متعدد در همان جفت گره اتصال یابد. علاوه بر این، یک لبه می تواند با وزن مدل سازی هزینه حرکت در طول لبه مرتبطباشد. (به عنوان مثال، زمان سفر، هزینه سوخت). در شبکه های ساده، وزن لبه مربوط به فاصله فضایی بین گره های متصل،می باشد به عنوان مثال، طول پاره خط مربوطه. یک راه ساده برای مدل کردن یک گراف با n گره تعریف N × ماتریس n مجاورت ، که در آن هر عنصر Mij اطلاعات در مورد لبه (بازدید کنندگان) اتصال گره i و j را ذخیره میکند. شکل a یک نمونه از گراف جهت ساده، که شامل 6 گره است را نشان می دهد، تنها اکثرا یک لبه در جهت برای هر جفت از گره ها، وجود دارد و لبه ها توسط وزن برچسب دهی میشوند.ماتریس مجاورت شکل 5.2b می تواند این گراف رامدل کند. هر عنصر ماتریس وزن متناظر لبه مربوطه یا "∞ 'اگر لبه وجود ندارد، ذخیره میشود. توجه داشته باشید که اگر گراف دو طرفه بود، ماتریس مجاورت متقارن خواهد بود ، از یک لبه اتصال A و B دو لبه b→a و a →b از همان وزن هدایت میکند.
بر خلاف نمودار کلی (به عنوان مثال، گرافهای شبکه اجتماعی یا وب)، شبکه های فضایی بسیار طبیعت اسپارس است. مانند نمودار نشان داده شده در شکل 5.2a، (خروجی یا ورودی) درجه هر گره انتظار می رود کوچک باشد. به طور معمول، در شبکه های جاده ای، و یا دیگر شبکه های فضایی (به عنوان مثال، شبکه های آب شناسی)، تعداد کمی از قطعات در یک محل اتصال متصل شده است. این به این معنی است که اکثر ورودیها در ماتریس مجاورت یک شبکه فضایی شامل هیچ اطلاعاتی نیست (به عنوان مثال، توجه داشته باشید که تعداد از '∞' ورودیهادر شکل 5.2b بزرگ است) و مقدار زیادی از فضا در یک چنین نمایشی هدر رفته است. مدل داده مناسب برای گرافهای اسپارس لیست مجاور برای ذخیره اطلاعات اتصال استفاده میکند. همانطور که شکل 5.2b نشان می دهد، برای هر گرهni در گراف، ما می توانیم یک لیست از گره مجاور با ni همراه با وزن از لبه مربوطه ذخیره کنیم (به عنوان مثال، (N3، 1) در فهرست N2 نشان دهنده این است که یک لبه از N2 بهN3 با وزن 1) وجود دارد. مزیت آن این است که ما مجبور به ذخیره هر اطلاعات برای جفت گره که به طور مستقیم وصل نشده نیستیم.اشکال جزئی است که ما باید جستجوی دودویی در فهرست NI انجام دهیم اگر ما می خواهیم یک لبه (NI، NJ) بازیابی کنیم. با این حال، از آنجا که انتظار می رود که فهرست در گرافهای اسپارس کوچک باشد ، این انتظار نمی رود که یک سربار قابل توجه باشد. یکی دیگر ازمشخصه شبکه های فضایی این است که اطلاعات فضایی را حمل میکند.گره ها به محل فضایی متناظرند و لبه های فضایی نیز دارای ویژگی های مکانی هستند. بنابراین، لیست مجاور نمایانگر تنها برای حمایت موثر از جستارهای فضایی کافی نیست. علاوه بر این، اگر گراف شبکه فضایی بیش از حد بزرگ باشد که در حافظه جای گیرد ، ما باید نمایش آن را بر روی دیسک مدیریت کنیم. در بخش بعدی، ما در مورد اینکه چطور گرافهای فضایی بزرگ می تواند نمایه شود.
روش های شاخص سازی بر اساس دیسک
روش دسترسی اتصال-خوشه (CCAM) ساختمان داده حافظه های ثانویه برای گرافهای بسیار بزرگ است ، که خوشه های لیستهای مجاورت گره را به صفحات بر اساس اتصال آنها خوشه بندی میکند. هدف از شاخص راهنمای پیمایش گراف است ، در حالی که I / O حداقل میرساند.CCAM اولیه گره از گراف با B + -tree، با استفاده از شناسه آنها به عنوان کلیدی شاخص میکند.شناسه گره ها بر اساس مرتبه آنها درمنحنی Z داده میشود، (اشاره به بخش 3.1.2 برای جزئیات بیشتر در مورد دستور داده های فضایی با استفاده از منحنی پرکردن فضا)، به منظور تسهیل در جستجوی مکانی برای گره گراف استفاده میشود . هر ورودی گره برگ ازدرخت B ، مربوط به گره گراف ni، به صفحه دیسک، بر اساس معیار بهینه سازی اتصال متصل میشود .لیست مجاورت گره ها به صفحات دیسک، با توجه به معیار بهینه سازی اتصال بسته بندی میشود، که نسبت لبه ذخیره شده در لیست مجاور را به حداقل می رساند که منجر به گره های خارج از صفحه میشود. به عبارت دیگر، لیست مجاورت از گره های متصل در صفحه دیسک با احتمال بالاذخیره میشود. شکل 5.3a نشان می دهد نمودار فضایی نمونه و شکل b را متناظر با شاخص ccamنشان میدهد .دقت کنید که نمودار به دو زیرگراف تقسیم میشود ، که هرکدام مربوطه به یک صفحه دیسک از لیست مجاورمیباشد. به عنوان مثال، لیست مجاورت از N1، N3، N5 در صفحه P1 ذخیره می شود.B + -tree برای قرار سریع لیست مجاور یک گره داده شده (به عنوان مثال، N1). تراورس گراف از N1 به گره همسایه N3 متحمل I / O نیست، ازآنجا که لیست مجاور N1 و N3 در همان صفحه دیسک (P1) ذخیره می شود. نسخه اولیه CCAM اطلاعات مکانی لبه گراف را شاخص نمیکند. بنابراین،جستارهای فضایی به اطلاعات در لبه گراف برمیگردند (به عنوان مثال، اشیاء و یا مکان های فضایی که ممکن است در لبه، نه لزوما در گره گراف واقع میشوند) ممکن است موثر ارزیابی نشود.