12231

12231

راه‌كاري براي جستجوي نزديك‌ترين همسايه‌ها به گروهي از پرس و جوها

كارشناسي ارشد

كامپيوتر - گرايش نرم‌افزار

مهرماه 1392

مهرماه 1392

دكتر حسن نادري

چكيده امروزه گسترش علوم كامپيوتري و توليد حجم انبوهي از اطلاعات، باعث شده تا نياز به راه‌كارها، روش‌ها و الگوريتم‌هاي مختلف جستجو بر روي داده‌ها افزايش يابد. اين رشد روزافزون باعث به وجود آمدن پيچيدگي‌هاي زماني و محاسباتي زيادي شده است. امروزه راه‌كارهاي مختلفي براي حل اين‌گونه مسائل به وجود آمده به طوري كه يكي از بهترين آن‌ها، جستجوي نزديك‌ترين همسايه است. اين راه‌كارها به دليل تنوع زياد علاوه بر رفع برخي از پيچيدگي‌ها، توانسته‌اند در مسائل و كاربردهاي گوناگون مانند تشخيص الگو، بازيابي اطلاعات، تشخيص متن و سيستم‌هاي چندرسانه‌اي نيز استفاده شوند. از جمله راه‌كارهاي مطرح در جستجوي نزديك‌ترين همسايه، جستجوي نزديك‌ترين همسايه گروهي است. در اين راه‌كار با توجه به حجم داده‌ها، روش‌هاي گوناگوني مطرح‌شده به طوري كه معمولاً در محيط‌هايي با حجم بالاي نقاط پرس و جو، پردازش سنگيني را انجام داده و بنابراين سرعت بالايي از خود بُروز نمي‌دهند. همچنين در يكي از اين راه‌كارها، به دليل فراخواني‌هاي متعدد يك تابع، سرعت اجرا كاهش يافته است. آنچه در اين پايان‌نامه به آن پرداخته مي‌شود، شامل سه بخش است. در بخش اول با نگاهي جديد به مسئله جستجوي نزديك‌ترين همسايه، بررسي جامعي بر روي ساختارها، راه‌كارها و الگوريتم‌هاي مختلف موجود در اين زمينه انجام‌شده و يك تقسيم‌بندي جديد ارائه شده است. اين تقسيم‌بندي شامل دو ساختار كلي درهم‌سازي و درخت در قسمت ساختارها و راه‌كارهاي ساده، وزن‌دار، كاهشي، افزايشي، معكوس، پيوسته، محدودشده، محور اصلي و گروهي در قسمت راه‌كارها مي‌باشد. همچنين مقايسه جامعي بين ساختارها و راه‌كارهاي مطرح‌شده انجام گرفته است. در قسمت دوم اين پايان‌نامه دو راهكار كلي براي جستجوي نزديك‌ترين همسايه ارائه شده است. اين راه‌كارها كه در جستجوي نزديك‌ترين همسايه گروهي نيز قابل‌استفاده هستند، با دقت كامل و كارايي بالا به پردازش پرس و جو پرداخته و نزديك‌ترين همسايه آن را محاسبه مي‌كنند. در راه‌كار اول با انجام يك بهينه‌سازي در صف‌هاي اولويت، سرعت عملكرد سيستم افزايش مي‌يابد. راه‌كار دوم كه يك راه‌كار جديد محسوب مي‌شود، با استفاده از آرايه‌هاي مرتب به محاسبه نزديك‌ترين همسايه مي‌پردازد. در قسمت سوم كه بخش اصلي پايان‌نامه است، جستجوي نزديك‌ترين همسايه گروهي بيشتر مورد بررسي قرارگرفته و دو روش جديد براي آن ارائه شده است. در روش اول يك هرس جديد براي داده‌ها تعريف‌شده به طوري كه به بهبود سرعت سيستم مي‌انجامد. در روش دوم نيز با استفاده از خلاصه‌سازي داده‌ها، كارايي سيستم افزايش يافته است. نتايج و ارزيابي‌هاي صورت گرفته در اين پايان‌نامه، بهبود عملكرد و افزايش كارايي را در راه‌كارهاي ارائه‌شده نشان مي‌دهد. به طور كلي در سه راه‌كار اول بدون اينكه دقت عملكرد سيستم كاهش يابد، كارايي بالا رفته است. در راه‌كار آخر (خلاصه‌سازي) نيز با حداقل كاهش ممكن در دقت، كارايي جستجوي نزديك‌ترين همسايه گروهي بهبود يافته است. واژه‌هاي كليدي: جستجوي نزديك‌ترين همسايه، فضاي متريك، محيط ايستا، گروهي از پرس و جوها، فاصله تجمعي، پردازش پرس و جو، NNS، kNN