A Method for k Nearest Neighbor Query of Line Segment in Obstructed Spaces
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
In order to make up the deficiencies of the existing research results which cannot effectively deal with thenearest neighbor query based on the line segments in obstacle space, the k nearest neighbor query method ofline segment in obstacle space is proposed and the STA_OLkNN algorithm under the circumstance of staticobstacle data set is put forward. The query process is divided into two stages, including the filtering processand 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 expressionmethod is put forward and the final result is obtained by comparing the distance. Theoretical research andexperimental results show that the proposed algorithm can effectively deal with the problem of k nearestneighbor query of the line segment in the obstacle environment.
Abstract
In order to make up the deficiencies of the existing research results which cannot effectively deal with thenearest neighbor query based on the line segments in obstacle space, the k nearest neighbor query method ofline segment in obstacle space is proposed and the STA_OLkNN algorithm under the circumstance of staticobstacle data set is put forward. The query process is divided into two stages, including the filtering processand 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 expressionmethod is put forward and the final result is obtained by comparing the distance. Theoretical research andexperimental results show that the proposed algorithm can effectively deal with the problem of k nearestneighbor query of the line segment in the obstacle environment.
참고문헌 (26)
- C. Efstathiades, "Efficient processing of relevant nearest-neighbor queries", ACM Transactions on Spatial Algorithms and Systems (TSAS),, 2(3) (2016)
- S. Suri, "On the most likely voronoi diagram and nearest neighbor searching", International Journal of Computational Geometry & Applications, 26(3-4), pp.151~166 (2016)
- O. F. Ertugrul, "A novel version of k nearest neighbor : dependent nearest neighbor", Applied Soft Computing, 55, pp.480~490 (2017)
- C. Li, "kNN query processing approach for content with location and time tags", Journal of Software, 27(9), pp.2278~2289 (2016)
- Y. Jing, "Authentication of k nearest neighbor query on road networks", IEEE Transactions on Knowledge and Data Engineering, 26(6), pp.1494~1506 (2013)
- S. Dasgupta, "Randomized partition trees for exact nearest neighbor search", Algorithmica, 72(1), pp.237~263 (2015)
- S. Yi, "Reverse view field nearest neighbor queries", Information Sciences, 402, pp.35~49 (2017)
- A. Hidayat, "Reverse approximate nearest neighbor queries", IEEE Transactions on Knowledge and Data Engineering, 30(2), pp.339~352 (2017)
- Z. Liu, "Aggregate nearest neighbor queries in uncertain graphs", World Wide Web, 17(1), pp.161~188 (2014)
- T. Hashem, "Protecting privacy for distance and rank based group nearest neighbor queries", World Wide Web, 22(1), pp.375~416 (2019)
- A. P. Sistla, "Continuous nearest-neighbor queries with location uncertainty", The VLDB Journal, 24(1), pp.25~50 (2015)
- Y. Wang, "Continuous nearest-neighbor query in location privacy preserving", Journal of Beijing University of Posts & Telecommunications, 39(5), pp.83~88 (2016)
- P. K. Agarwal, "Nearest-neighbor searching under uncertainty II", ACM Transactions on Algorithms, 13(1) (2016)
- Z. Liu, "Aggregate nearest neighbor queries in uncertain graphs", World Wide Web, 17(1), pp.161~188 (2014)
- S. Li, "Strong neighborhood pair query in dynamic dataset", Journal of Computer Research and Development, 52(3), pp.749~759 (2015)
- H. Zhu, "Location privacy preserving obstructed nearest neighbor queries", Journal of Computer Research and Development, 51(1), pp.115~125 (2014)
- X. N. Yu, "A method for reverse k-nearest-neighbor queries in obstructed spaces", Jisuanji Xuebao(Chinese Journal of Computers), 34(10), pp.1917~1925 (2011)
- H. Zhu, "Range-based obstructed nearest neighbor queries", Proceedings of the 2016 International Conference on Management of Data, pp.2053~2068 (2016)
- Z. Yang, "Group obstacle nearest neighbor query in spatial database", Journal of Computer Research and Development, 50(11), pp.2455~2462 (2013)
- L. Zhang, "Voronoi-based group reverse k nearest neighbor query in obstructed space", Journal of Computer Research and Development, 54(4), pp.861~871 (2017)
- Z. Hao, "Line segment nearest neighbor query of spatial database", Journal of Computer Research and Development, 45(9), pp.1539~1545 (2008)
- R. Liu, "Fast algorithm of nearest neighbor query for line segments of spatial database", Journal of Computer Research and Development, 48(12), pp.2379~2384 (2011)
- Z. Yi, "Research on line segment kNN query in spatial database", Computer Engineering and Applications, 51(18), pp.131~134 (2015)
- Y. Gu, "Efficient moving k nearest neighbor queries over line segment objects", World Wide Web, 19(4), pp.653~677 (2016)
- M. Held, "VRONI : an engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments", Computational Geometry, 18(2), pp.95~123 (2001)
- "Road network of the State of California" (2016)[URL]