Efficiently Producing the K Nearest Neighbors in the Skyline for Multidimensional Datasets

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.

Authors and Affiliations

1. Universidad Simón Bolívar, Venezuela

   Marlene Goncalves & Maria-Esther Vidal

Editors and Affiliations

1. Facultad de Informática, Universidad Politécnica de Madrid, Campus de Montegancedo S/N, Boadilla del Monte, 28660, Madrid, Spain

   Pilar Herrero

2. Research Centre for Automatic Control, School of Engineering in Information Technology, University of Lorraine, CNRS, Campus scientifique, BP 70239, 54506, Vandoeuvre-les-Nancy, France

   Hervé Panetto

3. Department of Computer Science, Semantic Technology and Application Research Laboratory (STARLab), Vrije Universiteit Brussel, Building G-10, Pleinlaan 2, 1050, Brussels, Belgium

   Robert Meersman

4. La Trobe University, Melbourne, VIC, Australia

   Tharam Dillon

Reprints and permissions

© 2012 Springer-Verlag Berlin Heidelberg

Policies and ethics