1 Department of Computer Science, The Faculty of Engineering and Science, Aalborg University, VBN2 The Faculty of Engineering and Science, Aalborg University, VBN3 Database and Programming Technologies, The Faculty of Engineering and Science, Aalborg University, VBN4 University of Queensland5 Microsoft Research Asia6 Carnegie Mellon University7 University of Queensland8 Microsoft Research Asia9 Carnegie Mellon University
The advances in location positioning and wireless communication technologies have led to a myriad of spatial trajectories representing the mobility of a variety of moving objects. While processing trajectory data with the focus of spatio-temporal features has been widely studied in the last decade, recent proliferation in location-based web applications (e.g., Foursquare, Facebook) has given rise to large amounts of trajectories associated with activity information, called activity trajectory. In this paper, we study the problem of efficient similarity search on activity trajectory database. Given a sequence of query locations, each associated with a set of desired activities, an activity trajectory similarity query (ATSQ) returns k trajectories that cover the query activities and yield the shortest minimum match distance. An order-sensitive activity trajectory similarity query (OATSQ) is also proposed to take into account the order of the query locations. To process the queries efficiently, we firstly develop a novel hybrid grid index, GAT, to organize the trajectory segments and activities hierarchically, which enables us to prune the search space by location proximity and activity containment simultaneously. In addition, we propose algorithms for efficient computation of the minimum match distance and minimum order-sensitive match distance, respectively. The results of our extensive empirical studies based on real online check-in datasets demonstrate that our proposed index and methods are capable of achieving superior performance and good scalability.
Data Engineering: Icde, 2013, p. 230-241
Main Research Area:
International Conference on Data Engineering. Proceedings
29th IEEE International Conference on Data EngineeringIEEE International Conference on Data Engineering, 2013