Efficient computation of combinatorial skyline queries

Current skyline evaluation techniques are mainly to find the outstanding tuples from a large dataset. In this paper, we generalize the concept of skyline query and introduce a novel type of query, the combinatorial skyline query, which is to find the outstanding combinations from all combinations of the given tuples. The past skyline query is a special case of the combinatorial skyline query. This generalized concept is semantically more abundant when used in decision making, market analysis, business planning, and quantitative economics research. In this paper, we first introduce the concept of the combinatorial skyline query (CSQ) and explain the difficulty in resolving this type of query. Then, we propose two algorithms to solve the problem. The experiments manifest the effectiveness and efficiency of the proposed algorithms.

► A novel type of the skyline query, called the combinatorial skyline query (CSQ), is proposed. ► CSQ is a more general form of the regular skyline query. ►Efficient algorithms are proposed for processing CSQ. ► The correctness of the proposed algorithms is proved.