基于Skyline的最大優惠產品組合查詢

曾一夫 周炎濤 周旭 蘇丹妮

摘 要：對于尋找有吸引力的產品而言，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 & 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，FU 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.