Journal of Information Processing Systems

Korea Information Processing Society (한국정보처리학회)
권호 표지
DOI QR코드

DOI QR Code

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

  • Zhang, Liping (College of Computer Science and Technology, Harbin University of Science and Technology) ;
  • Li, Song (College of Computer Science and Technology, Harbin University of Science and Technology) ;
  • Guo, Yingying (College of Computer Science and Technology, Harbin University of Science and Technology) ;
  • Hao, Xiaohong (College of Computer Science and Technology, Harbin University of Science and Technology)
  • Received : 2018.11.19
  • Accepted : 2019.02.27
  • Published : 2020.04.30
Download PDF
⟨ Previous Next ⟩

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.

Keywords

References

  1. C. Efstathiades, A. Efentakis, and D. Pfoser, "Efficient processing of relevant nearest-neighbor queries," ACM Transactions on Spatial Algorithms and Systems (TSAS), vol. 2, no. 3, article no. 9, 2016.
  2. S. Suri and V. Verbeek, "On the most likely voronoi diagram and nearest neighbor searching," International Journal of Computational Geometry & Applications, vol. 26, no. 3-4, pp. 151-166, 2016. https://doi.org/10.1142/S0218195916600025
  3. O. F. Ertugrul and M. E. Tagluk, "A novel version of k nearest neighbor: dependent nearest neighbor," Applied Soft Computing, vol. 55, pp. 480-490. 2017. https://doi.org/10.1016/j.asoc.2017.02.020
  4. C. Li, D. R. Shen, M. D. Zhu, Y. Kou, T. Z. Nie, and G. Yu, "kNN query processing approach for content with location and time tags," Journal of Software, vol. 27, no. 9, pp. 2278-2289, 2016.
  5. Y. Jing, L. Hu, W. S. Ku, and C. Shahabi, "Authentication of k nearest neighbor query on road networks," IEEE Transactions on Knowledge and Data Engineering, vol. 26, no. 6, pp. 1494-1506, 2013. https://doi.org/10.1109/TKDE.2013.174
  6. S. Dasgupta and K. Sinha, "Randomized partition trees for exact nearest neighbor search," Algorithmica, vol. 72, no. 1, pp. 237-263, 2015. https://doi.org/10.1007/s00453-014-9885-5
  7. S. Yi, C. Shim, and Y. D. Chung, "Reverse view field nearest neighbor queries," Information Sciences, vol. 402, pp. 35-49, 2017. https://doi.org/10.1016/j.ins.2017.03.031
  8. A. Hidayat, S. Yang, M. A. Cheema, and D. Taniar, "Reverse approximate nearest neighbor queries," IEEE Transactions on Knowledge and Data Engineering, vol. 30, no. 2, pp. 339-352, 2017. https://doi.org/10.1109/tkde.2017.2766065
  9. Z. Liu, C. Wang, and J. Wang, "Aggregate nearest neighbor queries in uncertain graphs," World Wide Web, vol. 17, no. 1, pp. 161-188, 2014. https://doi.org/10.1007/s11280-012-0200-6
  10. T. Hashem, L. Kulik, K. Ramamohanarao, R. Zhang, and S. C. Soma, "Protecting privacy for distance and rank based group nearest neighbor queries," World Wide Web, vol. 22, no. 1, pp. 375-416, 2019. https://doi.org/10.1007/s11280-018-0570-5
  11. A. P. Sistla, O. Wolfson, and B. Xu, "Continuous nearest-neighbor queries with location uncertainty," The VLDB Journal, vol. 24, no. 1, pp. 25-50, 2015. https://doi.org/10.1007/s00778-014-0361-2
  12. Y. Wang, Y. H. Dong, J. B. Qian, and H. H. Chen, "Continuous nearest-neighbor query in location privacy preserving," Journal of Beijing University of Posts & Telecommunications, vol. 39, no. 5, pp. 83-88, 2016.
  13. P. K. Agarwal, B. Aronov, S. Har-Peled, J. M. Phillips, K. Yi, and W. Zhang, "Nearest-neighbor searching under uncertainty II," ACM Transactions on Algorithms, vol. 13, no. 1, article no. 3, 2016.
  14. Z. Liu, C. Wang, and J. Wang, "Aggregate nearest neighbor queries in uncertain graphs," World Wide Web, vol. 17, no. 1, pp. 161-188, 2014. https://doi.org/10.1007/s11280-012-0200-6
  15. S. Li, L. Zhang, and Z. Hao, "Strong neighborhood pair query in dynamic dataset," Journal of Computer Research and Development, vol. 52, no. 3, pp. 749-759, 2015.
  16. H. Zhu, J. Wang, B. Wang, and X. Yang, "Location privacy preserving obstructed nearest neighbor queries," Journal of Computer Research and Development, vol. 51, no. 1, pp. 115-125, 2014. https://doi.org/10.7544/issn1000-1239.2014.20130694
  17. X. N. Yu, Y. Gu, T. C. Zhang, and G. Yu, "A method for reverse k-nearest-neighbor queries in obstructed spaces," Jisuanji Xuebao (Chinese Journal of Computers), vol. 34, no. 10, pp. 1917-1925, 2011.
  18. H. Zhu, X. Yang, B. Wang, and W. C. Lee, "Range-based obstructed nearest neighbor queries," in Proceedings of the 2016 International Conference on Management of Data, San Francisco, CA, 2016, pp. 2053-2068.
  19. Z. Yang and Z. Hao, "Group obstacle nearest neighbor query in spatial database," Journal of Computer Research and Development, vol. 50, no. 11, pp. 2455-2462, 2013.
  20. L. Zhang, L. Liu, and X. Hao, S. Li, and Z. Hao, "Voronoi-based group reverse k nearest neighbor query in obstructed space," Journal of Computer Research and Development, vol. 54, no. 4, pp. 861-871, 2017.
  21. Z. Hao, Y. Wang, and Y. He, "Line segment nearest neighbor query of spatial database," Journal of Computer Research and Development, vol. 45, no. 9, pp. 1539-1545, 2008.
  22. R. Liu and Z. Hao, "Fast algorithm of nearest neighbor query for line segments of spatial database," Journal of Computer Research and Development, vol. 48, no. 12, pp. 2379-2384, 2011.
  23. Z. Yi and Z. Yang, "Research on line segment kNN query in spatial database," Computer Engineering and Applications, vol. 51, no. 18, pp. 131-134, 2015.
  24. Y. Gu, H. Zhang, Z. Wang, and G. Yu, "Efficient moving k nearest neighbor queries over line segment objects," World Wide Web, vol. 19, no. 4, pp. 653-677, 2016. https://doi.org/10.1007/s11280-015-0351-3
  25. M. Held, "VRONI: an engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments," Computational Geometry, vol. 18, no. 2, pp. 95-123, 2001. https://doi.org/10.1016/S0925-7721(01)00003-7
  26. KONECT, "Road network of the State of California," 2016; http://konect.uni-koblenz.de/networks/roadNet-CA.