Continuous obstructed range queries in spatio-temporal databases

In this paper, we study the Continuous Obstructed Range (COR) queries in spatio-temporal databases, which consider the impact of obstacles on the distance between objects. Given a data set P, an obstacle set O, a query point q and a positive value r, a COR query continuously retrieves every point p from P such that the obstructed distance between p and q is less than r, where the obstructed distance is the shortest path between p and q without crossing any obstacle in O. The moving object candidates are divided into several groups according to the obstacles blocking the immediate path from moving objects to query point and the corresponding small local group visibility graphs are constructed. An efficient method is proposed to reduce the time and space costs of computing the obstructed distance. An identification strategy is designed to efficiently process the update of moving objects via directly identifying the qualified objects. Extensive experiments with both real and synthetic data sets demonstrate the efficiency and effectiveness of our proposed algorithm.