Probabilistic Range Query over Uncertain Moving Objects in Constrained Two-Dimensional Space

• Published in: IEEE transactions on knowledge and data engineering 2015-03, Vol.27 (3), p.866-879
• Main Authors: Zhi-Jie Wang, Dong-Hua Wang, Bin Yao, Minyi Guo
• Format: Article
• Language: English
• Subjects: Adaptation models; Computational modeling; Probabilistic logic; Probability density function; Solid modeling; Trajectory; Uncertainty
• ISSN: 1041-4347; 1558-2191
• DOI: 10.1109/TKDE.2014.2345402

Probabilistic range query (PRQ) over uncertain moving objects has attracted much attentions in recent years. Most of existing works focus on the PRQ for objects moving freely in two-dimensional (2D) space. In contrast, this paper studies the PRQ over objects moving in a constrained 2D space where objects are forbidden to be located in some specific areas. We dub it the constrained space probabilistic range query (CSPRQ). We analyze its unique properties and show that to process the CSPRQ using a straightforward solution is infeasible. The key idea of our solution is to use a strategy called pre-approximation that can reduce the initial problem to a highly simplified version, implying that it makes the rest of steps easy to tackle. In particular, this strategy itself is pretty simple and easy to implement. Furthermore, motivated by the cost analysis, we further optimize our solution. The optimizations are mainly based on two insights: (i) the number of effective subdivisions is no more than 1; and (ii) an entity with the larger span is more likely to subdivide a single region. We demonstrate the effectiveness and efficiency of our proposed approaches through extensive experiments under various experimental settings, and highlight an extra finding - the precomputation based method suffers a non-trivial preprocessing time, which offers an important indication sign for the future research.