曾一夫 周炎濤 周旭 蘇丹妮

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

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

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：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]，一個(gè)不被任何其他產(chǎn)品支配的產(chǎn)品被視為是Skyline產(chǎn)品，或者說在Skyline之中。Skyline產(chǎn)品是權(quán)衡各方面參數(shù)和消費(fèi)者需求之后所得出的最優(yōu)秀的產(chǎn)品。盡管Skyline查詢可以找到有吸引力的產(chǎn)品，卻很難幫助消費(fèi)者在面臨各種優(yōu)惠方式時(shí)選擇擁有最大折扣率的產(chǎn)品組合。為了處理這個(gè)問題，消費(fèi)者通常會(huì)比較所有有吸引力的產(chǎn)品組合，而不考慮實(shí)際折扣率。我們以表1為例來說明這種情況。

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

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

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

1）提出了最大優(yōu)惠的Skyline產(chǎn)品組合發(fā)現(xiàn)問題。該問題能夠返回?fù)碛凶畲笳劭勐实腟kyline產(chǎn)品組合。

2）提出了解決該問題的一個(gè)精確算法。此外，為獲得更好的運(yùn)算效率，為此設(shè)計(jì)了一個(gè)增量貪婪算法。

3）通過實(shí)驗(yàn)分析證明了所提出的算法的有效性和高效性。

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

1 相關(guān)工作

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

作為對于傳統(tǒng)Skyline的補(bǔ)充，近年內(nèi)許多學(xué)者提出和研究了很多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] 結(jié)合了概率Skyline查詢和不完整數(shù)據(jù)Skyline查詢，并給出了漸進(jìn)性的算法。

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

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

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

2.1 MPPC問題描述

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

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

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

2.3 MPPC問題的增量貪婪算法

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

3 實(shí)驗(yàn)分析

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

3.1 實(shí)驗(yàn)設(shè)置

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

參考文獻(xià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.