Robust and Fast Similarity Search for Moving Object Trajectories
Lei Chen, M. Tamer Özsu, Vincent Oria
Original Abstract: An important consideration in similarity-based retrieval of moving object trajectories is the definition of a distance function. The existing distance functions are usually sensitive to noise, shifts and scaling of data that commonly occur due to sensor failures, errors in detection techniques, disturbance signals, and different sampling rates. Cleaning data to eliminate these is not always possible. In this paper, we introduce a novel distance function, Edit Distance on Real sequence (EDR) which is robust against these data imperfections. Analysis and comparison of EDR with other popular distance functions, such as Euclidean distance, Dynamic Time Warping (DTW), Edit distance with Real Penalty (ERP), and Longest Common Subsequences (LCSS), indicate that EDR is more robust than Euclidean distance, DTW and ERP, and it is on average 50% more accurate than LCSS. We also develop three pruning techniques to improve the retrieval efficiency of EDR and show that these techniques can be combined effectively in a search, increasing the pruning power significantly. The experimental results confirm the superior efficiency of the combined methods.
 | Lei Chen received the BS degree in computer science and engineering from Tianjin University, Tianjin, China, in 1994, the MA degree from Asian Institute of Technology, Bangkok, Thailand, in 1997, and the PhD degree in computer science from the University of Waterloo, Canada, in 2005. He is currently an associate professor in the Department of Computer Science and Engineering, Hong Kong University of Science and Technology. His research interests include crowdsourcing, probabilistic and uncertain databases, trajectory data analysis and privacy-preserved data publishing. The spatial crowdsourcing system, Gmission, developed by his team won the excellent demonstration award in VLDB 2014. He also got the best paper awards in DASFAA 2009 and 2010. Currently, he serves as associate editor-in-chief for IEEE Transaction on Data and Knowledge Engineering and a Trustee Board Member of VLDB Endowment. |
 | M. Tamer Özsu is Professor of Computer Science at the University of Waterloo. His current research focuses on large scale data distribution and management of unconventional data (e.g., graphs, RDF, XML, streams). He is a Fellow of ACM and IEEE, an elected member of the Science Academy (Turkey), and a member of Sigma Xi and AAAS. He was awarded the ACM SIGMOD Contributions Award in 2008 and the Ohio State University College of Engineering Distinguished Alumnus Award in 2008. |
| Vincent Oria is an associate professor of computer science at the New Jersey Institute of Technology (NJIT) in the USA. His research interests include multimedia databases, spatio-temporal databases, and similarity search in high-dimensional spaces. He has held visiting professor positions at various institutions including National Institute of Informatics (Tokyo, Japan), Telecom-ParisTech (Paris, France), Université de Paris- Dauphine (Paris, France), INRIA (Roquencourt, France), Conservatoire National des Arts et Métiers (Paris, France), Chinese University of Hong Kong (Hong Kong, China) and Hubei University of Science and Art (Xiang Yang, China). He is the recipient of the 2014 Outstanding Achievement in Research Award for the NJIT College of Computing Sciences. |