[صفحه اصلی ]   [Archive] [ English ]  
:: صفحه اصلي :: درباره نشريه :: آخرين شماره :: تمام شماره‌ها :: جستجو :: ثبت نام :: ارسال مقاله :: تماس با ما ::
:: دوره 5، شماره 2 - ( 6-1396 ) ::
جلد 5 شماره 2 صفحات 141-162 برگشت به فهرست نسخه ها
شاخص‌گذاری موقعیت جاری و گذشته اشیاء متحرک درمجموعه داده‌های بزرگ مقیاس
محمدرضا عباسی فرد، حسن نادری*
دانشگاه علم و صنعت ایران
چکیده:   (1836 مشاهده)
با افزایش روز افزون سیستم‌های هوشمند حمل و نقل و سرویس‌های مبتنی برمکان که از داده‌های مکانی-زمانی بهره می‌برند، نیاز به تکنیک‌ها شاخص‌گذاری جدید برای این دادهها افزایش یافته است. این دادهها مربوط به زمان گذشته، حال یا آینده اشیاء متحرک هستند که شاخص‌های موجود عموماً امکان شاخصگذاری یکی از این سه زمان را دارند. داشتن شاخصی یکپارچه برای شاخص‌گذاری همزمان انواع دادهها و همچنین پاسخگویی به انواع پرس‌وجوها، یکی از چالش‌های این نوع داده‌ها می‌باشد که امکان کاهش فاصله زمانی بروزرسانی شاخص‌ها را داشته باشد. در این مقاله روشی یکپارچه با نام PCPI ارائه شده است که علاوه بر امکان ساخت و نگهداری شاخص‌های‌ داده‌های مکانی-زمانی در زمان گذشته و حال، به صورت همزمان به ترتیب در دیسک و حافظه اصلی، توانایی پاسخ به انواع پرس‌وجو‌های مکانی-زمانی را دارد. با استفاده از این تکنیک، از یک مجموعه منبع مشترک برای پردازش و ساخت شاخص‌ها در دو زمان مختلف استفاده شده و اختلاف فاز زمانی بین دو شاخص را کاهش داده است. در این روش از دو داده ساختار به صورت یکپارچه استفاده شده است. یک داده ساختار در حافظه اصلی برای شاخص‌گذاری و نگهداری موقعیت جاری اشیاء متحرک، و داده ساختار دوم برروی دیسک برای داده‌های خط‌سیر اشیاء متحرک که دارای حجم بالایی بوده و امکان نگهداری در حافظه اصلی را ندارند. علاوه بر این، در PCPI از روش‌های تطبیق برنقشه برای حذف اختلالات موجود در داده‌های دریافتی از اشیاء متحرک مانند اختلال حالت ساکن استفاده شده است که باعث افزایش دقت پرس‌وجوها می‌شود. همچنین تاثیر روش‌های کاهش داده بر افزایش سرعت شاخص‌گذاری، پردازش پرس‌وجو و کاهش اندازه شاخصها در دیسک در مجموعه داده‌های بزرگ، در آزمایش‌ها موردبررسی قرار گرفت. نتایج و مقایسه‌‌های انجام شده در آزمایش‌های تجربی، نشان از کارایی بالای این ساختار شاخص‌گذاری دارد.
واژه‌های کلیدی: پایگاه داده اشیاء متحرک، شاخص‌گذاری خط سیر، داده های مکانی-زمانی، پردازش پرس‌وجو
متن کامل [PDF 1301 kb]   (668 دریافت)    
نوع مطالعه: پژوهشي | موضوع مقاله: سیستمهای اطلاعات مکانی (عمومی)
دریافت: 1396/7/16 | پذیرش: 1396/7/16 | انتشار: 1396/7/16
فهرست منابع
1. [1] C.-I. Cha, S.-W. Kim, J.-I. Won, J. Lee, and D.-H. Bae, "Efficient Indexing in Trajectory Databases.," International Journal of Database Theory and Application, vol. 1, pp. 21–28, 2008.
2. [2] C. Lv, Y. Xu, J. Song, and P. Lv, "A data frame based spatiotemporal indexing algorithm for moving objects," presented at the 12th World Congress on Intelligent Control and Automation (WCICA), Guilin, China, 2016. [DOI:10.1109/WCICA.2016.7578643]
3. [3] Y. Shi, J. Feng, Z. Ren, and W. Xie, "Hadoop-based Probabilistic Range Queries of Moving Objects on Road Network," 2016.
4. [4] Y. Zheng and X. Zhou. (2011). Computing with Spatial Trajectories [Online].
5. [5] C. Parent, S. Spaccapietra, C. Renso, G. Andrienko, N. Andrienko, V. Bogorny, et al., "Semantic trajectories modeling and analysis," ACM Computing Surveys (CSUR), vol. 45, pp. 1-32, 2013. [DOI:10.1145/2501654.2501656]
6. [6] C. Renso, S. Spaccapietra, and E. Zimányi, Mobility data: modeling management and understanding: Cambridge University Press, 2013. [DOI:10.1017/CBO9781139128926]
7. [7] V. P. Chakka , A. C. Everspaugh, and J. M. Patel, "Indexing Large Trajectory Data SetsWith SETI," in CIDR 2003.
8. [8] Y. Fang , J. Cao, Y. Peng, N. Chen, and L. Liu, "Indexing the Past, Present and Future Positions of Moving Objects on Fixed Networks," presented at the International Conference on Computer Science and Software Engineering, Wuhan, Hubei, 2008. [DOI:10.1109/CSSE.2008.1449]
9. [9] M. Pelanis, S. Šaltenis, and C. S. Jensen, "Indexing the past, present, and anticipated future positions of moving objects," ACM Transactions on Database Systems (TODS), vol. 31, pp. 255-298 March 2006. [DOI:10.1145/1132863.1132870]
10. [10] D. Lin, C. S. Jensen, B. C. Ooi, and S. Šaltenis, "Efficient indexing of the historical, present, and future positions of moving objects," in Proceedings of the 6th international conference on Mobile data management, ACM, New York, NY, USA, 2005, pp. 59-66. [DOI:10.1145/1071246.1071256]
11. [11] K.-S. Kim, S.-W. Kim, T.-W. Kim, and K.-J. Li, "Fast indexing and updating method for moving objects on road networks," in Proceedings of the Fourth international conference on Web information systems engineering workshops(WISEW'03), Rome, Italy, 2003, pp. 34-42.
12. [12] M. Hashemi and H. A. Karimi, "A weight-based map-matching algorithm for vehicle navigation in complex urban networks," Journal of Intelligent Transportation Systems, pp. 1-18, 17 March 2016. [DOI:10.1080/15472450.2016.1166058]
13. [13] M. Bierlaire, J. Chen, and J. Newman, "A probabilistic map matching method for smartphone GPS data," Transportation Research Part C: Emerging Technologies, vol. 26, pp. 78-98, January 2013. [DOI:10.1016/j.trc.2012.08.001]
14. [14] P. Newson and J. Krumm, "Hidden Markov map matching through noise and sparseness," in 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Seattle, Washington, 2009, pp. 336-343. [DOI:10.1145/1653771.1653818]
15. [15] I. S. Popa, K. Zeitouni, V. Oria, and A. Kharrat, "Spatio-temporal compression of trajectories in road networks," GeoInformatica, vol. 19, pp. 117-145, January 2015. [DOI:10.1007/s10707-014-0208-4]
16. [16] R. Song, W. Sun, B. Zheng, and Y. Zheng, "PRESS: A Novel Framework of Trajectory Compression in Road Networks," Proceedings of the VLDB Endowment, vol. 7, pp. 661-672, May 2014 2014. [DOI:10.14778/2732939.2732940]
17. [17] G. Kellaris, N. Pelekis, and Y. Theodoridis, "Map-matched trajectory compression," Journal of Systems and Software, vol. 86, pp. 1566-1579, June 2013. [DOI:10.1016/j.jss.2013.01.071]
18. [18] M. F. Mokbel, T. M. Ghanem, and W. G. Aref, "Spatio-Temporal Access Methods," IEEE Data Engineering Bulletin, vol. 26, pp. 40-49, 2003.
19. [19] L.-V. Nguyen-Dinh, W. G. Aref, and M. F. Mokbel, "Spatio-Temporal Access Methods: Part 2 (2003 - 2010)," IEEE Data Engineering Bulletin, vol. 33, pp. 46-55 2010.
20. [20] Y. Manolopoulos, A. Nanopoulos, A. N. Papadopoulos, and Y. Theodoridis. (2005, November 21). R-Trees: Theory and Applications (2006 ed.) [Online].
21. [21] Y. Tao and D. Papadias, "MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries," in Proceedings of the 27th International Conference on Very Large Data Bases (VLDB '01), Roma, Italy, 2001, pp. 431-440.
22. [22] M. A. Nascimento, J. R. O. Silva, and Y. Theodoridis, "Evaluation of Access Structures for Discretely Moving Points," in Proceedings of the International Workshop on Spatio-Temporal Database Management (STDBM'99), 1999, pp. 171-188. [DOI:10.1007/3-540-48344-6_10]
23. [23] D. Pfoser, C. S. Jensen, and Y. Theodoridis, "Novel Approaches to the Indexing of Moving Object Trajectories," in Proceedings of the 26th International Conference on Very Large Data Bases (VLDB '00), Cairo, Egypt, 2000, pp. 395-406.
24. [24] C.-I. Cha, S.-W. Kim, J.-I. Won, J. Lee, and D.-H. Bae, "Efficient Indexing in Trajectory Databases," International Journal of Database Theory and Application, vol. 1, pp. 21-28, 2008.
25. [25] X. Xiong, M. F. Mokbel, and W. G. Aref, "LUGrid: Update-tolerant Grid-based Indexing for Moving Objects," in the 7th International Conference on Mobile Data Management (MDM '06), Nara, Japan, 2006, p. 13.
26. [26] Y. N. Silva, X. Xiong, and W. G. Aref, "The RUM-tree: supporting frequent updates in R-trees using memos," The VLDB Journal — The International Journal on Very Large Data Bases, vol. 18, pp. 719-738 June 2009 2009.
27. [27] Z. Song and N. Roussopoulos, "SEB-tree: An Approach to Index Continuously Moving Objects," in MDM '03 Proceedings of the 4th International Conference on Mobile Data Management, Melbourne, Australia, 2003, pp. 340-344. [DOI:10.1007/3-540-36389-0_25]
28. [28] Y. Tao, D. Papadias, and J. Sun, "The TPR*-Tree: An Optimized Spatio-temporal Access Method for Predictive Queries," in VLDB '03 Proceedings of the 29th international conference on Very large data bases, 2003, pp. 790-801. [DOI:10.1016/B978-012722442-8/50075-6]
29. [29] Z.-H. Liu, X.-L. Liu, J.-W. Ge, and H.-Y. Bae, "Indexing Large Moving Objects from Past to Future with PCFI+-Index," in Proceedings of the Eleventh International Conference on Management of Data(COMAD 2005), Goa, India, 2005, pp. 131–137.
30. [30] H. Ferhatosmanoğlu, D. Agrawal, Ö. Eğecioğlu, and A. El Abbadi, "Optimal Data-Space Partitioning of Spatial Data for Parallel I/O," Distributed and Parallel Databases vol. 17, pp. 75-101, January 2005. [DOI:10.1023/B:DAPD.0000045550.56749.75]
31. [31] M. R. Abbasifard, H. Naderi, Z. Fallahnejad, and O. Isfahani Alamdari, "Approximate aggregate nearest neighbor search on moving objects trajectories," Journal of Central South University, vol. 22, pp. 4246–4253, 08 November 2015 2015.
32. [32] R. Sedgewick and K. Wayne, Algorithms, 4 ed.: Pearson Education, 2011.
33. [33] H. Cao, O. Wolfson, and G. Trajcevski, "Spatio-temporal data reduction with deterministic error bounds," The VLDB Journal—The International Journal on Very Large Data Bases, vol. 15, pp. 211-228 September 2006.
34. [34] Z. Song and N. Roussopoulos, "SEB-tree: An Approach to Index Continuously Moving Objects," presented at the Proceedings of the 4th International Conference on Mobile Data Management, 2003. [DOI:10.1007/3-540-36389-0_25]
35. [35] M. R. Abbasifard, B. Ghahremani, and H. Naderi, "A Survey on Nearest Neighbor Search Methods," International Journal of Computer Applications, vol. 95, pp. 39-52, June 2014 2014.
36. [36] N. Bhatia and V. Ashev, "Survey of Nearest Neighbor Techniques," International Journal of Computer Science and Information Security, vol. 8, pp. 1-4, 2010.
37. [37] S. Dhanabal and S. Chandramathi, "A Review of various k-Nearest Neighbor Query Processing Techniques," Computer Applications, vol. 31, pp. 14-22, 2011.
ارسال پیام به نویسنده مسئول



XML   English Abstract   Print


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

Abbasifard M R, naderi H. Indexing the past and current position of moving objects in large-scale dataset . jgit. 2017; 5 (2) :141-162
URL: http://jgit.kntu.ac.ir/article-1-473-fa.html

عباسی فرد محمدرضا، نادری حسن. شاخص‌گذاری موقعیت جاری و گذشته اشیاء متحرک درمجموعه داده‌های بزرگ مقیاس. مهندسی فناوری اطلاعات مکانی. 1396; 5 (2) :141-162

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



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