CIS Colloquium, Feb 06, 2008, 03:00PM – 04:00PM, Wachman 447
Location Constraint Processing for Proximity Detection
Zhengdao Xu, University of Toronto
An important problem for many location-based applications is the continuous evaluation of proximity relations among moving objects. A proximity relation measures whether a set of moving objects is close to each other, for example, the relation determines whether two friends are within the range of 100 meters. We represent proximity relations as location constraints, which resemble standing queries over continuously changing location position information. The challenge lies in the continuous processing of large numbers of location constraints as the locations of objects and the constraint load change. Also the accuracy of establishing such proximity relations is severely impeded by the imprecision of dynamically obtained position data. We propose an adaptive partition-based approach for efficient constraint evaluation in the Euclidean space and the road network space. Empirical results based on a real data sets show that our approaches dramatically reduce the constraint processing overhead and are ten times faster than a baseline algorithm.
Zhengdao Xu is currently a Ph.D. Candidate in the Department of Computer Science at the University of Toronto. He received his B.S. degree in Computer Science from the Zhejiang University and his M.S. degree in Computer Science from the University of Ottawa. Zhengdao’s current research interest lies in spatio-temporal data management, mobile computing, and distributed systems. In the past, he also worked on routing protocols for telecommunication systems collaborating with Bell and Alcatel for five years.