基于Skyline的最大優(yōu)惠產(chǎn)品組合查詢

曾一夫 周炎濤 周旭 蘇丹妮

摘 要：對于尋找有吸引力的產(chǎn)品而言，Skyline查詢是最有效的工具。然而，現(xiàn)有的Skyline算法不能有效解決面對各種折扣組合時的產(chǎn)品組合式查詢?；谶@個問題，我們首次定義并研究了最大優(yōu)惠的Skyline產(chǎn)品組合發(fā)現(xiàn)問題，這也是一個NP-hard問題。該問題著力于返回所有擁有最大折扣率的Skyline產(chǎn)品組合?？紤]到面向最有效的Skyline產(chǎn)品組合發(fā)現(xiàn)問題的實際算法并不適用于過大或者高維度的數(shù)據(jù)庫，我們設計了一種增量貪婪算法。實驗結果證明了該算法的有效性和高效性。

關鍵詞：數(shù)據(jù)管理；動態(tài)Skyline查詢；并行計算；概率產(chǎn)品

中圖分類號：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

在尋找優(yōu)秀產(chǎn)品方面，Skyline查詢是一種常用的且非常有效的方式。根據(jù)Skyline查詢的定

義[1]，一個不被任何其他產(chǎn)品支配的產(chǎn)品被視為是Skyline產(chǎn)品，或者說在Skyline之中。Skyline產(chǎn)品是權衡各方面參數(shù)和消費者需求之后所得出的最優(yōu)秀的產(chǎn)品。盡管Skyline查詢可以找到有吸引力的產(chǎn)品，卻很難幫助消費者在面臨各種優(yōu)惠方式時選擇擁有最大折扣率的產(chǎn)品組合。為了處理這個問題，消費者通常會比較所有有吸引力的產(chǎn)品組合，而不考慮實際折扣率。我們以表1為例來說明這種情況。

基于表1中給出的等級、葡萄原汁含量、價格這三個因素，找出對于消費者有吸引力的葡萄酒，Skyline查詢是一種最有效的工具?？紤]到更高等級和更高原汁含量被認為是更優(yōu)秀產(chǎn)品，w1，w2和w3均同時被w5和w6支配。w7被w5支配，w8被w6支配。因此，對表1中的數(shù)據(jù)進行Skyline查詢后，我們得到的Skyline產(chǎn)品集合是{w4，w5，w6}，這也是對消費者更有吸引力的產(chǎn)品。

如果經(jīng)銷商進行了促銷活動，比如“滿200減60”（在接下來的例子中都使用這一折扣規(guī)則），前述的Skyline選項{w4，w5，w6}將可能不再是最優(yōu)選擇。圖2展示了一些產(chǎn)品的組合方式及其折扣信息，包括原價，折扣額，折扣率等。折扣率實際等于折扣額除以原價。對于葡萄酒組合{w4，w5}，其折扣率等于[（240+190）/200] ×60=120。如果用戶選擇了葡萄酒組合{w4，w5}，則獲得的實際折扣率是120/430=0.28。類似的，也可以計算得出其他的多個葡萄酒購買組合方式獲得的實際折扣率，并展示在表2中。同時，根據(jù)表2所示，葡萄酒組合{w5，w6}具有最大的折扣率，因此被認為是消費者的最佳選擇。

基于以上分析，最大優(yōu)惠的Skyline產(chǎn)品組合發(fā)現(xiàn)問題的研究和探討是有其實際價值的。如果面臨一組待分析甄選的產(chǎn)品，在本方法的處理下，可以獲取擁有最大折扣率的Skyline產(chǎn)品組合。本文的實際貢獻如下所述：

1）提出了最大優(yōu)惠的Skyline產(chǎn)品組合發(fā)現(xiàn)問題。該問題能夠返回擁有最大折扣率的Skyline產(chǎn)品組合。

2）提出了解決該問題的一個精確算法。此外，為獲得更好的運算效率，為此設計了一個增量貪婪算法。

3）通過實驗分析證明了所提出的算法的有效性和高效性。

本文將分為四個章節(jié)。第一章分析和描述了相關工作和文獻。第二章正式提出最大優(yōu)惠的Skyline產(chǎn)品組合發(fā)現(xiàn)問題，并設計了幾個有效的算法。第三章為實驗部分，主要是分析了算法的性能和效果。第四章為總結和展望。

1 相關工作

