:: دوره 3، شماره 4 - ( 12-1394 ) ::
جلد 3 شماره 4 صفحات 95-83 برگشت به فهرست نسخه ها
الگوریتمی برای فشرده‌سازی خطوط سیر مکانی با حفظ ماهیت معنایی
سمیه عاقل شاه‌نشین، سیمین سادات میروهابی، رحیم علی عباسپور*
دانشگاه تهران
چکیده:   (2912 مشاهده)

یک راه معمول برای ذخیره اطلاعات مکانی-زمانی اشیاء در حال حرکت، نمایش مسیر حرکت شئ متحرک به شکل خط سیر سه‌بعدی (موقعیت جغرافیایی نقاط به همراه زمان) است. در سال‌های اخیر تحقیقات گسترده‌ای در حوزه خط سیر انجام شده است. با این حال، در این مطالعات، ایده خط سیر معنایی یک مفهوم نسبتاً جدید است که با هدف انجام آنالیزهای معنایی مؤثر روی داده‌ها انجام می‌شود. در خط سیر معنایی که یک نمایش ثانویه از خط سیر مکانی است، حرکت شئ به شکل دنباله‌ای از توقف‌ها و حرکت‌ها توصیف می‌شود. تولید خط سیر معنایی از داده‌های خام جمع‌آوری شده، یک فرآیند با چندین گام پردازش است که با توجه به حجم عظیم داده‌ها، یکی از پیش‌پردازش‌های موردنیاز کاهش تعداد نقاط خط سیر با حفظ دقت موردنیاز با استفاده از تکینک‌های فشرده‌سازی است. با وجود این، اغلب تکنیک‌های کاهش داده خط سیر که بر اساس ساده‌سازی خطی هستند، قادر به حفظ مناطق توقف و حرکت نیستند. در این مقاله روشی برای فشرده‌سازی داده‌های خط سیر بر اساس سرعت نقاط ارائه شده است که از ترکیب دو تابع فاصله در درونیابی و محاسبه خطای نقاط استفاده کرده است. تابع فاصله اول بر اساس سرعت نقاط است که برای محاسبه خطای تقریب خط سیر استفاده شده و تابع فاصله دوم تابعی بر اساس توسعه الگوریتم شناخته شده داگلاس-پوکر است که از فرض ثابت بودن شتاب در محاسبه خطا در تقریب استفاده کرده است. الگوریتم ارائه شده روی داده‌های واقعی خط سیر پیاده‌سازی شده و نتایج به دست آمده حاکی از بهبود عمکرد در حفظ مناطق توقف در مقایسه با الگوریتم‌های فشرده‌سازی دیگر است.

واژه‌های کلیدی: خط سیر معنایی، فشرده‌سازی، مدل توقف-حرکت، Ev-E2
متن کامل [PDF 856 kb]   (929 دریافت)    
نوع مطالعه: پژوهشي |
دریافت: 1395/4/13 | پذیرش: 1395/4/13 | انتشار: 1395/4/13
فهرست منابع
1. [1] Alvares, L. O., Oliveira, G., Heuser, C. A., and Bogorny, V., "A Framework for Trajectory Data Preprocessing for Data Mining," in Conf. on Software Engineering and Knowledge Engineering, 2009.
2. [2] Pelekis, N., Theodoridis, Y., Janssens, D., "On the Management and Analysis of Our LifeSteps," ACM SIGKDD Explorations Newsletter, vol. 15, no. 1, pp. 23-32, 2013. [DOI:10.1145/2594473.2594478]
3. [3] Zheng, Y., Zhou, X., Computing with Spatial Trajectories, New York: Springer-Verlag New York, 2011. [DOI:10.1007/978-1-4614-1629-6]
4. [4] Douglas, D., Peucker, T., "Algorithms for the Reduction of the Number of Points Required to Represent a Line or its Caricature," Cartographica, vol. 10, no. 2, pp. 112-122, 1973. [DOI:10.3138/FM57-6770-U75U-7727]
5. [5] Maratnia, N., de By, R., "patio-Temporal Compression Techniques for Moving Point Objects," in International Conference on Extending Database Technology (EDBT), 2004.
6. [6] R. Bellman, "On the Approximation of Curves by Line Segments Using Dynamic Programming," Communications of the ACM, vol. 4, no. 6, 1961. [DOI:10.1145/366573.366611]
7. [7] J. Vitter, "Random sampling with a reservoir," ACM Transactions on Mathematical Software(TOMS), vol. 11, no. 1, 1985. [DOI:10.1145/3147.3165]
8. [8] Keogh, E., Chu, S., Hart, D., Pazzani, M., "An On-Line Algorithm for Segmenting Time Series," in International Conference on Data Mining (ICDM), 2001.
9. [9] Potamias, M., Patroumpas, K., Sellis, T., "ampling Trajectory Streams with Spatio-Temporal Criteria," in In: International Conference on Scientific and Statistical Database Management (SSDBM), 2006.
10. [10] K. Patroumpas, "Online tracking and summarization over streaming maritime trajectories," in Workshop on Moving Objects at Sea, 2013.
11. [11] W. Ting, "SOMETIMES TOO BIG: COMPRESSING TRAJECTORY DATA," in PACIS 2014 Proceedings, 2014.
12. [12] de Vries, G. K. D. and, Someren, M., "Machine learning for vessel trajectories using compression, alignments and domain knowledge," ELSEVIER, vol. 39, no. 18, p. 13426–13439, 2012.
13. [13] Cao, H., Wolfson, O. and Trajcevski, G., "Spatio-temporal data reduction with deterministic error bounds," The VLDB Journal — The International Journal on Very Large Data Bases, vol. 15, no. 3, pp. 211-228, 2006.
14. [14] Zheng, Y., Zhang, L., Xie, X., & Ma, W. Y., "Mining interesting locations and travel sequences from GPS trajectories," in In Proceedings of the 18th international conference on World wide, Madrid Spain, 2009. [DOI:10.1145/1526709.1526816]
15. [15] Zheng, Y., Li, Q., Chen, Y., Xie, X., & Ma, W. Y., "Understanding mobility based on GPS data," in In Proceedings of the 10th international conference on Ubiquitous computing, Seoul, Korea, 2008. [DOI:10.1145/1409635.1409677]
16. [16] Zheng, Y., Xie, X., & Ma, W. Y., "GeoLife: A Collaborative Social Networking Service among User, location and trajectory," in IEEE Data Engineering Bulletin, 2010.



XML   English Abstract   Print



بازنشر اطلاعات
Creative Commons License این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است.
دوره 3، شماره 4 - ( 12-1394 ) برگشت به فهرست نسخه ها