Moving range query processing in spatial databases
thesisposted on 23.02.2017 by AL-Khalidi, Haidar
In order to distinguish essays and pre-prints from academic theses, we have a separate category. These are often much longer text based documents than a paper.
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 user to follow a defined path. We use the time and the concept of the safe region together, hence, if the query makes a sudden turn, the result will not be affected because the query will still be located inside the safe region. Finally, we introduce a novel query processing technique for the moving range query in spatial network databases, called “lookforward moving range query”. Our technique is related to Euclidean and network distance to retrieve related objects and at the same time to exclude unrelated ones. Our technique can distinguish between the significant important objects and the minor important objects inside the range query. Our technique improves the selectivity of the filter step to reduce the number of candidate objects, and consequently, minimise the number of communications between the mobile device and the database server. The lookforward moving range query achieves a better running time and delivers a better performance having fewer split points than the original moving range query as shown on our experiments.