Evaluating the spatial indexing of dense point sets

In this paper, we present an evaluation of the mqr-tree as a spatial access method for handling high-density point regions, such as world co-ordinates. Although previous work in spatial access methods focused on indexing objects of arbitrary size and performing region searches on them, recent applications that require the management of co-ordinate data also require that high-density point data be managed effectively by spatial access methods. The mqr-tree has shown promise in effectively managing point data. A comparison of the mqr-tree versus the benchmark R-tree shows that the mqr-tree can index high-density point regions effectively. In addition, searching dense point regions using the mqr-tree requires far fewer disk accesses than the R-tree when point density is very high.