在本章節(jié)中，主要回顧一些傳統(tǒng)的Skyline查詢算法和研究。大部分此前的研究主要集中在如何通過快速和高效地計算來獲取Skyline結果。對于確定數(shù)據(jù)的Skyline查詢算法，主要分為兩大類，分別為基于索引的Skyline算法和基于非索引的Skyline算法[2，3]。第一類包括不使用索引來組織數(shù)據(jù)庫的解決方案。正如[2]中總結的，這一類主要包括塊嵌套循環(huán)（BNL），排序過濾Skyline（SFS），排序和限制Skyline算法（SaLSa），ZSearch和基于對象的空間分區(qū)（OSP）等。OSP[4]被認為是非索引算法中效率最高的算法。另一類，即使用了索引的算法，包含建立諸如R-tree和ZB-tree等索引來加速Skyline查詢的解決方案。 這一類的代表有近鄰（NN）算法，分支和界限（BBS）算法以及ZB樹算法。 其中基于R樹的BBS算法是一種漸進式的算法，并且被認為是I/O最優(yōu)的。

作為對于傳統(tǒng)Skyline的補充，近年內(nèi)許多學者提出和研究了很多Skyline查詢的變體問題。這些變體Skyline查詢包括分布式Skyline查詢[5，11]，反Skyline查詢[2，6，7，8]，反向k-skyband及反向排序Skyline查詢[3]，子空間Skyline和top-k查詢[1]，不確定數(shù)據(jù)Skyline查詢[9，10]，不完整數(shù)據(jù)Skyline查詢[12，13]等。此外，文[14] 結合了概率Skyline查詢和不完整數(shù)據(jù)Skyline查詢，并給出了漸進性的算法。

以上這些工作為各類數(shù)據(jù)庫下Skyline查詢提供了高效的算法，然而都沒有提供基于組優(yōu)化的Skyline查詢，不能解決最大優(yōu)惠產(chǎn)品組合查詢的問題。

2 最大優(yōu)惠產(chǎn)品組合查詢問題

在本節(jié)中，首先介紹了MPPC問題。本質(zhì)上，MPPC問題是文獻[14]中介紹的子集和問題的一個特殊形式，而子集和問題在文獻[14]中已證明是一個NP難的問題。故而MPPC問題也是一個NP難問題，并且比子集和問題更為復雜。在實踐中，有必要權衡性能和結果的準確性。因此，除了一種精確的算法外，還提出了一種增量貪婪算法來提高性能。此外，為了提高算法的實用性，還對算法進行了改進，使其成為一個漸進性的算法。

2.1 MPPC問題描述

復雜度分析：在EMPPC算法的實現(xiàn)中，首先使用R-tree來索引產(chǎn)品數(shù)據(jù)集。EMPPC由三個階段組成。在第一階段（第1行），它執(zhí)行BBS算法[16]計算skyline集。假設R-tree的高度為h，訪問節(jié)點的平均訪問成本是，文[16]中的BBS節(jié)點訪問成本最多為hn。在第二階段（第2-5行），它生成所有可能的組合。根據(jù)引理3，它在這個階段的計算成本是O（2n）。在最后一個階段，它計算所有擁有最大折扣率的Skyline組合，其成本是O（n）。

根據(jù)以上的分析，EMPPC算法的總計算復雜度是O（h + 1）n + 2n）。

EMPPC算法更適用于相對小型的數(shù)據(jù)集，而對于大型數(shù)據(jù)集，其所產(chǎn)生的組合的數(shù)量可能過多，這導致指數(shù)級的復雜性不可避免的會出現(xiàn)。顯然，這是不可接受的。

2.3 MPPC問題的增量貪婪算法

由于MPPC問題是NP難問題，為了提高其處理性能，還提出了一種增量式貪婪算法，即IGMPPC。根據(jù)文[17]中提出的IG算法，提出了IGMPPC算法。在IGMPPC算法中，它通過BBS算法[16]計算了Skyline集合。然后，計算出Skyline產(chǎn)品的實際折扣率，找到最高折扣率的Skyline產(chǎn)品。IGMPSP算法的左邊部分是一個迭代的過程。在每次迭代中，它遞增地生成Skyline產(chǎn)品組合，并保存具有當前最高折扣率的組合。

3 實驗分析

