Processing kNN query on spatial polygons using DSB-tree

作者：Zhang Hengfei; Zeng Zhiyuan; Tan Xiaojun

来源：Journal of Information and Computational Science, 2012, 9(7): 1821-1834.

• Advanced structure
• Approximate expressions
• B+-trees
• Branch-and-bound algorithms
• Digital map
• DSB-tree
• K-nearest neighbors
• K-NN query
• Multiple approximations
• Optimal shape
• Real-world entities
• Spatial index structure
• Spatial indices
• SS-tree

In digital maps used in GIS, many real world entities are represented as spatial polygons. Some spatial index structures, such as R-tree and its variants, have capacity of managing polygons. But they could not process the queries on polygons efficiently since most of their subsequent studies were for points. Double-approximation Similarity-searching B+-tree, or termed as DSB-tree, is presented for spatial polygons specially which is an advanced structure based on SS-tree. DSB-tree employs minimum bounding circle and maximum enclosed circle together to approximately instead spatial polygons in some computing. Maximum enclosed circle can increase the precision of approximate expression and reduce the query expense substantially. Circle is the optimal shape for distance computing, and it brings instinctive advantage to DSB-tree on k nearest neighbors query. Branch and bound algorithm is adapted to DSB-tree in this paper to perform the k nearest neighbors query. Additionally, extensive experiments are conducted to study the performance of DSB-tree.

• 出版日期2012
• 单位华中科技大学