Title: A spatial access method approach to continuous k-nearest neighbour processing for location-based services

Authors: Wendy Osborn

Addresses: Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge, Alberta, Canada

Abstract: In this paper, two strategies for handling continuous k-nearest neighbour queries for location-based services are proposed. CKNN1 and CKNN2 utilise a validity (i.e., safe) region approach for minimising the number of query requests that need to be send to the server. They also use a two-dimensional spatial access method for both validity region selection and in-structure searching. The latter feature ensures that new searches for a validity region are not required to begin from the root. An evaluation and comparison of both strategies is performed against repeated nearest neighbour search. Both random and exponentially distributed point sets are utilised. Results show that both approaches achieve significant performance gains, especially with respect to reducing the number of queries that must be sent from the client to the server.

Keywords: location-based services; continuous spatial queries; spatial access methods; k-nearest neighbour; mobile information systems.

DOI: 10.1504/IJGUC.2020.105540

International Journal of Grid and Utility Computing, 2020 Vol.11 No.2, pp.253 - 266

Received: 28 Feb 2019
Accepted: 10 Mar 2019

Published online: 03 Feb 2020 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article