這些實驗是在配備Intel[R] CoreTM I5-3330S 2.7GHz CPU（含4個核心），4GB主內(nèi)存以及Microsoft Windows 7操作系統(tǒng)的個人電腦上進行的。誠然，需要枚舉所有skylines組合的精確算法不適用于大型或高維數(shù)據(jù)集。與文[15]中的方法類似，在本節(jié)中首先進行一些實驗，將所有提出的算法應用在幾個小型合成數(shù)據(jù)集上并進行比較。上述所有提出的算法都是用C ++實現(xiàn)的，以評估它們的運行效率和有效性。具體來說，從兩個方面來評估算法的效能：（1）處理時間（PT），即對應于在獲得Skyline查詢結果時算法所花費的時間。（2）查詢結果的數(shù)量（NR），代表 MPPC返回的Skyline組合的數(shù)量。Skyline點（NS）的數(shù)量也用圖表顯示出來，以驗證PT，NR和NS之間的關系。

3.1 實驗設置

調(diào)整了文獻[1]中公開提供的數(shù)據(jù)生成器來生成實驗中使用的合成數(shù)據(jù)集。我們使用修改后的數(shù)據(jù)生成器生成了兩種類型的數(shù)據(jù)集，分別為獨立（Ind）數(shù)據(jù)集和和反相關數(shù)據(jù)集（Ant）。此外，使用高斯分布來生成每個點的價格屬性。每個數(shù)據(jù)集由4KB頁面大小的R樹索引。

在實際應用中，商家通常根據(jù)產(chǎn)品的歷史交易數(shù)據(jù)來計算最大折扣率MaxDisR。更具體地說，商家需要先設定一個可接受的最大折扣率MaxDisR后再決定自己的價格促銷策略。在此處，設定促銷策略的方式是，根據(jù)最大折扣率MaxDisR和上百次的平均價格[AveP]。這里的商品平均價格AveP的計算方式是：AveP（P） = 。如果MaxDisR等于0.30并且上百次的“平均價格”為500元，則促銷策略設置為“買500減500 × 0.30 = 150元”。

3.2 實驗結果

在本節(jié)中，首先評估幾個小型合成數(shù)據(jù)集上的MPPC問題的所有算法，然后評估IGMPPC算法在大型合成數(shù)據(jù)集上的效果。

3.2.1 小數(shù)據(jù)集性能

不可否認，由于EMPPC算法需要處理所有的Skyline組合，因此它不適用于大數(shù)據(jù)集。在實驗中，EMPPC無法高效處理Skyline查詢結果大于20的數(shù)據(jù)集。表4顯示了數(shù)據(jù)量N固定為256K的四個小型合成數(shù)據(jù)集的結果。如表4所示，每個算法的內(nèi)存消耗量（MC）和PT都受Skyline查詢結果的影響。顯然，當處理擁有大量Skyline點的數(shù)據(jù)集時，所需要的內(nèi)存（MC）和處理時間（PT）會更多。而無論如何，IGMPPC總是比EMPPC占用的內(nèi)存更少。

需要指出的是，當Skyline點的數(shù)量較少或維度較低時，EMPPC算法反而比IGMPPC算法更快，其結果也更精確。如表4所示，實驗條件為獨立數(shù)據(jù)（d = 3）、相關數(shù)據(jù)（d = 4）、反相關數(shù)據(jù)（d = 3）時，均出現(xiàn)了這種情況。而當進一步提高數(shù)據(jù)維度從而使得Skyline點更多時，IGMPPC就會具有處理時間上的優(yōu)勢。同時，其結果的精度雖較之EMPPC有所損失，但是完全在可接受范圍內(nèi)。尤其是對于大部分用戶而言，并不需要過多的推薦組合，最為優(yōu)秀的幾個結果就已經(jīng)能夠保證很好的查詢體驗。

3.2.2 大數(shù)據(jù)集性能

在本小節(jié)中，分別用不同的d和N來評估IGMPPC算法。

在不同維度d上的實驗結果。保持其他參數(shù)為默認值不變，但使d的變化范圍從3到6之間按步進1進行變化，并檢查算法的性能。表5描述了不同d下算法的效率，展示了其NS，PT和NR的數(shù)據(jù)。 顯然，隨著d的增長，NS，PT和NR都有所增加，這是因為較大的d導致更多的Skyline查詢結果，自然需要更多的時間來對其進行處理。更多的Skyline查詢結果往往會產(chǎn)生更多關于MPPC問題的結果。

在不同基數(shù)N下的實驗結果。保持其他參數(shù)為默認值不變，但使N的變化范圍從64 K到1024 K之間變化，并檢查算法的性能。算法的實驗結果見表6。不同的N對實驗結果的影響與d類似。隨著N的增加，Skyline查詢結果的數(shù)量變得更多，這也導致了PT和NR的增長。

