Upgrading Uncompetitive Products Economically

Hua Lu, Christian S. Jensen

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review


The skyline of a multidimensional point set consists of the points that are not dominated by other points. In a scenario where product features are represented by multidimensional points, the skyline points may be viewed as representing competitive products. A product provider may wish to upgrade uncompetitive products to become competitive, but wants to take into account the upgrading cost. We study the top-k product upgrading problem. Given a set P of competitor products, a set T of products that are candidates for upgrade, and an upgrading cost function f that applies to T, the problem is to return the k products in T that can be upgraded to not be dominated by any products in P at the lowest cost. This problem is non-trivial due to not only the large data set sizes, but also to the many possibilities for upgrading a product. We identify and provide solutions for the different options for upgrading an uncompetitive product, and combine the solutions into a single solution. We also propose a spatial join-based solution that assumes P and T are indexed by an R-tree. Given a set of products in the same R-tree node, we derive three lower bounds on their upgrading costs. These bounds are employed by the join approach to prune upgrade candidates with uncompetitive upgrade costs. Empirical studies with synthetic and real data show that the join approach is efficient and scalable
TitelIEEE 28th International Conference on Data Engineering (ICDE 2012), Washington, DC, USA (Arlington, Virginia), 1-5 April, 2012
RedaktørerAnastasios Kementsietsidis, Marcos Antonio Vaz Salles
Antal sider12
ForlagIEEE Computer Society Press
ISBN (Trykt)978-0-7685-4747-3
StatusUdgivet - 2012
Udgivet eksterntJa
Begivenhed28th IEEE International Conference on Data Engineering - Washington, USA
Varighed: 1 apr. 20125 apr. 2012
Konferencens nummer: 28


Konference28th IEEE International Conference on Data Engineering

Citer dette