Fast Algorithm of Nearest Neighbor Query for Line Segments of Spatial Database

The definitions of the orders between line segments are given according to their MBRs. Based on the orders, an index structure—SI-tree for line segments is proposed with the aim of improving the efficiency for nearest neighbor query. In the structure, it is set that the children nodes of each middle node are arranged in some order according to their geometric locations so that the positions of data can be determined quickly when nearest neighbor query is taken on the structure. It is a brand new way to process this kind of problems. Three pruning rules for NN query are created, by which a lot of unnecessary computations can be reduced to achieve effective screening and filtering of data when corresponding query is processed so that the speed of query is quicken. In the pruning rules, the main computing used to make decision to prune a node is judgment, which is simpler than that used in other algorithms of the same kind of problems. A new nearest query algorithm for line segment data set and the proofs of the algorithms'correctness and termination are presented. The experiments show that the efficiency of query with the new algorithms presented in this paper is greatly improved, compared with that of the current algorithms used to solve the same problems when nearest neighbor query is processed.