Efficient Processing of Moving Keyword Queries on Tagged Spatial Databases


In this talk, we study the efficient processing of moving keyword queries on tagged spatial databases. Objects (e.g., restaurants, museums) are increasingly being tagged by their owners on their provided features or by visitors on their comments. While moving in a city, a mobile user wishes to be continuously aware of nearby objects that best match his query keywords. This motivates the importance of the moving keyword search, whose parameters includes the user's moving query location and query keywords.

Moving keyword queries are important for many mobile applications. For instance, a mobile user wishes to be continuously aware of the objects-of-interests (e.g., ATMs, gas stations) that best match his location and query keywords. While walking along a street, a visitor wants to be kept informed of nearby scenes and cultural heritage that match his interests.

Several challenges arise from moving keyword search. First, it is impractical to search/update the result periodically (e.g., every second) because it either yields excessive cost or outdated result. Indeed, even with a small time period, correct near-future result is not guaranteed. Second, it is not possible to pre-compute the result in advance because the user's future movement may not be known. Third, the relevancy of an object depends both its location and keyword relevancy to a user, which can vary across different users.

Our goal is to develop efficient techniques for processing continuously moving keyword queries over tagged spatial databases. Our approach adopts the client-server architecture and the server computes a keyword-aware safe zone that guarantees the reported result to remain the best match of the moving keyword query as long as the client is inside the safe zone. This reduces the communication frequency between the server and the client. Only upon leaving the safe zone, the client sends a location update to the server which then computes the updated result and the safe zone accordingly.

We are the first to study the keyword-aware safe zone and its computation techniques. Preliminary techniques are developed for optimizing the communication cost between the server and the client, and the computation time of the safe zone. Some experimental results on real tagged spatial data will be presented.


Dr. Man Lung Yiu
Department of Computing
The Hong Kong Polytechnic University

Date & Time

07 Jan 2011 (Friday) 11:30



Organized by

Department of Computer and Information Science


Dr. Man Lung Yiu received the bachelors degree in computer engineering and the PhD degree in computer science from the University of Hong Kong in 2002 and 2006, respectively. Prior to his current post, he worked at Aalborg University for three years starting in the Fall of 2006. He is now an assistant professor in the Department of Computing, Hong Kong Polytechnic University. His research focuses on the management of complex data, in particular query processing topics on spatiotemporal data and multidimensional data.