AbstractsComputer Science

Moving range query processing in spatial databases

by Haidar AL-Khalidi




Institution: Monash University
Department: Computer Science
Year: 2014
Keywords: Moving range query; Approximate range query; lookforward moving range; Safe region; Approximate moving range query; Monitoring moving range query; Approximate Moving Range Query; Static range query; Continuous range query
Record ID: 1048727
Full text PDF: http://arrow.monash.edu.au/hdl/1959.1/1133660


Abstract

Recent developments in mobile communications have brought dramatic and fundamental changes to the modern world. These developments have resulted in a great demand for applications that integrate geographic locations and services to fulfill the user’s needs. Different types of spatial queries are used in such applications, however, most studies consider the moving range query to be the most common, and frequently used. The moving range query is used to find all objects of interest within a given radius while the user who invokes the query is moving. During the last decade, some studies in moving range queries considered Euclidean geometry, where the distance between two objects is determined by their relative position in space. Some other studies considered network distance, wherein the trajectory between two objects is specified by the underlying network. The main objective of all the previous studies is to process moving range queries efficiently. However, most of these studies focus on index efficiency and less effort has been made to address the issues of moving query updating and optimisation, which are crucial factors affecting system performance. In this thesis, we attempt to investigate this possibility by proposing four new processing techniques. First, we introduce a new “approximate moving range query” to optimise the query process in two ways: i) we reduce the amount of time needed to obtain the results; and ii) we give the users alternative options in order to avoid another search(es) when searching an empty result or a massive number of objects in the result. The result of our experiments show that our techniques are successful in terms of reducing the number of split points and false hits. Also, the approximate results are of a high quality compared to the exact results. Furthermore, our algorithms reduce the number of communications between the mobile device and the databases server, indicating their performance is better in terms of lower search time and improved search accuracy. Second, we present a technique to deal with the moving range query called “safe region”. The high computation and communication costs of monitoring and updating the location of the moving range query needs to be considered, as the calculation of the range query needs to be re-evaluated whenever the query moves. Our aim is to avoid any communication between the query and the server while the query moves within the specified safe region. We have extended the size of the safe region to reduce the amount of supplementary communication. Our main objective is to reduce the need for continuous monitoring of the query, and eliminate the need for the user to follow a defined path. Third, we propose a linear model called “monitoring moving range query” to monitor moving queries inside a safe region. Our technique gives the users the ability to monitor themselves and inform the server when leaving the safe region. This will give the user more privacy and reduce the load on the server. Also, our technique will eliminate the need for the…