12440

12440

پردازش پرس‌و‌جو‌‌هاي نزديك‌ترين همسايه‌ي متقابل پيوسته بر روي جريان داده‌هاي زماني‌-‌مكاني

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

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

آبان 1392

آبان 1392

دكتر بهروز مينائي

چكيده افزايش روز‌افزون استفاده از سرويس‌هاي مكان‌آگاه و پيشرفت‌هاي سريع در فناوري‌هايي كه قادر به رديابي اشياء متحرك هستند، منجر به بوجود آمدن تكنيك‌هايي براي پردازش پرس‌و‌جو‌‌هاي زماني‌-‌مكاني پيوسته گرديده است. اين‌گونه سيستم‌ها عمدتاً با حجم بالايي از داده‌هاي ورودي سر‌و‌كار دارند. اين داده‌ها اغلب توسط اشياء متحرك به سيستم ارسال مي‌گردند. با توجه به اين‌كه داده‌هاي ارسالي توسط اشياء متحرك به سيستم وارد مي‌شوند، حجم به‌روز‌رساني‌ها در اين‌گونه سيستم‌ها بسيار بالا است. روش‌هاي مختلفي براي پردازش اين‌گونه داده‌ها مطرح گرديده است. در اين روش‌ها سعي بر پردازش‌پرس‌و‌جو‌‌ها با در نظر گرفتن تكنيك‌هايي براي كاهش زمان اجرا و حجم حافظه‌ي مصرفي گرديده است. از جمله پرس‌و‌جو‌‌هايي كه بر روي اين نوع از داده‌ها اعمال گرديده و بسيار مورد توجه بوده است، پردازش پرس‌و‌جو‌ي نزديك‌ترين همسايه‌ي پيوسته است. در اين‌گونه پرس‌و‌جو‌‌ها با در نظر گرفتن مكان نقطه‌ي پرس‌و‌جو‌ به صورت پيوسته اشياءاي كه به نقطه‌ي مورد نظر نزديك‌ترند شناسايي و معرفي مي‌گردند. نوع خاصي از اين‌گونه پرس‌و‌جو‌‌ها، پرس‌و‌جو‌‌هاي نزديك‌ترين همسايه‌ي متقابل پيوسته است. اين پايان‌نامه به ارائه‌ي روشي نوين براي پاسخ‌گويي به اين نوع از پرس‌و‌جو‌‌ها پرداخته است. خاصيت اين نوع پرس‌و‌جو‌‌ها در اين است كه پاسخ اين پرس‌و‌جو‌‌ها نقاطي هستند كه علاوه بر‌اين‌كه اين نقاط جزء نزديك‌ترين نقاط پرس‌و‌جو‌ هستند، توأماً نقطه‌ي پرس‌و‌جو‌ نيز جزء نزديك‌ترين نقاط به اشياء مورد نظر است. در روش ارائه شده هيچ محدوديتي براي حركت اشياء و پرس‌و‌جو‌‌ها در نظر گرفته نشده است. شاخص‌گذاري اشياء با استفاده از شاخص‌گذاري گريد انجام شده است. براي پاسخ‌گويي به پرس‌و‌جو‌‌هاي نزديك‌ترين همسايه‌ي متقابل در اين پايان‌نامه از تكنيك‌هاي يافتن نزديك‌ترين همسايه و نزديك‌ترين همسايه‌ي معكوس استفاده شده است. هم‌چنين با در نظر گرفتن نواحي نظارت قادر به پاسخ‌گويي به پرس‌و‌جو‌‌ها به صورت افزايشي شده‌ايم. مهم‌ترين ويژگي روش پيشنهادي ارزيابي افزايشي پرس‌و‌جو‌‌ها و قابليت گسترش‌پذيري آن است. با توجه به آزمايش‌هاي انجام شده بر روي داده‌ها با شرايط متفاوت، كارايي روش پيشنهادي نشان داده شده است. هم‌چنين آزمايش‌ها نشان مي‌دهد كه روش پيشنهادي از سرعت بسيار بالايي برخوردار است. واژه‌هاي كليدي: زماني‌-‌مكاني ، نزديك‌ترين همسايه، نزديك‌ترين همسايه معكوس، اشياء متحرك، پرس‌و‌جو‌‌هاي پيوسته.