Assignment query and its implementation in moving object databases

Abstract

With the rapid development of wireless communications as well as positioning technologies, the concept of moving objects has become more and more important. Moving Objects Databases (MOD) are being used in a wide range of location based services that are of growing interest in many application areas. In the literature, several queries such as nearest neighbor, reverse nearest neighbor, k-nearest neighbor, proximity queries etc. have been considered in moving object databases. Differently from these, in this thesis, a novel operator is proposed as a query type for moving object databases, and also a possible implementation is presented. The aim of the proposed assignment query is to solve the assignment problem, which is also known as weighted bipartite matching. In short, our objective is to find a perfect matching between two set of objects in a manner that minimizes the total cost. For instance, a set of people is to be assigned to a set of taxicabs with minimal total travel time. On the other hand, working with moving object databases, we have to give near realtime responses to user queries to provide an efficient solution for the problem. Unfortunately, the problem of finding a minimal-cost matching for a general bipartite graph is known to have an O(N3) time algorithm. Thus, we realized that classical solutions having a time complexity of O(N3) become infeasible for this type of moving object database application. In this thesis, we propose an assignment query that responds in a reasonable time period for MOD. Furthermore, we employ a Q+Rtree index structure to cope with the high update and querying overhead of MOD. At the end, we discussed the performance issues to improve efficiency and showed that the time complexity of our application meets the needs of users in mobile environment.