總的說來，IGMPPC算法作為一個較為快速的算法，能夠迅速提供幾乎最優(yōu)的結果，以滿足實時交易需求。尤其是面臨較高維度和較大數(shù)據(jù)庫的查詢需求時表現(xiàn)更佳。

4 結 論

首次提出并研究了基于優(yōu)惠條件的Skyline查詢問題。提出了最大優(yōu)惠產(chǎn)品組合查詢問題，用基于產(chǎn)品組合的Skyline算法來返回擁有最大折扣率的產(chǎn)品組合。提出了精確算法來解決上述問題，并使用了一種增量貪婪算法來提高算法的效率。提出的方法不僅可以為消費端提供參考工具，亦可以為商家優(yōu)化產(chǎn)品信息做出貢獻。

參考文獻

[1] TAO Yu-fei，XIAO Xiao-kui，PEI Jian.Efficient skyline and top-k retrieval in subspaces[J].IEEE Transactions on Knowledge & Data Engineering，2007，19（8）：1072—1088.

[2] GAO Yun-jun，LIU Qing，ZHENG Bai-hua，et al.On efficient reverse skyline query processing[J].Expert Systems with Applications An International Journal，2014，41（7）：3237—3249.

[3] GAO Yun-jun，LIU Qing，ZHENG Bai-hua，et al.On processing reverse k -skyband and ranked reverse skyline queries [J]. Information Sciences，2015，293（C）：11—34.

[4] ZHANG Shi-ming，MAMOULIS N，CHEUNG D W. Scalable skyline computation using object-based space partitioning[C]// ACM.2009：483—494.

[5] ZHU Lin，TAO Yu-fei，ZHOU Shui-geng. Distributed skyline retrieval with low bandwidth consumption[J].IEEE Transactions on Knowledge & Data Engineering，2009，21（3）：384—400.

[6] EVANGELOS D， SEEGER B，Efficient computation of reverse skyline queries[C]// International Conference on Very Large Data Bases.VLDB Endowment，2007：291—302.

[7] SAIFUL，I M，ZHOU Rui，LIU Cheng-fei，On answering why-not questions in reverse skyline queries[C]//IEEE，International Conference on Data Engineering. IEEE，2013：973—984.

[8] PARK Y，MIN JK，SHIM K，Parallel computation of skyline and reverse skyline queries using mapreduce[J]. Proceedings of the Vldb Endowment，2014，6（14）：2002—2013.

[9] PEI Jian，JIANG Bin，LINXue-min，et al.Probabilistic skylines on uncertain data[C]// International Conference on Very Large Data Bases.VLDB Endowment，2007：15—26.

[10] DING Xiao-feng，JIN Hai.Efficient and progressive algorithms for distributed skyline queries over uncertain data[J].IEEE Transactions on Knowledge and Data Engineering，2012，24（8）：1448—1462.

[11] ZHOU Xu，LI Ken-li，ZHOU Yan-tao，et al.Adaptive processing for distributed skyline queries over uncertain data[J]. IEEE Transactions on Knowledge and Data Engineering，2016，28（2）： 371—384.

[12] WANG Yan，SHI Zhan，WANG Jun-lu，et al.Skyline preference query based on massive and incomplete dataset[J].IEEE Access，2017，5： 3183—3192.

[13] ALWAN A A，IBRAHIM H，UDZIR N I，et al.Processing skyline queries in incomplete distributed databases[J]. Journal of Intelligent Information Systems，2017，48（2）： 399—420.

[14] ZENG Yi-fu，LI Ken-li，YU Shui，et al.Parallel and progressive approaches for skyline query over probabilistic incomplete database[J]. IEEE ACCESS，2018，6： 13289—13301.

[15] WAN Qian，WONG R C，PENG Yu.Finding top profitable products[C]. In Data Engineering （ICDE），2011，1055—1066.

[16] DIMITRIS P，TAO Yu-fei，F(xiàn)U G，et al.Progressive skyline computation in database systems[J].ACM Transactions on Database Systems （TODS），2005，30（1）：41—82.

[17] LIN Chen-Yi，KOH JL，CHEN A L.Determining most demanding products with maximum expected number of total customers[J].IEEE Transactions on Knowledge and Data Engineering，2013，25（8）：1732—1747.

[18] YU Wen-hui，QIN Zheng，LIU Jin-fei，et al.Fast algorithms for pareto optimal group-based skyline[C].ACM，2017：417—426.