Abstract
Recently, many approaches on solving the skyline problems have been proposed. From the perspective of marketing, the domination concept is conducive to choose the competitive products. A product provider may want to know which uncompetitive products can be upgraded to gain much more potential customers under a limited budget. In this paper, we make the first attempt to address a new problem on upgrading uncompetitive products to maximize the number of potential customers, which returns a set of products that are not dominated by any existing products and maximize the number of potential customers. Given two data sets A and P, the former represents a set of competitive products while the latter represents a set of uncompetitive products waiting for being upgraded, and a limited budget of M, we return some products in P that are upgraded to avoid being dominated by any products in A under the condition of M and these products can maximize the number of potential customers. We propose an approximate algorithm based on an interesting index structure to group together the similar products and prune the other products that may cost too much. A series of experiments on a real dataset and three synthetic datasets are performed. The experiment results show that the approximate method is more efficient than a basic method and also has a good accurate rate.