Query Processing Over Locationally Uncertain Moving Objects

Location data obtained from real world are imprecise or uncertain in MOD (Moving ObjectDatabases), LBS (Location-Based Services) and GIS (Geographical Information Systems), due to theaccuracy of positioning devices, updating protocols or characteristics of applications (for example,location privacy protection). Locationally uncertainty is an inherent characteristic of moving objectdata management and should be taken into consideration. Some query processing techniques foruncertain moving object are proposed in this dissertation.The main contributions are summarized as follows.Firstly, the probabilistic uncertain distance-based range (PUDR) query is defined. Not only thequery issuer but also data objects are uncertain in this type of query. The search range is dominated bythe distance threshold and the uncertain location of the query issuer. The location relationshipsbetween uncertain objects and uncertain search range are categorized into six cases and theprobability evaluation in each case is derived. The geometry and probabilistic properties of uncertainregions are utilized in the design of query processing algorithms. Query/node expanding range-basedand distance-based pruning stratgies are developed. The empirical performance experiments undervarious experimental settings are reported. It is verified by experiments that the proposed evaluationapproach outperforms Monte-Carlo method utilized by most existing work in the precision and timecost. It is shown that the algorithm based on the distance pruning rule performs the best among threeproposed algorithms and efficiently processes PUDR queries.Secondly, the difference of uncertainty and fuzziness in semantic is differentiated. These twokinds of indeterminacy are integrated into the query processing together. Two new types of queries areobtained, namely the fuzzy distance-based range (FDR) query and fuzzy spatio-temporal range (FSTR)query. Probability density functions (pdf) and fuzzy sets are utilized to represent the uncertainlocations of moving objects, the fuzzy spatial and temporal predicates in query conditions respectively.The matching degree is defined to represent the qualifying guarantees of uncertain objects about theblurry query conditions. On the utilization of the-cut of fuzzy distance threshold, the pruningtechniques based on the temporal intervals and distances are proposed. Rules are designed to rejectnon-qualifying objects and validate qualifying objects, in order to avoid unnecessary costly numericintegrations in refinement step. An extensive empirical study has been conducted to demonstrate theefficiency and scalability of the proposed algorithms for FDR queries and FSTR queries under various experimental settings. It is also verified by experiments that the locational uncertainty, the fuzzinessof spatial and temporal conditions have significant influence in the performance of algorithms.Thirdly, the mutual nearest neighbor query is defined in the context of uncertain scenario. Theproperties of uncertain mutual nearest neighbors (UMNN) are elaborated. The evaluation ofprobability is also derived. The processing algorithm is developed according to the principle that theset of q’s mutual nearest neighbors is the subset of q’s nearest neighbors. The pruning rule namedminimal farthest distance bound (MinFDB) is employed. An optimization strategy based on thesample list is designed in order to avoid the repeated sampling for the same object in probabilityevaluation. An empirical study, based on the experiments utilizing synthetic datasets, has beenconducted to demonstrate the efficiency and effectiveness of the proposed algorithm under variousexperimental settings. It turns out that the distribution, the cardinality of dataset and the radius ofuncertain domain have significant influence in the results and the performance of the algorithm. It isalso verified by experiments that the optimization strategy improves the efficiency of UMNN queryprocessing remarkably.Finally, a road network based uncertain objects and uncertain query range analysis (NU2RA)method is proposed for the uncertain distance-based range queries over uncertain objects constrainedin road network. Three network distances between two uncertain objects are defined. The network ispartitioned into five parts according to uncertain query ranges. Possible distributions of objects arerepresented with distribution codes.22kinds of topological relationship between uncertain objectsand uncertain ranges are identified. Probability evaluation in each case is derived. NU2RA method isindependent of concrete uncertain moving objects models, and provides the general topology analysisand probability evaluation method for uncertain range queries in road network. The method isapplicable to both uncertain history trajectories and uncertain current and near future motions ofmoving objects.