Parametric R-tree: An index structure for moving objects

We describe an indexing method for parametric rectangles that were recently proposed in [6] to represent moving ob-jects. Parametric rectangles are a more natural representa-tion of moving objects than moving points. Our indexing method extends R-trees, with the following important mod-ifications among others: (i) definition of parametric rectan-gle trees, or PR-trees (ii) searching a PR-tree for intersection queries (iii) insertion into PR-trees (iv) deletion from PR-trees. These modified operations need new algorithms for finding a minimum bounding parametric rectangle (MBPR) of a set of parametric rectangles and a new insertion and splitting criteria and algorithms. Experiments show that PR-trees provide a significant improvement over R-trees for intersection queries with moving rectangles. 1