Title: Finding the Most Accessible Locations - Reverse Path Nearest Neighbor Query in Road Networks

Speaker: Dr. Shuo Shang, Aalborg University, Denmark

Time: 2:00 PM, Thursday, 20th June, 2013

Venue: Meeting room, 11rd Floor, Building #5, Institute of Software, Chinese Academy of Sciences

Abstract:

In this paper, we propose and investigate a novel spatial query called Reverse Path Nearest Neighbor (R-PNN) search to find the most accessible locations in road networks. Given a trajectory data-set and a list of location candidates specified by users, if a location o is the Path Nearest Neighbor (PNN) of k trajectories, the influence-factor of o is defined as k and the R-PNN query returns the location with the highest influence-factor. The R-PNN query is an extension of the conventional Reverse Nearest Neighbor (RNN) search. It can be found in many important applications such as urban planning, facility allocation, traffic monitoring, etc. To answer the R-PNN query efficiently, an effective trajectory data pre-processing technique is conducted in the first place. We cluster the trajectories into several groups according to their distribution. Based on the grouped trajectory data, a two-phase solution is applied. First, we specify a tight search range over the trajectory and location data-sets. The efficiency study reveals that our approach defines the minimum search area. Second, a series of optimization techniques are adopted to search the exact PNN for trajectories in the candidate set. By combining the PNN query results, we can retrieve the most accessible locations. The complexity analysis shows that our solution is optimal in terms of time cost. The performance of the proposed R-PNN query processing is verified by extensive experiments based on real and synthetic trajectory data in road networks.

Biography:

Dr. Shuo Shang is currently a Research Assistant Professor level Research Fellow (his duty is equivalent to research assistant professor, including teaching and supervising research students) with Department of Computer Science, Aalborg University. He is also a faculty member of the Center for Data-intensive Systems (Daisy), which conducts research and offers education with a focus on data management for various data-intensive systems. He obtained his B.Sc. from Peking University in 2008, and Ph.D. from The University of Queensland in 2012 respectively, both in Computer Science. His research interests include Efficient Query Processing in Spatial-Temporal Databases, Trajectory Search and Mining, Uncertain Data Management, Personalized Recommendation, Location Based Services, and Location Based Social Networks. At present, he is working on BagTrack project (track of baggage, a project dedicated to improving bag handling in aviation industry globally) with Prof. Torben Bach Pederson; and Personalized Trajectory Recommendation with Prof. Chiristian S. Jensen. He is also working closely with Prof. Xiaofang Zhou.