Research On The Methods Of Uncertainty Data Indexing And Querying In Mobile Environments

One of the most important research issues in MOD is the problem of modeling andquerying the location of moving objects. Much work exists on traditional spatial andspatio-temporal queries, but there has recently attracted much research interest inevaluating such queries in the presence of uncertainty. This is reasonable, due to locationupdate delay, sampling error, or limitation of measuring equipments, it is rarely possiblefor the database to record the exact positions of moving objects at all times. Theconventional objects indexing methods and query processing techniques assume that thedata are precise, so they cannot be directly applied for uncertain data processing. As aresult, in the context of uncertain database, efficient indexing methods and correspondingquery processing techniques should be developed to guarantee the accuracy of answer andspeed up the query performance.U-tree is currently the most popular indexing method for the imprecise positions ofstationary objects. It minimizes the amount of qualification probability computation inrange search and it's fully dynamic for the objects can be inserted or deleted in any order.However, it can not deal with the moving objects with uncertainty.In the mobile environment, a spatio-temporal indexing structure TPU-tree, which is anovel U-tree based indexing technique, can combine the issues of timestamp to predict thefuture location of uncertain evolving data. Along with the data models capturing thespatial-temporal uncertainty and TPU-tree, a modified p-bound based range queryalgorithms (MP_BBRQ), using probabilistic pruning regions and corresponding decisionheuristic rules, can speed up the probabilistic range queries; and a branch and boundalgorithm for constrained probabilistic skyline (B~2CPS), using the best-first searchstrategy of nearest neighbor, can minimum the node access numbers. New probabilistic spatial queries are more expensive to compute. The disk I/O- andcomputationally-efficient algorithms should be explored to enhance the performance ofprobabilistic range queries, probabilistic k nearest-neighbor queries. Specifically, aprobabilistic k nearest neighbor query returns k objects with the highest probability ofbeing the k-th nearest neighbor to a given query point Q. Comparedto the k-NN query intraditional databases, which retrieves k closest objects to the given query point, thecomputation cost of k-PNN is very expensive due to the costly numerical integration orMonte-Carlo approach it adopts. In order to speed up the k-PNN query processing,efficient spatial and probabilistic pruning approaches are used to reduce the search space,thus the costly numerical evaluation of complex integrals can be avoided as much aspossible. The Spatial and probabilistic pruning approaches can be seamless integrated inthe query procedure. Extensive experiments have been conducted to demonstrate theefficiency and effectiveness of algorithms under various parameter settings.There are many research issues exist in the uncertain database. It would be interestingto apply new probabilistic queries techniques to solve new problems are explored, such asprobabilistic joins, probabilistic Top-k, probabilistic reverse nearest neighbors, andprobabilistic reverse skyline queries. For these kinds of probabilistic queries, how tointegrate these processing methods to DMBS will be new research issues. Furthermore,extend the current works to handle high dimensional data, and consider non-Euclideandistance could be another interesting directions. In the uncertain streaming environment,how to develop efficient memory indexing method, and speed up kind of streamingqueries will also be very potential research problems.