DSB-tree: an improved spatial data index structure based on SS-tree

摘要

Using approximate geometrical expression to construct spatial data index becomes to an effective method because of the complexity of spatial entity. The simple exterior approximate expression could not satisfy the multiple query requirements to the spatial dataset. Obvious distance and topology relationships can be found between spatial data, especially the two or three dimensions spatial data used in GIS. Circle shape is can be constructed and expressed with a low amount of data, and all kinds of operations on distance and topology are exceedingly simple and easy to implement. A novel index structure named double sphere balance tree and abbreviated as DSB-tree is represented with importing maximum enclosed circle (MEC) as interior approximate expression based on SS-tree. Due to the double approximate expression constructed with two circles (MBC and MEC), all the operations of DSB-tree are low cost and more effective. We implement the structure and its basal operations as spatial data index, including insertion, remove and query. Finally, the extensive experiments and their results are given to discuss the performance of the DSB-tree for the NN query.