شماره ركورد
9992
شماره راهنما(اين فيلد مربوط به كارشناس ميباشد لطفا آن را خالي بگذاريد)
9992
پديد آورنده
علياكبر عباسي
عنوان
توسعهي پرسوجوي نزديكترين همسايه و بهبود روشهاي پاسخگويي به آن
مقطع تحصيلي
درجهي كارشناسي ارشد
رشته تحصيلي
مهندسي كامپيوتر گرايش نرمافزار
سال تحصيل
آذرماه 1390
تاريخ دفاع
آذرماه 1390
استاد راهنما
دكتر مصطفي حقجو
چكيده
چكيده
با پيشرفت فنآوري و دانش پايگاهداده، كاربردهاي جديد و ويژهاي براي آن پيدا ميشود كه باعث پديد آمدن و گسترشِ سيستمهاي مديريت پايگاهداده و پايگاهدادههاي خاصمنظوره شده است و خواهد شد. پايگاهدادههاي زماني، فضايي و فضازماني نمونههايي از پايگاهدادههاي خاصمنظورهاند كه داراي پيشينهاي نسبتاً طولاني و كاربردهاي گسترده هستند. براي نمونه در سيستمهاي اطلاعات جغرافيايي و سيستمهاي بازيابي محتواي چندرسانهاي، حضور اين نوع پايگاهدادههاي خاصمنظوره، متداول است.
پايگاهدادههاي خاصمنظوره در سايهي نيازهاي جديد و ويژه شكل گرفتهاند و در راستاي تحقق آنها بايد به دنبال راهكارها، فنآوريها و دانشهاي ويژهاي رفت. براي نمونه ساختار شاخصگذاريِ متداول B+-Tree جوابگوي شاخصگذاريِ دادههاي فضايي نيست و محققان تلاش كردهاند كه جايگزين مناسب و كارآيي براي آن بيابند. حاصل تلاشهاي محققان، ساختارهاي شاخصگذاري فضايي بوده است كه از متداولترين آنها، خانوادهي ساختارهاي شاخصگذاري R-tree هستند.
يكي از جالبترين موضوعاتي كه محققانِ زمينهي پايگاهدادهها را به خود جلب ميكند، پاسخگويي به پرسوجوهاي فضايي است. استفاده از ساختارهاي شاخصگذاري فضايي براي پاسخگويي به پرسوجوهاي فضايي، بزرگ بودن حجم دادهها، كاربردهايي با شرايط و محدوديتهاي خاص، از جمله دلايل افزايش اين جذابيت هستند. پرسوجويِ نقاط محدودهي اطراف يك نقطه، نزديكترين همسايه(هاي) يك نقطه، و نزديكترين جفت شيء، از نمونههاي پركاربردِ پرسوجوهاي فضايي هستند.
پاياننامهي پيشِ رو، نتيجهي پژوهشها و تلاشهاي نگارنده در راستاي بهبود پاسخگويي به پرسوجوي نزديكترين همسايهي يك نقطه، در اشكال و صورتهاي مختلف آن است. اين پرسوجو به دليل كاربردِ فراوان، اهميت كارآيي براي پاسخگويي به آن، تنوع در انواع و شرايط پرسوجو، و دلايلي از اين دست، انتخاب شده است و توجه ويژهي بزرگان عرصهي پايگاهدادههاي فضايي به اين پرسوجو، مهر تأييدي بر درستي اين انتخاب است. هدف اوليهي نگارنده، تلاش در جهتِ شناخت و بسط پرسوجوي نزديكترين همسايهي يك نقطه، و بهبود پاسخگويي به آن، تحت شرايط و در شكلها گوناگون آن است.
پيشنهاد ما براي بهبود پاسخگويي به پرسوجوي نزديكترين همسايههاي يك نقطه، نگهداري نتايج پرسوجوها و استفاده از دانش نهفته در اين نتايج براي پاسخگويي به پرسوجوهاي بعدي است. به عبارت ديگر، از دانش نهفته در پاسخِ پرسوجوهاي پيشين، براي محدود كردن بازهي جستجو و كاهش هزينه، استفاده ميشود. هدف نهايي از بهينهسازي، كاهش تعداد دسترسي به حافظهي جانبي است كه در سيستمهاي پايگاهداده يك گلوگاه به شمار ميرود.
روش پيشنهادي ما، همچون روش عادي براي پاسخگويي به پرسوجوي نزديكترين همسايه، برمبناي ساختار شاخصگذاري R-tree كار ميكند. در روش عادي، از هرسهايي براي محدود كردن بازهي جستجو استفاده ميشود كه تأثير قابل توجهي بر كارآيي پاسخگويي دارند. روش ما علاوه بر اين هرسها، از نتيجهي پرسوجويهاي پيشين نيز استفاده ميكند و به اين ترتيب، زمان كلي پاسخگويي به پرسوجو را با صرف هزينهاي اندك، كاهش ميدهد. نتايج تحليلهاي نظري و آزمونهاي عملي كه در اين پاياننامه ارائه شدهاند، برتري روش ما را نسبت به روش عادي نشان ميدهند.
واژههاي كليدي: پايگاهدادهي فضايي، پرسوجوي فضايي، R-tree، پرسوجوي نزديكترين همسايه، پرسوجوي نزديكترين k همسايه.