Efficient ϵ-Approximate k-Flexible Aggregate Nearest Neighbor Search for Arbitrary ϵ in Road Networks

Recently, complicated spatial search algorithms have emerged as spatial-information-based applications, such as location-based services (LBS), and have become very diverse and frequent. The aggregate nearest neighbor (ANN) search is an extension of the existing nearest neighbor (NN) search; it finds the object (Formula presented.) that minimizes (Formula presented.) from a set Q of M (≥1) query objects, where (Formula presented.) is an aggregate function and (Formula presented.) is the distance between two objects. The flexible aggregate nearest neighbor (FANN) search is an extension of the ANN search by introducing flexibility factor  (Formula presented.) ; it finds the object (Formula presented.) that minimizes (Formula presented.) from (Formula presented.), a subset of Q with (Formula presented.). This paper proposes an efficient (Formula presented.) -approximate k-FANN (Formula presented.) search algorithm for an arbitrary approximation ratio (Formula presented.) (≥1) in road networks. In general, (Formula presented.) -approximate algorithms are expected to give an improved search performance at the cost of allowing an error ratio of up to the given (Formula presented.). Since the optimal value of (Formula presented.) varies greatly depending on applications and cases, the approximate algorithm for an arbitrary (Formula presented.) is essential. We prove that the error ratios of the approximate FANN objects returned by our algorithm do not exceed the given (Formula presented.). To the best of our knowledge, our algorithm is the first (Formula presented.) -approximate k-FANN search algorithm in road networks for an arbitrary (Formula presented.). Through a series of experiments using various real-world road network datasets, we demonstrated that our approximate algorithm always outperformed the previous state-of-the-art exact algorithm and that the error ratios of the approximate FANN objects were significantly lower than the given (Formula presented.) value.