Efficient Processing of k-regret Queries via Skyline Frequency

摘要

Helping end-users to find the most desired points in the database is an important task for database systems to support multi-criteria decision making. The recent proposed k-regret query doesn't ask for elaborate information and can output k points for users easily to choose. However, most existing algorithms for k-regret query suffer from a heavy burden by taking the numerous skyline points as candidate set. In this paper, we aim at decreasing the candidate points from skyline points to a relative small subset of skyline points, called frequent skyline points, so that the k-regret algorithms can be applied efficiently on the smaller candidate set to improve their efficiency. A useful metric based on subspace skyline called skyline frequency is adopted to help determine the candidate set and corresponding algorithm is developed. Experiments on synthetic and real datasets show the efficiency and effectiveness of our proposed method.