Query And Update Over Uncertain Moving Objects

Location based service depends on the efficient management of moving objects.Uncertainty is one key feature of the moving objects,performed in attribute uncertainty,positional uncertainty and exist uncertainty.In order to provide more reliable and high quality service,we need query results to limit inaccuracy in a certain range,on account of uncertainty of the moving objects.Existed query and update over uncertain moving objects aim to improve the efficiency of querying to provide real-time location service.However,update is inefficient,furthermore,they can't effectively solve the problem of dynamic changes of moving objects attributes.Based on the above,the thesis studies query and update over uncertain moving objects.Analysis and summary based on relevant research at home and abroad,proposing an effective which support dynamic changes of moving objects attributes algorithm to solve the multi-objective optimization query in the obstacle space and index structure of uncertain moving objects for frequent updates.The main research work and contributions are summarized as follows:(1)Combine multi-objective optimization algorithms of uncertain moving objects with interior obstacle space,research and analysis of the existing indoor environment moving objects distance calculation model,improve the calculation model based on viewing area model.Propose an effective multi-objective optimization algorithm DSP-Topk(Dynamic and Support Pruning Topk).The algorithm for uncertain moving objects with multiple attributes,adopt pruning strategy with preprocessing to decrease the target set size,introduction of the target objects dynamic adjustment mechanism,furthermore,the concept of dynamic and static sets were introduced.The experimental results show that the DSP-Topk is correct and query performance advantage.(2)Based on existing support uncertainty of moving objects index TPU-tree,give an index structure named GTPU-tree(Group Time-Parameterized Uncertain-tree)that supports relate to moving objects trajectories.GTPU-tree using spatial trajectory similarity to describe the trajectory of moving objects similarity,divide the similarity of moving objects into a group.Propose a mixed update strategy based on GTPU-tree.Mixed update strategy reduces update cost by reducing the number the update number,in order to ensure the moving objects in the same group have higher trajectory similarity,need to detect periodically trajectory similarity of moving objects in the same group.The experimental results show that the GTPU-tree performance advantage on reducing update cost when uncertain moving objects'positions update frequently.(3)Based on the GTPU-tree,we propose an index structure named HGTPU-tree(Hash Group Time-Parameterized Uncertain-tree).HGTPU-tree query supports bottom-up with zero order index hash table,when uncertain moving objects' positions update,reduces query consume time of leaf nodes,and through reducing the update number in the same group,thus decreasing the update cost.In the aspect of memory overhead,HGTPU-tree using synchronous update mechanism to solve the existing bottom-up updating indexs due to the large memory overhead cause of the decline of the system stability,especially in the number of moving objects.