Answering spatial queries on moving objects with reduced communication

Submission note: A thesis submitted in total fulfilment of the requirements for the degree of Doctor of Philosophy to the School of Engineering and Mathematical Sciences, Faculty of Science, Technology and Engineering, La Trobe University, Bundoora.

Existing studies on answering spatial queries on moving objects fall into two main categories: those focused on reducing the computation time; and/or those focused on reducing the communication costs. This thesis is focused on reducing communication costs while reducing computation time to acceptable levels. One subgroup of work on reducing communication costs uses safe regions. Communication cost is reduced by not requiring the moving objects to report their locations while they stay within their rectangular safe regions, unless explicitly requested by the server. We extend the existing studies that use safe regions for answering continuous spatial queries on moving objects in three ways. First, we allow queries to move instead of being stationary. Second, we handle queries of different degrees of continuity to cover the entire spectrum between snapshot and continuous queries. Finally, we extend the traditional range and k-nearest neighbor queries to make them more useful. We extend the traditional range query to allow an aggregation predicate to be applied to the returned objects. We exploit this property to reduce the communication costs. We propose a probabilistic k nearest neighbor query that effectively trades-off communication costs against query result accuracy. We propose a system that has two main components. The first is the query evaluation component, which answers queries based on the current set of safe regions. The second is the safe region assignment component. The main challenge during query evaluation is to answer the current set of queries using the least number of object location exposures. We devise both information gain and fast heuristic approaches to solve this problem. We propose a reactive approach to safe region assignment, which assigns larger safe regions to objects that move more and are queried less often. Experimental results show that our approach greatly reduces the communication costs when compared to existing solutions and naive solutions.