论文部分内容阅读
摘 要：对于寻找有吸引力的产品而言，Skyline查询是最有效的工具。然而，现有的Skyline算法不能有效解决面对各种折扣组合时的产品组合式查询。基于这个问题，我们首次定义并研究了最大优惠的Skyline产品组合发现问题，这也是一个NP-hard问题。该问题着力于返回所有拥有最大折扣率的Skyline产品组合。考虑到面向最有效的Skyline产品组合发现问题的实际算法并不适用于过大或者高维度的数据库，我们设计了一种增量贪婪算法。实验结果证明了该算法的有效性和高效性。
关键词：数据管理；动态Skyline查询；并行计算；概率产品
中图分类号：TP301.6 文献标识码：A
Abstract： The Skyline query is a most useful tool to find out attractive products.However，it does little to help select the product 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 skyline 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 results demonstrate the efficiency and effectiveness of the proposed algorithm.
Key words： data management；dynamic skyline query；parallel algorithm；probabilistic products
在寻找优秀产品方面，Skyline查询是一种常用的且非常有效的方式。根据Skyline查询的定
义[1]，一个不被任何其他产品支配的产品被视为是Skyline产品，或者说在Skyline之中。Skyline产品是权衡各方面参数和消费者需求之后所得出的最优秀的产品。尽管Skyline查询可以找到有吸引力的产品，却很难帮助消费者在面临各种优惠方式时选择拥有最大折扣率的产品组合。为了处理这个问题，消费者通常会比较所有有吸引力的产品组合，而不考虑实际折扣率。我们以表1为例来说明这种情况。
基于表1中给出的等级、葡萄原汁含量、价格这三个因素，找出对于消费者有吸引力的葡萄酒，Skyline查询是一种最有效的工具。考虑到更高等级和更高原汁含量被认为是更优秀产品，w1，w2和w3均同时被w5和w6支配。w7被w5支配，w8被w6支配。因此，对表1中的数据进行Skyline查询后，我们得到的Skyline产品集合是{w4，w5，w6}，这也是对消费者更有吸引力的产品。
如果经销商进行了促销活动，比如“满200减60”（在接下来的例子中都使用这一折扣规则），前述的Skyline选项{w4，w5，w6}将可能不再是最优选择。图2展示了一些产品的组合方式及其折扣信息，包括原价，折扣额，折扣率等。折扣率实际等于折扣额除以原价。对于葡萄酒组合{w4，w5}，其折扣率等于[（240 190）/200] ×60=120。如果用户选择了葡萄酒组合{w4，w5}，则获得的实际折扣率是120/430=0.28。类似的，也可以计算得出其他的多个葡萄酒购买组合方式获得的实际折扣率，并展示在表2中。同时，根据表2所示，葡萄酒组合{w5，w6}具有最大的折扣率，因此被认为是消费者的最佳选择。
基于以上分析，最大优惠的Skyline产品组合发现问题的研究和探讨是有其实际价值的。如果面临一组待分析甄选的产品，在本方法的处理下，可以获取拥有最大折扣率的Skyline产品组合。本文的实际贡献如下所述：
1）提出了最大优惠的Skyline产品组合发现问题。该问题能够返回拥有最大折扣率的Skyline产品组合。
2）提出了解决该问题的一个精确算法。此外，为获得更好的运算效率，为此设计了一个增量贪婪算法。
3）通过实验分析证明了所提出的算法的有效性和高效性。
本文将分为四个章节。第一章分析和描述了相关工作和文献。第二章正式提出最大优惠的Skyline产品组合发现问题，并设计了几个有效的算法。第三章为实验部分，主要是分析了算法的性能和效果。第四章为总结和展望。
1 相关工作
在本章节中，主要回顾一些传统的Skyline查询算法和研究。大部分此前的研究主要集中在如何通过快速和高效地计算来获取Skyline结果。对于确定数据的Skyline查询算法，主要分为两大类，分别为基于索引的Skyline算法和基于非索引的Skyline算法[2，3]。第一类包括不使用索引来组织数据库的解决方案。正如[2]中总结的，这一类主要包括块嵌套循环（BNL），排序过滤Skyline（SFS），排序和限制Skyline算法（SaLSa），ZSearch和基于對象的空间分区（OSP）等。OSP[4]被认为是非索引算法中效率最高的算法。另一类，即使用了索引的算法，包含建立诸如R-tree和ZB-tree等索引来加速Skyline查询的解决方案。 这一类的代表有近邻（NN）算法，分支和界限（BBS）算法以及ZB树算法。 其中基于R树的BBS算法是一种渐进式的算法，并且被认为是I/O最优的。 作为对于传统Skyline的补充，近年内许多学者提出和研究了很多Skyline查询的变体问题。这些变体Skyline查询包括分布式Skyline查询[5，11]，反Skyline查询[2，6，7，8]，反向k-skyband及反向排序Skyline查询[3]，子空间Skyline和top-k查询[1]，不确定数据Skyline查询[9，10]，不完整数据Skyline查询[12，13]等。此外，文[14] 结合了概率Skyline查询和不完整数据Skyline查询，并给出了渐进性的算法。
以上这些工作为各类数据库下Skyline查询提供了高效的算法，然而都没有提供基于组优化的Skyline查询，不能解决最大优惠产品组合查询的问题。
2 最大优惠产品组合查询问题
在本节中，首先介绍了MPPC问题。本质上，MPPC问题是文献[14]中介绍的子集和问题的一个特殊形式，而子集和问题在文献[14]中已证明是一个NP难的问题。故而MPPC问题也是一个NP难问题，并且比子集和问题更为复杂。在实践中，有必要权衡性能和结果的准确性。因此，除了一种精确的算法外，还提出了一种增量贪婪算法来提高性能。此外，为了提高算法的实用性，还对算法进行了改进，使其成为一个渐进性的算法。
2.1 MPPC问题描述
复杂度分析：在EMPPC算法的实现中，首先使用R-tree来索引产品数据集。EMPPC由三个阶段组成。在第一阶段（第1行），它执行BBS算法[16]计算skyline集。假设R-tree的高度为h，访问节点的平均访问成本是，文[16]中的BBS节点访问成本最多为hn。在第二阶段（第2-5行），它生成所有可能的组合。根据引理3，它在这个阶段的计算成本是O（2n）。在最后一个阶段，它计算所有拥有最大折扣率的Skyline组合，其成本是O（n）。
根据以上的分析，EMPPC算法的总计算复杂度是O（h 1）n 2n）。
EMPPC算法更适用于相对小型的数据集，而对于大型数据集，其所產生的组合的数量可能过多，这导致指数级的复杂性不可避免的会出现。显然，这是不可接受的。
2.3 MPPC问题的增量贪婪算法
由于MPPC问题是NP难问题，为了提高其处理性能，还提出了一种增量式贪婪算法，即IGMPPC。根据文[17]中提出的IG算法，提出了IGMPPC算法。在IGMPPC算法中，它通过BBS算法[16]计算了Skyline集合。然后，计算出Skyline产品的实际折扣率，找到最高折扣率的Skyline产品。IGMPSP算法的左边部分是一个迭代的过程。在每次迭代中，它递增地生成Skyline产品组合，并保存具有当前最高折扣率的组合。
3 实验分析
这些实验是在配备Intel[R] CoreTM I5-3330S 2.7GHz CPU（含4个核心），4GB主内存以及Microsoft Windows 7操作系统的个人电脑上进行的。诚然，需要枚举所有skylines组合的精确算法不适用于大型或高维数据集。与文[15]中的方法类似，在本节中首先进行一些实验，将所有提出的算法应用在几个小型合成数据集上并进行比较。上述所有提出的算法都是用C 实现的，以评估它们的运行效率和有效性。具体来说，从两个方面来评估算法的效能：（1）处理时间（PT），即对应于在获得Skyline查询结果时算法所花费的时间。（2）查询结果的数量（NR），代表 MPPC返回的Skyline组合的数量。Skyline点（NS）的数量也用图表显示出来，以验证PT，NR和NS之间的关系。
3.1 实验设置
调整了文献[1]中公开提供的数据生成器来生成实验中使用的合成数据集。我们使用修改后的数据生成器生成了两种类型的数据集，分别为独立（Ind）数据集和和反相关数据集（Ant）。此外，使用高斯分布来生成每个点的价格属性。每个数据集由4KB页面大小的R树索引。
在实际应用中，商家通常根据产品的历史交易数据来计算最大折扣率MaxDisR。更具体地说，商家需要先设定一个可接受的最大折扣率MaxDisR后再决定自己的价格促销策略。在此处，设定促销策略的方式是，根据最大折扣率MaxDisR和上百次的平均价格[AveP]。这里的商品平均价格AveP的计算方式是：AveP（P） = 。如果MaxDisR等于0.30并且上百次的“平均价格”为500元，则促销策略设置为“买500减500 × 0.30 = 150元”。
3.2 实验结果
在本节中，首先评估几个小型合成数据集上的MPPC问题的所有算法，然后评估IGMPPC算法在大型合成数据集上的效果。
3.2.1 小数据集性能
不可否认，由于EMPPC算法需要处理所有的Skyline组合，因此它不适用于大数据集。在实验中，EMPPC无法高效处理Skyline查询结果大于20的数据集。表4显示了数据量N固定为256K的四个小型合成数据集的结果。如表4所示，每个算法的内存消耗量（MC）和PT都受Skyline查询结果的影响。显然，当处理拥有大量Skyline点的数据集时，所需要的内存（MC）和处理时间（PT）会更多。而无论如何，IGMPPC总是比EMPPC占用的内存更少。
需要指出的是，当Skyline点的数量较少或维度较低时，EMPPC算法反而比IGMPPC算法更快，其结果也更精确。如表4所示，实验条件为独立数据（d = 3）、相关数据（d = 4）、反相关数据（d = 3）时，均出现了这种情况。而当进一步提高数据维度从而使得Skyline点更多时，IGMPPC就会具有处理时间上的优势。同时，其结果的精度虽较之EMPPC有所损失，但是完全在可接受范围内。尤其是对于大部分用户而言，并不需要过多的推荐组合，最为优秀的几个结果就已经能够保证很好的查询体验。 3.2.2 大數据集性能
在本小节中，分别用不同的d和N来评估IGMPPC算法。
在不同维度d上的实验结果。保持其他参数为默认值不变，但使d的变化范围从3到6之间按步进1进行变化，并检查算法的性能。表5描述了不同d下算法的效率，展示了其NS，PT和NR的数据。 显然，随着d的增长，NS，PT和NR都有所增加，这是因为较大的d导致更多的Skyline查询结果，自然需要更多的时间来对其进行处理。更多的Skyline查询结果往往会产生更多关于MPPC问题的结果。
在不同基数N下的实验结果。保持其他参数为默认值不变，但使N的变化范围从64 K到1024 K之间变化，并检查算法的性能。算法的实验结果见表6。不同的N对实验结果的影响与d类似。随着N的增加，Skyline查询结果的数量变得更多，这也导致了PT和NR的增长。
总的说来，IGMPPC算法作为一个较为快速的算法，能够迅速提供几乎最优的结果，以满足实时交易需求。尤其是面临较高维度和较大数据库的查询需求时表现更佳。
4 结 论
首次提出并研究了基于优惠条件的Skyline查询问题。提出了最大优惠产品组合查询问题，用基于产品组合的Skyline算法来返回拥有最大折扣率的产品组合。提出了精确算法来解决上述问题，并使用了一种增量贪婪算法来提高算法的效率。提出的方法不仅可以为消费端提供参考工具，亦可以为商家优化产品信息做出贡献。
参考文献
[1] TAO Yu-fei，XIAO Xiao-kui，PEI Jian.Efficient skyline and top-k retrieval in subspaces[J].IEEE Transactions on Knowledge
关键词：数据管理；动态Skyline查询；并行计算；概率产品
中图分类号：TP301.6 文献标识码：A
Abstract： The Skyline query is a most useful tool to find out attractive products.However，it does little to help select the product 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 skyline 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 results demonstrate the efficiency and effectiveness of the proposed algorithm.
Key words： data management；dynamic skyline query；parallel algorithm；probabilistic products
在寻找优秀产品方面，Skyline查询是一种常用的且非常有效的方式。根据Skyline查询的定
义[1]，一个不被任何其他产品支配的产品被视为是Skyline产品，或者说在Skyline之中。Skyline产品是权衡各方面参数和消费者需求之后所得出的最优秀的产品。尽管Skyline查询可以找到有吸引力的产品，却很难帮助消费者在面临各种优惠方式时选择拥有最大折扣率的产品组合。为了处理这个问题，消费者通常会比较所有有吸引力的产品组合，而不考虑实际折扣率。我们以表1为例来说明这种情况。
基于表1中给出的等级、葡萄原汁含量、价格这三个因素，找出对于消费者有吸引力的葡萄酒，Skyline查询是一种最有效的工具。考虑到更高等级和更高原汁含量被认为是更优秀产品，w1，w2和w3均同时被w5和w6支配。w7被w5支配，w8被w6支配。因此，对表1中的数据进行Skyline查询后，我们得到的Skyline产品集合是{w4，w5，w6}，这也是对消费者更有吸引力的产品。
如果经销商进行了促销活动，比如“满200减60”（在接下来的例子中都使用这一折扣规则），前述的Skyline选项{w4，w5，w6}将可能不再是最优选择。图2展示了一些产品的组合方式及其折扣信息，包括原价，折扣额，折扣率等。折扣率实际等于折扣额除以原价。对于葡萄酒组合{w4，w5}，其折扣率等于[（240 190）/200] ×60=120。如果用户选择了葡萄酒组合{w4，w5}，则获得的实际折扣率是120/430=0.28。类似的，也可以计算得出其他的多个葡萄酒购买组合方式获得的实际折扣率，并展示在表2中。同时，根据表2所示，葡萄酒组合{w5，w6}具有最大的折扣率，因此被认为是消费者的最佳选择。
基于以上分析，最大优惠的Skyline产品组合发现问题的研究和探讨是有其实际价值的。如果面临一组待分析甄选的产品，在本方法的处理下，可以获取拥有最大折扣率的Skyline产品组合。本文的实际贡献如下所述：
1）提出了最大优惠的Skyline产品组合发现问题。该问题能够返回拥有最大折扣率的Skyline产品组合。
2）提出了解决该问题的一个精确算法。此外，为获得更好的运算效率，为此设计了一个增量贪婪算法。
3）通过实验分析证明了所提出的算法的有效性和高效性。
本文将分为四个章节。第一章分析和描述了相关工作和文献。第二章正式提出最大优惠的Skyline产品组合发现问题，并设计了几个有效的算法。第三章为实验部分，主要是分析了算法的性能和效果。第四章为总结和展望。
1 相关工作
在本章节中，主要回顾一些传统的Skyline查询算法和研究。大部分此前的研究主要集中在如何通过快速和高效地计算来获取Skyline结果。对于确定数据的Skyline查询算法，主要分为两大类，分别为基于索引的Skyline算法和基于非索引的Skyline算法[2，3]。第一类包括不使用索引来组织数据库的解决方案。正如[2]中总结的，这一类主要包括块嵌套循环（BNL），排序过滤Skyline（SFS），排序和限制Skyline算法（SaLSa），ZSearch和基于對象的空间分区（OSP）等。OSP[4]被认为是非索引算法中效率最高的算法。另一类，即使用了索引的算法，包含建立诸如R-tree和ZB-tree等索引来加速Skyline查询的解决方案。 这一类的代表有近邻（NN）算法，分支和界限（BBS）算法以及ZB树算法。 其中基于R树的BBS算法是一种渐进式的算法，并且被认为是I/O最优的。 作为对于传统Skyline的补充，近年内许多学者提出和研究了很多Skyline查询的变体问题。这些变体Skyline查询包括分布式Skyline查询[5，11]，反Skyline查询[2，6，7，8]，反向k-skyband及反向排序Skyline查询[3]，子空间Skyline和top-k查询[1]，不确定数据Skyline查询[9，10]，不完整数据Skyline查询[12，13]等。此外，文[14] 结合了概率Skyline查询和不完整数据Skyline查询，并给出了渐进性的算法。
以上这些工作为各类数据库下Skyline查询提供了高效的算法，然而都没有提供基于组优化的Skyline查询，不能解决最大优惠产品组合查询的问题。
2 最大优惠产品组合查询问题
在本节中，首先介绍了MPPC问题。本质上，MPPC问题是文献[14]中介绍的子集和问题的一个特殊形式，而子集和问题在文献[14]中已证明是一个NP难的问题。故而MPPC问题也是一个NP难问题，并且比子集和问题更为复杂。在实践中，有必要权衡性能和结果的准确性。因此，除了一种精确的算法外，还提出了一种增量贪婪算法来提高性能。此外，为了提高算法的实用性，还对算法进行了改进，使其成为一个渐进性的算法。
2.1 MPPC问题描述
复杂度分析：在EMPPC算法的实现中，首先使用R-tree来索引产品数据集。EMPPC由三个阶段组成。在第一阶段（第1行），它执行BBS算法[16]计算skyline集。假设R-tree的高度为h，访问节点的平均访问成本是，文[16]中的BBS节点访问成本最多为hn。在第二阶段（第2-5行），它生成所有可能的组合。根据引理3，它在这个阶段的计算成本是O（2n）。在最后一个阶段，它计算所有拥有最大折扣率的Skyline组合，其成本是O（n）。
根据以上的分析，EMPPC算法的总计算复杂度是O（h 1）n 2n）。
EMPPC算法更适用于相对小型的数据集，而对于大型数据集，其所產生的组合的数量可能过多，这导致指数级的复杂性不可避免的会出现。显然，这是不可接受的。
2.3 MPPC问题的增量贪婪算法
由于MPPC问题是NP难问题，为了提高其处理性能，还提出了一种增量式贪婪算法，即IGMPPC。根据文[17]中提出的IG算法，提出了IGMPPC算法。在IGMPPC算法中，它通过BBS算法[16]计算了Skyline集合。然后，计算出Skyline产品的实际折扣率，找到最高折扣率的Skyline产品。IGMPSP算法的左边部分是一个迭代的过程。在每次迭代中，它递增地生成Skyline产品组合，并保存具有当前最高折扣率的组合。
3 实验分析
这些实验是在配备Intel[R] CoreTM I5-3330S 2.7GHz CPU（含4个核心），4GB主内存以及Microsoft Windows 7操作系统的个人电脑上进行的。诚然，需要枚举所有skylines组合的精确算法不适用于大型或高维数据集。与文[15]中的方法类似，在本节中首先进行一些实验，将所有提出的算法应用在几个小型合成数据集上并进行比较。上述所有提出的算法都是用C 实现的，以评估它们的运行效率和有效性。具体来说，从两个方面来评估算法的效能：（1）处理时间（PT），即对应于在获得Skyline查询结果时算法所花费的时间。（2）查询结果的数量（NR），代表 MPPC返回的Skyline组合的数量。Skyline点（NS）的数量也用图表显示出来，以验证PT，NR和NS之间的关系。
3.1 实验设置
调整了文献[1]中公开提供的数据生成器来生成实验中使用的合成数据集。我们使用修改后的数据生成器生成了两种类型的数据集，分别为独立（Ind）数据集和和反相关数据集（Ant）。此外，使用高斯分布来生成每个点的价格属性。每个数据集由4KB页面大小的R树索引。
在实际应用中，商家通常根据产品的历史交易数据来计算最大折扣率MaxDisR。更具体地说，商家需要先设定一个可接受的最大折扣率MaxDisR后再决定自己的价格促销策略。在此处，设定促销策略的方式是，根据最大折扣率MaxDisR和上百次的平均价格[AveP]。这里的商品平均价格AveP的计算方式是：AveP（P） = 。如果MaxDisR等于0.30并且上百次的“平均价格”为500元，则促销策略设置为“买500减500 × 0.30 = 150元”。
3.2 实验结果
在本节中，首先评估几个小型合成数据集上的MPPC问题的所有算法，然后评估IGMPPC算法在大型合成数据集上的效果。
3.2.1 小数据集性能
不可否认，由于EMPPC算法需要处理所有的Skyline组合，因此它不适用于大数据集。在实验中，EMPPC无法高效处理Skyline查询结果大于20的数据集。表4显示了数据量N固定为256K的四个小型合成数据集的结果。如表4所示，每个算法的内存消耗量（MC）和PT都受Skyline查询结果的影响。显然，当处理拥有大量Skyline点的数据集时，所需要的内存（MC）和处理时间（PT）会更多。而无论如何，IGMPPC总是比EMPPC占用的内存更少。
需要指出的是，当Skyline点的数量较少或维度较低时，EMPPC算法反而比IGMPPC算法更快，其结果也更精确。如表4所示，实验条件为独立数据（d = 3）、相关数据（d = 4）、反相关数据（d = 3）时，均出现了这种情况。而当进一步提高数据维度从而使得Skyline点更多时，IGMPPC就会具有处理时间上的优势。同时，其结果的精度虽较之EMPPC有所损失，但是完全在可接受范围内。尤其是对于大部分用户而言，并不需要过多的推荐组合，最为优秀的几个结果就已经能够保证很好的查询体验。 3.2.2 大數据集性能
在本小节中，分别用不同的d和N来评估IGMPPC算法。
在不同维度d上的实验结果。保持其他参数为默认值不变，但使d的变化范围从3到6之间按步进1进行变化，并检查算法的性能。表5描述了不同d下算法的效率，展示了其NS，PT和NR的数据。 显然，随着d的增长，NS，PT和NR都有所增加，这是因为较大的d导致更多的Skyline查询结果，自然需要更多的时间来对其进行处理。更多的Skyline查询结果往往会产生更多关于MPPC问题的结果。
在不同基数N下的实验结果。保持其他参数为默认值不变，但使N的变化范围从64 K到1024 K之间变化，并检查算法的性能。算法的实验结果见表6。不同的N对实验结果的影响与d类似。随着N的增加，Skyline查询结果的数量变得更多，这也导致了PT和NR的增长。
总的说来，IGMPPC算法作为一个较为快速的算法，能够迅速提供几乎最优的结果，以满足实时交易需求。尤其是面临较高维度和较大数据库的查询需求时表现更佳。
4 结 论
首次提出并研究了基于优惠条件的Skyline查询问题。提出了最大优惠产品组合查询问题，用基于产品组合的Skyline算法来返回拥有最大折扣率的产品组合。提出了精确算法来解决上述问题，并使用了一种增量贪婪算法来提高算法的效率。提出的方法不仅可以为消费端提供参考工具，亦可以为商家优化产品信息做出贡献。
参考文献
[1] TAO Yu-fei，XIAO Xiao-kui，PEI Jian.Efficient skyline and top-k retrieval in subspaces[J].IEEE Transactions on Knowledge