پديد آورندگان :
نصيري، افسانه دانشگاه تهران - پرديس دانشكده هاي فني - دانشكده مهندسي نقشه برداري و اطلاعات مكاني , عظيمي، ساناز دانشگاه تهران - پرديس دانشكده هاي فني - دانشكده مهندسي نقشه برداري و اطلاعات مكاني , عباسپور، رحيم علي دانشگاه تهران - پرديس دانشكده هاي فني - دانشكده مهندسي نقشه برداري و اطلاعات مكاني
كليدواژه :
خط سير مكاني-زماني , فشرده‌سازي , الگوريتم SQUISH-E , پنجره اولويت
چكيده فارسي :
با توسعه روزافزون دستگاه‌هاي همراه مجهز به سيستم تعيين موقعيت جهاني مانند گوشي‌هاي هوشمند همراه، حجم زيادي از اطلاعات مكاني توليد مي‌شود. اين داده‌ها كه بيشتر به صورت دنباله‌اي از نقاط مكاني در طول زمان ذخيره و مدل‌سازي مي‌شوند، خط سير نام دارند. حجم بالاي داده‌هاي خطوط سير هزينه انتقال، ذخيره‌سازي و پردازش اين داده‌ها را بالا برده است. براي برطرف نمودن اين مشكلات، تعدادي از الگوريتم‌هاي فشرده‌سازي، با رويكرد كاهش تعداد نقاط مسير مطرح شده است. در اين مقاله، هفت الگوريتم نمونه‌برداري يكنواخت، داگلاس پوكر، الگوريتم نسبت زماني بالا- پايين، پنجره متحرك، پنجره متحرك-نسبت زماني، الگوريتم سرعت مبنا بالا-پايين وSQUISH-E (Spatial QUalIty Simplification Heuristic - Extended) مورد بحث قرار گرفتند و مزايا و معايب هر يك بررسي شد. در اين ميان الگوريتمSQUISH-E ، قادر به برقراري تعادل بين نسبت فشرده‌سازي و خطاي فاصله اقليدسي همزماني است در حالي كه نرخ فشرده‌سازي بالايي نسبت به ساير روش‌ها دارد. به منظور رفع اين مشكل، در اين مقاله راهكاري براي متغير كردن پنجره اولويت الگوريتم SQUISH-E ارائه شد كه موجب بهبود نرخ فشرده‌سازي الگوريتم مي‌شود. به منظور بررسي عملكرد روش يشنهادي، تمامي الگوريتم‌ها روي شش زير مسير با پيچيدگي‌هاي مختلف پياده‌سازي شده و با يكديگر از نظر معيارهايي مانند نرخ فشرده‌سازي، زمان اجرا و خطاي فاصله اقليدسي همزماني مقايسه شدند. نتايج به‌دست آمده حاكي از بهبود عملكرد الگوريتم پيشنهادي در نرخ فشرده‌سازي، زمان اجرايي و خطاي فاصله اقليدسي همزماني مي‌باشد. زمان الگوريتم پيشنهادي نسبت به الگوريتم SQUISH-E حدود 130 ميلي‌ثانيه كاهش و نرخ فشرده‌سازي آن 015/0 افزايش يافته است.
چكيده لاتين :
With development of mobile devices equipped with a global positioning system, such as smartphones, large amounts of spatial information are generated. These data, which are often stored and modeled as a sequence of spatial locations over time, are called trajectory. The large amount of trajectory data has increased the cost of transferring, storing and processing such data. To overcome these problems, a number of compression algorithms have been proposed for reducing the size of trajectory data. In this paper, seven algorithms including uniform sampling, Douglas Poker, TD-TR, Opening Window, OPW-TR, TD-SB and SQUISH-E algorithms are being discussed and the advantages and disadvantages of these algorithms are investigated as well. The SQUISH-E algorithm can create a balance between the compression rate and the Synchronized Euclidean Distance error, but has a high compression rate than other compression algorithms. To solve mentioned problem, this paper proposed a method for changing the priority window of the SQUISH-E algorithm, which improves the compression rate of this algorithm. In order to evaluate the performance of the proposed method, all algorithms are implemented on six trajectories of varying complexity and compared with each other in terms of criteria such as compression rate, run-time, and concurrency Euclidean distance errors. The results of implementation of the proposed method indicate the improvement of the proposed algorithm at the compression rate, computation time, and Synchronized Euclidean Distance error. In compare to SQUISH-E algorithm, the computation time and compression rate of proposed algorithm is decreased about 130 millisecond and 0.015, respectively.
