Eclipse: Generalizing kNN and skyline
k nearest neighbor (kNN) queries and skyline queries are important operators on multi-dimensional data points. Given a query point, kNN returns the k nearest neighbors based on a scoring function such as a weighted sum of the attributes, which requires predefined attribute weights (or preferences). Skyline returns all possible nearest neighbors for any monotonic scoring functions without requiring attribute weights but the number of returned points can be prohibitively large.In this paper, we propose an eclipse operator that generalizes the classic 1NN and skyline queries and provides a more customizable query solution for users. In eclipse, users can specify rough and customizable attribute preferences and control the number of returned points. We show that both 1NN and skyline are instantiations of eclipse. To process eclipse queries, we propose a baseline algorithm with time complexity O(n22d-1), and an improved O(nlogd-1n) time transformationbased algorithm, where n is the number of points and d is the number of dimensions. Furthermore, we propose a novel index-based algorithm utilizing duality transform with much better efficiency. The experimental results on the real NBA dataset and the synthetic datasets demonstrate the effectiveness of the eclipse operator and the efficiency of our eclipse algorithms.
