Approximate Continuous Nearest Neighbour Query Processing in Clustered Point Sets

摘要

In this paper we propose a strategy for continuous k-nearest neighbour query processing for location-based services. Our approach applies clustering, which has not been applied to k-nearest neighbour processing by other works. Using a clustered point set on the server, a safe region is formed using a subset of the existing clusters. As long as the user's location (i.e., query point) remains in the safe region, the data set on the server can be used to accurately answer all k-nearest neighbour queries the majority of the time. Our strategy is an approximation strategy, as there are situations where the result produced for the user may not be accurate. However, an evaluation of our strategy show that the result is accurate at least 70% of the time in most cases. We also observed that when compared to repeated k-nearest neighbour search, our strategy is computationally significantly faster for a larger dataset. Therefore, it is worth the trade-off of less than 100% accuracy to achieve results quickly, and for several applications (e.g., restaurant searching), this can be ideal.