基于Skyline的最大优惠产品组合查询

Most Preferential Product Combinations Searching Based on Skyline Query

对于寻找有吸引力的产品而言,Skyline查询是最有效的工具。然而,现有的Skyline算法不能有效解决面对各种折扣组合时的产品组合式查询。基于这个问题,我们首次定义并研究了最大优惠的Skyline产品组合发现问题,这也是一个NP-hard问题。该问题着力于返回所有拥有最大折扣率的Skyline产品组合。考虑到面向最有效的Skyline产品组合发现问题的实际算法并不适用于过大或者高维度的数据库,我们设计了一种增量贪婪算法。实验结果证明了该算法的有效性和高效性。

The Skyline query, is a most useful tool to find out attractive products.However,it does little to help select the prod- uet combinations with the maximum discount rate.Motivated by this,we identify- an interesting problem,a most preferential product combinations （MPPC） searching problem, which is NP-hard, for the first time in the literature.This problem aims to report all sky- line product combinations having the maximum discount rate.Since the exact algorithm for the MPPC is not scalable to large or high-dimensional datasets,we design an incremental greedy algorithm.The experiment resuhs demonstrate the efficiency and effectiveness of the proposed algorithm.