We investigate the accuracy of continuous nearest neighbour queries along several trajectory types. Many Location Based Services (LBS) for continuous k nearest neighbour queries utilize a safe region approach when processing the query locally on a user’s device. Some approaches, however, are approximate as the safe region may be missing points of interest (POIs) which makes the query result invalid. This paper further investigates a cluster-based safe region approach that is proposed in the literature. Past studies of this approach did not focus on the accuracy of random trajectories. Therefore, we evaluate the cluster-based strategy using different random path scenarios to determine how close to 100% accuracy can be achieved. By varying the number of clusters, safe region size, the number of nearest neighbours and the distribution of the data, results show that the cluster-based strategy achieves high accuracy in most situations.