Moving object databases arise in numerous applications such as traffic monitoring, crowd tracking, and games. They all require keeping track of objects that move and thus the database of objects must be constantly updated. The cover fieldtree (more commonly known as the loose quadtree and the loose octree, depending on the dimension of the underlying space) is designed to overcome the drawback of spatial data structures that associate objects with their minimum enclosing quadtree (octree) cells which is that the size of these cells depends more on the position of the objects and less on their size. In fact, the size of these cells may be as large as the entire space from which the objects are drawn. The loose quadtree (octree) overcomes this drawback by expanding the size of the space that is spanned by each quadtree (octree) cell c of width w by a cell expansion factor p (p>0) so that the expanded cell is of width (1+p)*w and an object is associated with its minimum enclosing expanded quadtree (octree) cell. It is shown that for an object o with minimum bounding hypercube box b of radius r (i.e., half the length of a side of the hypercube), the maximum possible width w of the minimum enclosing expanded quadtree cell c is just a function of r and p, and is independent of the position of o. Normalizing w via division by 2r enables calculating the range of possible expanded quadtree cell sizes as a function of p. For p >= 0.5 the range consists of just two values and usually just one value for p >= 1. This makes updating very simple and fast as for p >= 0.5, there are at most two possible new cells associated with the moved object and thus the update can be done in O(1) time. Experiments with random data showed that the update time to support motion in such an environment is minimized when p is infinitesimally less than 1, with as much as a one order of magnitude increase in the number of updates that can be handled vis-a-vis the p=0 case in a given unit of time. Similar results for updates were obtained for an N-body simulation where improved query performance and scalability were also observed.
What is a Loose Quadtree?
The cover fieldtree and the equivalent
loose quadtree (loose octree in three dimensions),
is obtained by expanding the size of the space
that is spanned by each quadtree block
c of width w by a block expansion factor p (p>0) so that the
expanded block is of width w.(1+p).
Thus instead of associating (inserting) objects with (into) their
minimum enclosing quadtree blocks as in MX-CIF quadtrees,
they are associated with (inserted
into) their minimum expanded quadtree block.
For additional information, please see pages 257-259, 466-473 and 827-832 of Samet,
Foundations of Multidimensional and Metric Data Structures
and, see pages 200-213 of Samet, Design and Analysis of Spatial Data Structures.
Video
This video tiled ``Crates and Barrels'' is an N-body simulation of 14,000 objects. This simulation shows the comparisons between the performance of loose quadtree with a looseness factor of p=0.999 with that of MX-CIF quadtree. Note that the video renders all the cells in the quadtree which is expensive as it requires traversing the entire tree. To an extent this diminishes the advantage of the loose quadtree compared to the MX-CIF quadtree. In spite of these limitations of the setup, the loose quadtree performs significantly better than the MX-CIF quadtree. Please make sure to set the video to a high resolution using a button at the bottom right corner of the player.
Applet
In Insert mode, click and drag to specify a new rectangle. In
Delete mode click inside an existing rectangle to remove it from
the quadtree. If you click in an area that is occupied by several rectangles,
one of them will be chosen arbitrarily and deleted.
In Move mode, you can click and drag to specify
a rectangle. The yellow rectangle corresponds to the rectangle that is being
operated upon. The blue square is the minimum enclosing
quadtree block containing the yellow
rectangle. The green square corresponds to the expanded blue quadtree block,
containing the yellow rectangle. The yellow rectangle is reinserted in to the
loose quadtree as soon as the centroid of the yellow rectangle extends
past the blue quadtree block.
In Motion Insensitivity mode, you can click and drag to specify
a rectangle. The yellow rectangle corresponds to the rectangle that is being
operated upon. The blue square is the minimum enclosing quadtree block containing the yellow
rectangle. The green square corresponds to the expanded blue quadtree block,
containing the yellow rectangle. The yellow rectangle is reinserted in to the
loose quadtree as soon as it touches the green square.
The difference between Motion Insensitivity and the Move operation is that
in the case of the Motion Insensitivity the centroid of the yellow
rectangle can lie outside the blue quadtree block.
In Show Quadtree mode, the yellow rectangle corresponds to the rectangle that is being
operated upon. The blue square is the minimum enclosing quadtree block containing the yellow
rectangle. The green square corresponds to the expanded blue quadtree block,
containing the yellow rectangle.
Acknowledgments
This work was supported in part by the National Science
Foundation under grants CCF-05-15241, IIS-0713501, IIS-10-18475,
IIS-12-19023, Microsoft Research, Google, NVIDIA, the E.T.S. Walton
Visitor Award of the Science Foundation of Ireland, and the National
Center for Geocomputation at the National University of Ireland at Maynooth.