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

Most Preferential Product Combinations Searching Based on Skyline Query

作　　者：曾一夫 周炎涛[1] 周旭 苏丹妮 ZENG Yi-fu;ZHOU Yan-tao;ZHOU Xu;SU Dan-ni(College of Electrical and Information Engineering,Hunan University,Changsha,Hunan 410082,China;College of Information Science and Engineering,Hunan University,Changsha,Hunan 410082,China)

机构地区：[1]湖南大学电气与信息工程学院,湖南长沙410082 [2]湖南大学信息科学与工程学院,湖南长沙410082

出　　处：《计算技术与自动化》2018年第3期155-160,共6页Computing Technology and Automation

基　　金：国家自然科学基金资助项目(61472126)

摘　　要：对于寻找有吸引力的产品而言,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.

关 键 词：数据管理 动态Skyline查询 并行计算 概率产品 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]