Abstract

For spatial objects which are stored in database as polygons, an advanced spatial index based on MR-tree is proposed in this paper, which is named as MR+-tree. MR-tree adopts a maximum enclosed circle as interior approximation of a spatial object, and improves performance on spatial retrieval compared with R-tree. However, it can not deal well with shape diversity of spatial polygons. MR+-tree employs multiple enclosed circles to replace maximum enclosed circle, and overcomes that drawback of MR-tree. Theoretically, efficiency of MR+-tree outperforms MR-tree in all cases. Moreover, extensive experiments are conducted to study the performance of MR+-tree, which indicates that MR+-tree is an efficient and robust spatial index for polygonal objects.

Paper Details