Approximate Hotspots of Orthogonal Trajectories

• Autorzy: Rudi, Ali Gholami
• Języki publikacji: EN

Abstrakty

EN

We study the problem of finding hotspots, i.e. regions, in which a moving entity spends a significant amount of time, for polygonal trajectories. The fastest exact algorithm, due to Gudmundsson, van Kreveld, and Staals (2013) finds an axis-parallel square hotspot of fixed side length in O(n²) for a trajectory with n edges. Limiting ourselves to the case in which the entity moves in a direction parallel either to the x or to the y-axis, we present an approximation algorithm with the time complexity O(n log³ n) and approximation factor 1/2.

Słowa kluczowe

EN

trajectory hotspots; kinetic tournament; computational geometry

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 167, nr 4
• Strony: 271--285
• Opis fizyczny: Bibliogr. 13 poz., rys., tab., wykr.

Twórcy

autor

Rudi, Ali Gholami

• Department of Electrical and Computer Engineering, Bobol Noshirvani University of Technology, Babol, Iran,

Bibliografia

• [1] Zheng Y. Trajectory Data Mining - An Overview. ACM Transactions on Intelligent Systems and Technology, 2015. 6(3):29:1-29:41. doi:10.1145/2743025.
• [2] Benkert M, Djordjevic B, Gudmundsson J, Wolle T. Finding Popular Places. International Journal of Computational Geometry & Applications, 2010. 20(1):19-42. doi:10.1142/S0218195910003189.
• [3] Buchin M, Driemel A, van Kreveld MJ, Sacristán V. Segmenting Trajectories - A Framework and Algorithms Using Spatiotemporal Criteria. Journal of Spatial Information Science, 2011. 3(1):33-63. doi:10.5311/JOSIS.2011.3.66.
• [4] Aronov B, Driemel A, van Kreveld MJ, Löffler M, Staals F. Segmentation of Trajectories on Nonmonotone Criteria. ACM Transactions on Algorithms, 2016. 12(2):26:1-26:28. doi:10.1145/2660772.
• [5] Rudi AG. Looking for Bird Nests: Identifying Stay Points with Bounded Gaps. In: The Canadian Conference on Computational Geometry. 2018 pp. 334-339. URL http://www.cs.umanitoba.ca/~cccg2018/papers/session7A-p2.pdf.
• [6] Gudmundsson J, van Kreveld MJ, Staals F. Algorithms for Hotspot Computation on Trajectory Data. In: International Conference on Advances in Geographic Information Systems. 2013 pp. 134-143. doi:10.1145/2525314.2525359.
• [7] Alvares LO, Bogorny V, Kuijpers B, de Macêdo JAF, Moelans B, Vaisman AA. A Model for Enriching Trajectories with Semantic Geographical Information. In: ACM International Symposium on Geographic Information Systems. ACM, 2007 p. 22. doi:10.1145/1341012.1341041.
• [8] Tiwari S, Kaushik S. Mining Popular Places in a Geo-spatial Region Based on GPS Data Using Semantic Information. In: Workshop on Databases in Networked Information Systems. Springer, 2013 pp. 262-276. doi:10.1007/978-3-642-37134-9_20.
• [9] Basch J, Guibas LJ, Hershberger J. Data Structures for Mobile Data. Journal of Algorithms, 1999. 31(1):1-28. doi:10.1006/JAGM.1998.0988.
• [10] Miller HJ. Modelling Accessibility Using Space-Time Prism Concepts Within Geographical Information Systems. International Journal of Geographical Information Science, 1991. 5(3):287-301. doi:10.1080/02693799108927856.
• [11] Fenwick PM. A New Data Structure for Cumulative Probability Tables - An Improved Frequency-to-Symbol Algorithm. Software, Practice and Experience, 1996. 26(4):489-490. doi:10.1002/(SICI)1097-024X(199604)26:4¡489::AID-SPE22¿3.0.CO;2-S.
• [12] Agarwal PK, Kaplan H, Sharir M. Kinetic and Dynamic Data Structures for Closest Pair and All Nearest Neighbors. ACM Transactions on Algorithms, 2008. 5(1):4:1-4:37. doi:10.1145/1435375.1435379.
• [13] de Berg M, Cheong O, van Kreveld MJ, Overmars MH. Computational Geometry - Algorithms and Applications. Springer, third edition, 2008. doi:10.1007/978-3-540-77974-2.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).

Identyfikatory

DOI

10.3233/FI-2019-1818