Abstract:
The large and steadily increasing availability of multidimensional data in various forms (e.g., satellite images, digital video, multimedia documents) has rendered spatial information processing as one of the most active research areas in the database community. Traditional methods used in relational databases are not directly applicable for spatial queries due to the fact that there is no total ordering of objects in space that preserves spatial proximity. As a result, a number of spatial access methods (SAMs) have been proposed to perform several spatial operations.

In this talk we present the R-tree, the most popular SAM, and its application for several forms of spatial queries, including spatial selections, joins and nearest neighbors. Next we propose extensions of these queries for moving objects. In particular, we develop the subsequence retrieval (SR) query, which identifies when the next change in the result will happen. Any type of moving object query (e.g., selections, nearest neighbors) can be reduced to an SR query and processed by branch-and-bound algorithms that take advantage of the R-tree structure to prune the search space.

Biography:
Dimitris Papadias is an assistant professor at the department of Computer Science, HKUST. Before joining HKUST, he held positions at the Institute for Intelligent Robotics and Information Systems (Canada), the National Technical University of Athens (Greece), the Technical University of Vienna (Austria), the University of California at San Diego, the National Center for Geographic Information and Analysis (USA), and the German National Research Center for Information Technology (GMD). His research interests include (spatial, spatio-temporal) databases, OLAP, and search algorithms. He has published more than 60 articles on these topics in prestigious venues (including ACM TODS, TOIS, TKDE, Algorithmica, SIGMOD, VLDB, SIGIR, ICDE etc) and has participated in the program committees of all major database conferences.

Mr. Yufei Tao obtained his Bachelor's degree from the Department of Computer Science and Engineering, South China University of Technology (SCUT), Guangzhou, China in 1999. He is currently a PhD student at the Department of Computer Science, Hong Kong University of Science and Technology supervised by Dr. Dimitris Papadias. His research interests include indexing techniques, query optimization, aggregate reasoning in temporal, spatial, and spatio-temporal databases.