Search

A new type of the spatio-temporal queries is the Intelligent Probabilistic Collision Detection Query ( IPCDQ for short). In this paper, we focus on efficiently processing the IPCDQ on moving objects with uncertainty. Given two sets O and Q of objects, each of which moves with uncertain speed and direction, a time instant t, and a probability threshold P, the IPCDQ returns each pair of objects ( o, q) (where $$o \in O$$ and $$q \in Q$$ ), whose probability of colliding with each other is greater than or equal to P at time t. The pairs of objects satisfying the IPCDQ are termed the collision-possible pairs (or CPPs for short). We utilize a $$R^{lsd}$$ -tree, in which the spatially proximate objects with similar uncertain speeds and directions are grouped together, to effectively manage the moving objects in O. Similarly, a $$R^{lsd}$$ -tree is used to index the moving objects in Q. Then, with the two $$R^{lsd}$$ -trees for O and Q, respectively, we develop the specialized index traversals combined with three pruning criteria, the location-pruning criterion, the angle-pruning criterion, and the speed-pruning criterion to efficiently determine the objects that may collide with each other. Besides, to provide the more useful information to the user, we propose a probability model to quantify the possibility of each object pair being the query result. Comprehensive experiments demonstrate the efficiency and the effectiveness of the proposed methods. [ABSTRACT FROM AUTHOR]