17215

17215

ارائه‌ي روشي توزيع شده براي شاخص گذاري داده‌هاي خط‌سير اشياي متحرك

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

نرم افزار

خردادماه 1395

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

كامپيوتر

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

1396/02/10

3/21/2018 12:00:00 AM

The proliferation of positioning devices such as smart phones, RFID tags an​d vehicle navigation systems an​d development in wireless technologies have resulted in an increasing growth in location-based services. Tracking moving objects has many applications in different areas such as traffic an​d transportation management systems, tourism an​d location-based social networks. As a result of this process massive amounts of data is produced. Storing an​d processing this amount of data requires a great deal of resources an​d time which highlights the need for scalable an​d efficient methods to store data an​d answer queries. A reasonable solution which have gained a lot of interest over the past few years is horizontal scaling an​d usage of distributed methods to store an​d retrieve spatial-temporal data. Very few works have been done around this subject an​d some of them ignore the temporal aspect of data an​d only index spatial part. This point of view limits us on using a wide range of queries an​d using gathered data for applications such as congested parts over a certain time period. Also in some works the emphasis is on a certain property of data such as the volume an​d the need to decrease that. In this research our emphasis is on the range queries, both spatial an​d temporal. We also consider the nearest neighbor queries an​d try to come up with a distributed storage system which can efficiently store, index an​d answer queries for spatial-temporal data on road networks. At the end we also eva​luate the proposed method an​d show the results on a cluster of commodity computers. Keywords: moving objects, trajectory, spatial-temporal data, indexing, map-reduce