Identifying and Querying Regularly Visited Places

Scientific Annals of Computer Science

article

A. G. Rudi¹ 

[1] Department of Electrical and Computer Engineering, Babol Noshirvani University of Technology

关键词: Trajectory analysis;    stay points;    regular visits;    geometric algorithm.;   

DOI  :  10.7561/SACS.2019.2.185

来源: Alexandru Ioan Cuza University of Iasi

【 摘 要 】

A stay point of a moving entity is a region in which it spends a significant amount of time. In this paper, we identify all stay points of an entity in a certain time interval, where the entity is allowed to leave the region but it should return within a given time limit. This definition of stay points seems more natural in many applications of trajectory analysis than those that do not limit the time of entity’s absence from the region. We present an O(n log n) algorithm for trajectories in R1 with n vertices and a (1 + ε)-approximation algorithm for trajectories in R2 to identify all such stay points. Our algorithm runs in O(kn2), where k depends on ε and the ratio of the duration of the trajectory to the allowed gap time. We also present an algorithm to answer stay point queries in logarithmic time, after an O(kn log n) time preprocessing.

【 授权许可】

CC BY-ND