[صفحه اصلی ]   [Archive] [ English ]  
:: صفحه اصلي :: درباره نشريه :: آخرين شماره :: تمام شماره‌ها :: جستجو :: ثبت نام :: ارسال مقاله :: تماس با ما ::
:: دوره 6، شماره 3 - ( 9-1397 ) ::
جلد 6 شماره 3 صفحات 23-38 برگشت به فهرست نسخه ها
کاهش داده‌های خطوط سیر مکانی-زمانی با به‌کارگیری یک الگوریتم فشرده‌سازی برخط
افسانه نصیری، ساناز عظیمی، رحیم علی عباسپور
دانشگاه تهران
چکیده:   (203 مشاهده)
با توسعه روزافزون دستگاه‌های همراه مجهز به سیستم تعیین موقعیت جهانی مانند گوشی‌های هوشمند همراه، حجم زیادی از اطلاعات مکانی تولید می‌شود. این داده‌ها که بیشتر به صورت دنباله‌ای از نقاط مکانی در طول زمان ذخیره و مدل‌سازی می‌شوند، خط سیر نام دارند. حجم بالای داده‌های خطوط سیر هزینه انتقال، ذخیره‌سازی و پردازش این داده‌ها را بالا برده است. برای برطرف نمودن این مشکلات، تعدادی از الگوریتم‌های فشرده‌سازی، با رویکرد کاهش تعداد نقاط مسیر مطرح شده‌ است. در این مقاله، هفت الگوریتم‌ نمونه‌برداری یکنواخت، داگلاس پوکر، الگوریتم نسبت زمانی بالا- پایین، پنجره متحرک، پنجره متحرک-نسبت زمانی، الگوریتم سرعت مبنا بالا-پایین وSQUISH-E  (Spatial QUalIty Simplification Heuristic - Extended) مورد بحث قرار گرفتند و مزایا و معایب هر یک بررسی شد. در این میان الگوریتمSQUISH-E ، قادر به برقراری تعادل بین نسبت فشرده‌سازی و خطای فاصله اقلیدسی همزمانی است در حالی که نرخ فشرده‌سازی بالایی نسبت به سایر روش‌ها دارد. به منظور رفع این مشکل، در این مقاله راهکاری برای متغیر کردن پنجره اولویت الگوریتم SQUISH-E ارائه شد که موجب بهبود نرخ فشرده‌سازی الگوریتم می‌شود. به منظور بررسی عملکرد روش یشنهادی، تمامی الگوریتم‌ها روی شش زیر مسیر با پیچیدگی‌های مختلف پیاده‌سازی شده و با یکدیگر از نظر معیارهایی مانند نرخ فشرده‌سازی، زمان اجرا و خطای فاصله اقلیدسی همزمانی مقایسه ‌شدند. نتایج به‌دست آمده حاکی از بهبود عملکرد الگوریتم پیشنهادی در نرخ فشرده‌سازی، زمان اجرایی و خطای فاصله اقلیدسی همزمانی می‌باشد. زمان الگوریتم پیشنهادی نسبت به الگوریتم SQUISH-E حدود 130 میلی‌ثانیه کاهش و نرخ فشرده‌سازی آن 015/0 افزایش یافته است.
واژه‌های کلیدی: خط سیر مکانی-زمانی، فشرده‌سازی، الگوریتم SQUISH-E، پنجره اولویت
متن کامل [PDF 1488 kb]   (111 دریافت)    
نوع مطالعه: پژوهشي | موضوع مقاله: سیستمهای اطلاعات مکانی (عمومی)
دریافت: ۱۳۹۷/۱۰/۴ | پذیرش: ۱۳۹۷/۱۰/۴ | انتشار: ۱۳۹۷/۱۰/۴
فهرست منابع
1. [1] J.-G. Lee, J. Han, and K.-Y. Whang, "Trajectory clustering: a partition-and-group framework," in Proceedings of the 2007 ACM SIGMOD international conference on Management of data, 2007, pp. 593-604. [DOI:10.1145/1247480.1247546]
2. [2] M. Chen, M. Xu, and P. Franti, "Compression of GPS trajectories," in 2012 Data Compression Conference, 2012, pp. 62-71.
3. [3] H. Wang, H. Su, K. Zheng, S. Sadiq, and X. Zhou, "An effectiveness study on trajectory similarity measures," in Proceedings of the Twenty-Fourth Australasian Database Conference-Volume 137, 2013, pp. 13-22.
4. [4] P. Sun, S. Xia, G. Yuan, and D. Li, "An Overview of Moving Object Trajectory Compression Algorithms," Mathematical Problems in Engineering, vol. 2016, 2016.
5. [5] W. Tobler, "Numerical Map Generalization, Michigan Inter-University Community of Mathematical Geographers," Discussion Paper1966.
6. [6] R. Bellman, "On the approximation of curves by line segments using dynamic programming," Communications of the ACM, vol. 4, p. 284, 1961. [DOI:10.1145/366573.366611]
7. [7] D. H. Douglas and T. K. Peucker, "Algorithms for the reduction of the number of points required to represent a digitized line or its caricature," Cartographica: The International Journal for Geographic Information and Geovisualization, vol. 10, pp. 112-122, 1973. [DOI:10.3138/FM57-6770-U75U-7727]
8. [8] N. Meratnia and R. De By, "A new perspective on trajectory compression techniques," in Proc. ISPRS Commission II and IV, WG II/5, II/6, IV/1 and IV/2 Joint Workshop Spatial, Temporal and Multi-Dimensional Data Modelling and Analysis, 2003.
9. [9] E. Keogh, S. Chu, D. Hart, and M. Pazzani, "An online algorithm for segmenting time series," in Data Mining, 2001. ICDM 2001, Proceedings IEEE International Conference on, 2001, pp. 289-296. [DOI:10.1109/ICDM.2001.989531]
10. [10] M. Potamias, K. Patroumpas, and T. Sellis, "Sampling trajectory streams with spatiotemporal criteria," in 18th International Conference on Scientific and Statistical Database Management (SSDBM'06), 2006, pp. 275-284. [DOI:10.1109/SSDBM.2006.45]
11. [11] J. Muckell, J.-H. Hwang, V. Patil, C. T. Lawson, F. Ping, and S. Ravi, "SQUISH: an online approach for GPS trajectory compression," in Proceedings of the 2nd International Conference on Computing for Geospatial Research & Applications, 2011, p. 13. [DOI:10.1145/1999320.1999333]
12. [12] J. Muckell, P. W. Olsen Jr, J.-H. Hwang, C. T. Lawson, and S. Ravi, "Compression of trajectory data: a comprehensive evaluation and new approach," GeoInformatica, vol. 18, pp. 435-460, 2014. [DOI:10.1007/s10707-013-0184-0]
13. [13] X. Wu and Z. Cao, "Basic conception, function and implementation of temporal GIS," Earth Science-Journal of China University of Geosciences, vol. 27, pp. 241-245, 2002.
14. [14] N. Meratnia and A. Rolf, "Spatiotemporal compression techniques for moving point objects," in International Conference on Extending Database Technology, 2004, pp. 765-782. [DOI:10.1007/978-3-540-24741-8_44]
15. [15] Y. Zheng and X. Zhou, Computing with spatial trajectories: Springer Science & Business Media, 2011. [DOI:10.1007/978-1-4614-1629-6]
16. [16] K. Deb, "Multi-objective optimization," in Search methodologies, ed: Springer, 2014, pp. 403-449. [DOI:10.1007/978-1-4614-6940-7_15]
ارسال پیام به نویسنده مسئول


XML   English Abstract   Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Nasiri A, Azimi S, Abbaspour R A. Data Reduction of Spatio-temporal Trajectories using a Modified Online Compression Algorithm. jgit. 2018; 6 (3) :23-38
URL: http://jgit.kntu.ac.ir/article-1-615-fa.html

نصیری افسانه، عظیمی ساناز، عباسپور رحیم علی. کاهش داده‌های خطوط سیر مکانی-زمانی با به‌کارگیری یک الگوریتم فشرده‌سازی برخط. مهندسی فناوری اطلاعات مکانی. 1397; 6 (3) :23-38

URL: http://jgit.kntu.ac.ir/article-1-615-fa.html



دوره 6، شماره 3 - ( 9-1397 ) برگشت به فهرست نسخه ها
نشریه علمی-پژوهشی مهندسی فناوری اطلاعات مکانی Engineering Journal of Geospatial Information Technology
Persian site map - English site map - Created in 0.05 seconds with 31 queries by YEKTAWEB 3858