A Method for k Nearest Neighbor Query of Line Segment in Obstructed Spaces


Liping Zhang, Song Li, Yingying Guo, Xiaohong Hao, Journal of Information Processing Systems Vol. 16, No. 2, pp. 406-420, Apr. 2020  

10.3745/JIPS.04.0167
Keywords: Line Segment k Nearest Neighbor, Line Segment Obstacle Distance, Line Segment Voronoi Diagram, Nearest Neighbor Query, spatial database
Fulltext:

Abstract

"In order to make up the deficiencies of the existing research results which cannot effectively deal with the nearest neighbor query based on the line segments in obstacle space, the k nearest neighbor query method of line segment in obstacle space is proposed and the STA_OLkNN algorithm under the circumstance of static obstacle data set is put forward. The query process is divided into two stages, including the filtering process and refining process. In the filtration process, according to the properties of the line segment Voronoi diagram, the corresponding pruning rules are proposed and the filtering algorithm is presented. In the refining process, according to the relationship of the position between the line segments, the corresponding distance expression method is put forward and the final result is obtained by comparing the distance. Theoretical research and experimental results show that the proposed algorithm can effectively deal with the problem of k nearest neighbor query of the line segment in the obstacle environment."


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from November 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.




Cite this article
[APA Style]
Liping Zhang, Song Li, Yingying Guo, & Xiaohong Hao (2020). A Method for k Nearest Neighbor Query of Line Segment in Obstructed Spaces. Journal of Information Processing Systems, 16(2), 406-420. DOI: 10.3745/JIPS.04.0167.

[IEEE Style]
L. Zhang, S. Li, Y. Guo and X. Hao, "A Method for k Nearest Neighbor Query of Line Segment in Obstructed Spaces," Journal of Information Processing Systems, vol. 16, no. 2, pp. 406-420, 2020. DOI: 10.3745/JIPS.04.0167.

[ACM Style]
Liping Zhang, Song Li, Yingying Guo, and Xiaohong Hao. 2020. A Method for k Nearest Neighbor Query of Line Segment in Obstructed Spaces. Journal of Information Processing Systems, 16, 2, (2020), 406-420. DOI: 10.3745/JIPS.04.0167.