Ripple: An approach to locate k nearest neighbours for location-based services

Abstract The increasing popularity of location-based services has led to a renewed interest in spatial query processing. In this paper, we propose Ripple, a light-weighted framework to find the nearest neighbours. The area is divided into square cells of equal size to form a grid structure. The search advances by progressively expanding the investigation region as a series of concentric squares, with the cell of query point as the centre. This is in contrast to the popular approach of increasing the search space as concentric circles. The circular search scheme explores only those square cells that intersect the circle and as a result, has a smaller search region. However, it has an added overhead of tracing the cells that intersect the circle for the same reason. In Ripple, there is no such additional overhead due to harmony in the investigation region’s configuration and the underlying grid structure. We optimize the search space by exploiting the distance between the query point and the distant candidate neighbours. Extensive experiments have been performed to compare the performance of the proposed approaches using different performance measures.