NU2RA: An Analysis Method for Range Queries over Uncertain Moving Objects in Road Networks

The positions of moving objects are assumed to be exactly known in most researches on different types of queries. In fact, except for updating instants, moving objects exact locations are not known, but are bounded by uncertainty regions. So the algorithms based on precise positions are inapplicable. Existing algorithms that involve uncertainty concern either uncertain querying objects or uncertain interesting objects moving in Euclidean space. Aiming at the uncertain range queries over uncertain objects constrained in road network, an analysis method named NU/+2RA is proposed here. The length of shortest path instead of the Euclidean distance is used. Network distances between two uncertain objects are defined. The network is partitioned into 5 parts according to uncertain query ranges. Possible distributions of objects are represented with distribution codes, and 22 kinds of topological relations between uncertain objects and uncertain ranges are identified. Query answers are augmented with probabilistic guarantees of the validity of answers. Probability evaluation in each case is derived. NU/+2RA, being independent of concrete uncertain moving objects models, provides the general topology analysis and probability evaluation for uncertain range queries in road network. The method is applicable to both uncertain history trajectories and uncertain current and near future motions of moving objects.