The Study Of The Probabilistic Query Processing Techniques And The Analysis Of The Reachable Region For Moving Objects Located In A Constrained Space

With the rapid advancement of computer technologies such as wireless networks, computer storages, moving object databases as a branch of spatial databases has been receiving more and more attention from both domestic and foreign scholars. As query processing is a common operation in moving object databases, and the manners and/or ways to query the objects are diversity, consequently, query processing on moving objects has been a very active area. Recently,researchers noted a fact that moving object data usually contain uncertainty due to various reasons. To tackle it, many representative models were proposed, and probabilistic query processing on moving objects has been also received much attention. For example, probabilistic range query,probabilistic nearest neighbor query, and probabilistic skyline query, etc. View the development process of probabilistic query processing technologies, we realize that existing works can be generally classified into two types: one is to assume that objects can freely move in two-dimensional space without any constraint; another is to assume that objects move on predefined road networks.Recently, many research results about these two types of works have been reported. Regarding to probabilistic query processing for objects moving in a constrained space, little results are reported.In view of these, this dissertation takes the objects moving in a constrained space as the research object, and considers how to efficiently answer probabilistic queries as well as other related issues.The main contributions of this dissertation include:(1)It proposes constrained-space probabilistic range query for uncertain moving objects,analyzes the nature of this problem, and proves that a straightforward method is infeasible. It develops efficient solution, its key idea is to use a strategy called pre-approximation. Moreover, it further optimizes the solution based on two important insights. Experimental results demonstrate the superiority of the proposed method, and report an extra finding, i.e., the pre-computation based method suffers a non-trivial pre-computing time. This finding offers an important indication sign for the future research.(2) It proposes explicit and implicit constrained-space probabilistic threshold range queries,and proves that technologies used for the traditional probabilistic threshold range query are not well suitable for the context of our concern. It develops a suit of techniques used to answer explicit query. Its key ideas are to swap the order of geometrical operations, and to use a multi-step way to compute the appearance probability. Afterwards, it extends these techniques to answer implicit query, in which an enhanced multi-step mechanism is developed. Moreover, it further optimizes the solutions based on a new insight, i.e., different candidate moving objects may share same candidate restricted areas. Also, it gives rigorous theoretical analysis for the proposed algorithms, and shows these proposed techniques can be easily extended to answer other types of probabilistic threshold queries. Finally, its demonstrates the effectiveness and efficiency through extensive experiments,and the experimental results also further show the differences between explicit and implicit queries.(3) It proposes the problem of computing the reachable region of moving object, and demonstrates that the so-call rough solution is incorrect. It develops a simple-version algorithm for the sake of intuition, its basic idea is to reduce this problem into the problem of computing the Boolean union of a set of circular visibility regions. This algorithm takes O(n3) time. By analyzing its dominant steps, it breakthroughs the bottleneck by incorporating the shortest path map technique,obtaining an O(n2log n) algorithm. Finally, it gives some new insights about the properties of shortest path map, and uses these properties to construct the final algorithm, which obtains an O(n log n) worst case upper bound.(4) It points out that circular-arc polygon is a special or degenerated case of conic polygon,and illustrates that Boolean operation of circular-arc polygons can also find many applications. It designs a concise and easy-to-operate data structure, and develops a targeted algorithm based on this data structure. Elaborate theoretical analysis and extensive experiments verify the superiority of the proposed algorithm.