Regresar

Efficiently producing the K nearest neighbors in the skyline for multidimensional datasets

Abstract:

We propose a hybrid approach that combines Skyline and Top-k solutions, and develop an algorithm named k-NNSkyline. The proposed algorithm exploits properties of monotonic distance metrics, and identifies among the skyline tuples, the k ones with the lowest values of the distance metric, i.e., the k nearest incomparable neighbors. Empirically, we study the behavior of k-NNSkyline in both synthetic and real-world datasets; our results suggest that k-NNSkyline outperforms existing solutions by up to three orders of magnitude. © 2012 Springer-Verlag.