An extended MD-tree with internal leaf for efficient management of moving objects

Abstract

Management systems for moving objects such as automobiles, airplanes, ships, and humans, must not only manage the moving objects efficiently but also quickly provide information about their surroundings on demand, because a moving object must know its environment to determine optimal solutions, e.g., the best path to a destination. In this paper, an efficient method for managing moving objects is proposed. This method is developed by extending the spatial data structure, MD-tree, through the introduction of two novel concepts, internal leaf and improvements in bottom-up search. The internal leaf that is managed by corresponding internal node in a tree has pointers to moving objects and helps reduce the update cost of the tree. The improved bottom-up search of the tree reduces the retrieval costs by managing the non-overlapped areas of split data space. Moreover, the usual spatial searches and updates of the tree can be executed as efficient as the MD-tree.