Abstract
This paper proposes several strategies for continuous k-nearest neighbour query processing in location-based services. All utilize a clustered dataset to create safe regions. The only previously proposed strategy to do so has limited validation of the safe region on the client, which leads to only approximate k-nearest neighbour results being obtained. This work improves upon both the creation of the safe region and the validation of the safe region on the client. An evaluation of our strategy, including a comparison versus the existing strategy, show significant improvements in accuracy, and up to over 90% accuracy. When compared to repeated k-nearest neighbour search, our strategy is computationally significantly faster for larger datasets. Obtaining significantly high accuracy at low computational costs is significant for our strategies.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Cheng, R., Lam, K.Y., Prabhakar, S., Liang, B.: An efficient location update mechanism for continuous queries over moving objects. Inf. Syst. 32(4), 593–620 (2007)
Frank, E., Hall, M., Witten, I.: The weka workbench (2016). https://www.cs.waikato.ac.nz/ml/weka/Witten_et_al_2016_appendix.pdf. Accessed 14 Feb 2021
Gao, Y., Zheng, B.: Continuous obstructed nearest neighbor queries in spatial databases. In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, pp. 577–590 (2009)
Gupta, M., Tu, M., Khan, L., Bastani, F., Yen, I.L.: A study of the model and algorithms for handling location-dependent continuous queries. Knowl. Info. Syst. 8(4), 414–437 (2005)
Huang, Y.K., Chen, C.C., Lee, C.: Continuous k-nearest neighbor query for moving objects with uncertain velocity. GeoInformatica 13(1), 1–25 (2009)
Huang, Y.K., Chen, Z.W., Lee, C.: Continuous k-nearest neighbor query over moving objects in road networks. In: Proceedings of the International Conference on APWeb/WAIM, pp. 27–38 (2009)
Ilarri, S., Bobed, C., Mena, E.: An approach to process continuous location-dependent queries on moving objects with support for location granules. Jnl. Syst. Soft. 84(8), 1327–1350 (2011)
Iwerks, G.S., Samet, H., Smith, K.P.: Maintenance of k-nn and spatial join queries on continuously moving points. ACM Trans. Database Syst. 31(2), 485–536 (2006)
Ku, W.S., Zimmermann, R., Wang, H.: Location-based spatial query processing with data sharing in wireless broadcast environments. IEEE Trans. Mob. Comput. 7(6), 778–791 (2008)
Lam, K.Y., Ulusoy, Ö.: Adaptive schemes for location update generation in execution location-dependent continuous queries. Jnl. Syst. Soft. 79(4), 441–453 (2006)
Liu, F., Hua, K.A.: Moving query monitoring in spatial network environments. Mob. Netw. Appl. 17(2), 234–254 (2012)
Mouratidis, K., Papadias, D.: Continuous nearest neighbor queries over sliding windows. IEEE Trans. Knowl. Data Eng. 19(6), 789–803 (2007)
Osborn, W.: Continuous k-nearest neighbour strategies using the MQR-tree. In: Proceedings of the 21st International Conference on Network-Based Information Systems (2018)
Osborn, W., Anderson, C.: Approximate continuous nearest neighbour query processing in clustered point sets. In: Proceedings of the 11th Annual IEEE IEMCON Conference (2020)
Osborn, W., Keykavoos, F.: Continuous region query processing in clustered point sets. In: Proceedings of the 16th International Conference on Mobile Systems and Pervasive Computing, pp. 282–288 (2019)
Schiller, J.H., Voisard, A. (eds.): Location-Based Services. Morgan Kaufmann (2004)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Osborn, W. (2021). Using Clusters for Approximate Continuous k-Nearest Neighbour Queries. In: Barolli, L., Woungang, I., Enokido, T. (eds) Advanced Information Networking and Applications. AINA 2021. Lecture Notes in Networks and Systems, vol 225. Springer, Cham. https://doi.org/10.1007/978-3-030-75100-5_40
Download citation
DOI: https://doi.org/10.1007/978-3-030-75100-5_40
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-75099-2
Online ISBN: 978-3-030-75100-5
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)