Indexing methods for moving object databases
Hanan Samet, Jagan Sankaranarayanan, Michael Auerbach · 2013
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.