La Trobe
37827_SOURCE01_3_A.pdf (954.55 kB)

Answering spatial queries on moving objects with reduced communication

Download (954.55 kB)
posted on 2023-01-18, 15:41 authored by Mitzi McCarthy
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.


Center or Department

Faculty of Science, Technology and Engineering. School of Engineering and Mathematical Sciences.

Thesis type

  • Ph. D.

Awarding institution

La Trobe University

Year Awarded


Rights Statement

The thesis author retains all proprietary rights (such as copyright and patent rights) over the content of this thesis, and has granted La Trobe University permission to reproduce and communicate this version of the thesis. The author has declared that any third party copyright material contained within the thesis made available here is reproduced and communicated with permission. If you believe that any material has been made available without permission of the copyright owner please contact us with the details.

Data source

arrow migration 2023-01-10 00:15. Ref: latrobe:37827 (9e0739)

Usage metrics

    Open Theses


    No categories selected



    Ref. manager