آقای علی اکبر عباسی دانشجوی کارشناسی ارشد جناب آقای دکتر مصطفی حق جو روز یکشنبه 27/9/90 ساعت 9:30 در اتاق 304 واقع در طبقه سوم دانشکده کامپیوتر از پروژه کارشناسی ارشد خود تحت عنوان توسعه پرس و جوی نزدیکترین همسایه و بهبود روشهای پاسخ گویی به آن دفاع خواهند نمود.

  چکیده پایان نامه:

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

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

  روش پیشنهادی ما، هم‌چون روش عادی برای پاسخ‌گویی به پرس‌وجوی نزدیک‌ترین همسایه، برمبنای ساختار شاخص‌گذاری R-tree کار می‌کند. در روش عادی، از هرس‌هایی برای محدود کردن بازه‌ی جستجو استفاده می‌شود که تأثیر قابل توجهی بر کارآیی پاسخ‌گویی دارند. روش ما علاوه بر این هرس‌ها، از نتیجه‌ی پرس‌وجوی‌های پیشین نیز استفاده می‌کند و به این ترتیب، زمان کلی پاسخ‌گویی به پرس‌وجو را با صرف هزینه‌ای اندک، کاهش می‌دهد. نتایج تحلیل‌های نظری و آزمون‌های عملی‌ که در این پایان‌نامه ارائه شده‌اند، برتری روش ما را نسبت به روش عادی نشان می‌دهند.

واژه‌های کلیدی: پایگاه‌داده‌ی فضایی، پرس‌وجوی فضایی، R-tree ، پرس‌وجوی نزدیک‌ترین همسایه، پرس‌وجوی نزدیک‌ترین k همسایه.

  Abstract:

  Progression in database knowledge and technology causes new and special applications to be found, and new DBMSs and database systems to be developed. Temporal, spatial, and spatiotemporal databases are some instances of special-purpose database systems that have been appeared years ago and have broad range of applications today. For example, in the geographic information systems (GIS) and content-based multimedia retrieval systems, these kind of special-purpose database systems are very common today. One of the appealing fields of database technology for researchers is spatial queries. Using spatial access methods for answering these queries, the huge size of datasets, applications with special constraints and conditions, are some reasons of this appeal. Spatial range query, nearest neighbor query, and closest pair query are some useful kinds of spatial queries.

  This thesis is the result of writer’s researches and contributions to increase the efficiency of answering to various types of nearest neighbor query. Because of reasons such as numerous applications, the necessity of efficient answering methods, variety of types and constraints, and so on, nearest neighbor query has been chosen. Our proposed method for nearest neighbor query processing is based on storing the answers and using the hidden information coming from old results to answer new queries. In other words, hidden information coming form results of old queries is used for restricting the search range and reducing the cost of processing of new answers. The final goal of this kind of improvement is reducing the number of access to secondary memory that is a bottleneck for database systems.

  Our method, like the older one, is based on R-tree index structure. In the older method some pruning techniques are exploited to restrict the search range. This restriction improves the efficiency of processing dramatically. Our method uses the answers of old queries plus these pruning techniques in a way that reduces the overall turn-around time in price of a little computational cost. The experimental results presented here, show the advantages of our method against the classic one.

  Keywords: Spatial database, Spatial query, R-tree, Nearest neighbor query , k nearest neighbor query.

  ارائه­دهنده:

  علی اکبر عباسی

  اساتید راهنما:

  دکتر مصطفی حق جو

  استاد ممتحن داخلی : دکتر حسن نادری

  استاد ممتحن خارجی :دکتر مسعود رهگذر

  زمان : یکشنبه 27 آذرماه

  ساعت 9:30

  مکان: دانشکده مهندسی کامپیوتر- طبقه سوم- اتاق 304

  از اساتید بزرگوار، دانشجویان گرامی و دیگر متخصصان و علاقه مندان به موضوع دفاعیه دعوت
می شود با حضور خود موجبات غنای علمی و ارتقای کیفی را فراهم سازند.

  دانشکده مهندسی کامپیوتر مدیریت تحصیلات تکمیلی