Efficient identification and approximation of k-nearest moving neighbors

Georgios Skoumas, Dimitrios Skoutas, Alexandra Vlachaki
ACM SIGSPATIAL GIS 2013, November 5-8, 2013 Orlando, Florida, USA, 2013
Abstract. Nowadays, massive amounts of tracking data for various types of moving objects, including vehicles, humans and animals, are becoming available. Analyzing this type of spatio-temporal data is crucial for discovering movement patterns, understanding and forecasting behaviors, and developing novel applications and services. One problem of particular interest is finding objects that move close together with a certain object during some periods of time. In this paper, we focus on finding the k-nearest moving neighbors for a given query object and time interval. We formulate the problem, using a similarity function that takes into consideration both the proximity and the direction of the trajectories, and we firstly present an exact algorithm. Then, we focus on approximate algorithms in order to reduce the execution time, investigating two directions. The first employs line simplification to approximate the compared trajectories, thus reducing the calculations needed to identify the nearest neighbors. The second relies on estimates of prior probabilities derived from trajectory distributions and attempts to achieve a faster approximation of the k-nearest neighbors. A detailed experimental evaluation of the aforementioned algorithms on three real-world datasets is finally presented in order to verify their efficiency and accuracy.