黃震華張 波

①（同濟大學電子與信息工程學院 上海 201804）

②（同濟大學嵌入式系統(tǒng)與服務計算國家教育部重點實驗室 上海 201804）

③（上海師范大學信息與機電工程學院 上海 200234）

一種分布式網絡中輪廓推薦的有效方法

黃震華*①②張 波③

①（同濟大學電子與信息工程學院 上海 201804）

②（同濟大學嵌入式系統(tǒng)與服務計算國家教育部重點實驗室 上海 201804）

③（上海師范大學信息與機電工程學院 上海 200234）

當底層數據的容量以及輪廓推薦指令個數增大時，輪廓推薦的時間代價將呈指數級增長，從而嚴重影響其推薦效率。為此，基于超對等分布式網絡（SPA），該文提出預存儲w個輪廓快照來高效處理系統(tǒng)中u個輪廓推薦指令的分布式網絡輪廓推薦算法（EMSRDN）。EMSRDN算法充分考慮SPA網絡的數據存儲和通信特性，利用map/reduce分布式計算模型，通過初始快照集啟發(fā)式構造來快速產生最優(yōu)w個輪廓快照。理論分析和仿真實驗表明，該算法具有有效性和實用性。

分布式網絡；輪廓推薦；Map/reduce分布式計算；信息服務

1 引言

輪廓推薦技術是近年來信息服務方向的一個研究重點和熱點［1］，這主要是因為它在許多領域有著廣泛的應用，如：大數據分析、城市導航系統(tǒng)、多標準決策支持以及高維數據可視化等［2］。給定對象集合R=｛o1，o2，…，on｝，其中每個對象oi（i∈［0，n］）具有δ個維度F=｛d1，d2，，dδ…｝，每個維度衡量它的一個子特征（比如距離，價格等），那么維度空間U F?上的輪廓推薦就是在R中找出一類對象集合R'，它滿足如下條件：?R R'且R'中每個對象不會在U所有維度上的取值均差于R中的某一對象。顯然，通過輪廓推薦，用戶只需考慮屬于輪廓對象集合的對象，而不必關心那些被過濾掉的對象，這樣用戶就可以在小規(guī)模的輪廓對象集合上對自己感興趣的對象進行選擇。不難看出，δ個維度的對象集合，最多擁有2 1δ-個維度空間上的輪廓推薦。

隨著分布式網絡的深入應用，文獻［8］首次考慮在超對等架構（Super Peer Architecture， SPA）［9］的分布式網絡中實施輪廓推薦技術，并通過傳輸擴展輪廓對象集合來降低數據傳輸的代價。SPA架構是目前使用較廣的一種分布式網絡，因為傳統(tǒng)客戶/服務（Client/Server， C/S）模型的網絡架構能夠方便地升級為SPA架構的分布式網絡。文獻［10］在文獻［9］的基礎上，增加了多維路由索引機制（Multidimensional Routing Indices， MRI）來降低參與輪廓推薦的網絡節(jié)點數量，從而進一步降低數據傳輸的代價。文獻［11］在識別文獻［8，9］性能缺陷的基礎上，提出了有效預處理分布式網絡中子空間輪廓推薦的有效方法（Efficient Preprocessing of Subspace Sky line Queries in Distributed Networks，EPSSQDN）。EPSSQDN算法基于布隆過濾器（Bloom Filter， BF）技術［11］來縮減數據傳輸代價；同時基于正規(guī)格結構［12］來索引網絡節(jié)點上的數據對象，并且使用格間的支配關系來有效降低數據對象間的比較次數，從而提高輪廓推薦的計算效率。文獻［13］基于非共享策略，圍繞降低網絡反應延遲與通信負荷的目標，提出了一種兩階段分布式算法（Two-Phase Distributed A lgorithm， TPDA），并對算法的關鍵實現環(huán)節(jié)，如協(xié)調-遠程節(jié)點間的通信、輪廓推薦增量的計算等進行優(yōu)化，使算法在通信負荷與反應延遲上達到較好的綜合性能。

2 問題描述

3 EMSRDN算法

本文發(fā)現，從候選的γ個輪廓快照中精確挑選最優(yōu)的w（γ＞w）個輪廓快照，需要遍歷指數級個數的輪廓快照組合空間，從而使得獲取精確最優(yōu)w個輪廓快照是非多項式困難（NP-hard）問題。因此在本節(jié)中，將提出一種快速獲取近似最優(yōu)方案ASN的有效算法EMSRDN。

EMSRDN算法的核心思想是利用map/reduce分布式計算模型，通過初始輪廓快照集啟發(fā)式構造以及基于遺傳算法的輪廓快照集深度優(yōu)化這兩個階段來快速產生最優(yōu)的w個輪廓快照，其偽代碼如表1所示。

map函數和reduce函數具體實施過程如表2和表4所示。

OPTIM IZATION的具體實施過程如表3。

4 實驗評估

這一節(jié)通過具體的實驗來評估本文EMSRDN算法的優(yōu)化率和運行時間。

表1 EMSRDN算法

表2 map函數

表3 OPTIM IZATION實施過程

4.1 實驗環(huán)境設置

本文的實驗環(huán)境由30臺PC機組成3層SPA分布式網絡架構，每臺PC機的配置為4核i5-3450 CPU， 4 G內存和500 G硬盤，操作系統(tǒng)為CentOS Linux 6.4。計算節(jié)點包含10臺PC機組成的集群，其中1臺PC機選為控制計算機（Master），這10臺PC機構成Hadoop平臺，其版本號為1.0.3。而其余兩層為20個分布式存儲節(jié)點，共分配20臺PC機。實驗中，本文在計算節(jié)點上產生200個輪廓推薦指令，在每個存儲節(jié)點上產生100個輪廓快照，總計2000個候選輪廓快照。

表4 reduce函數

與EMSRDN比較的方法是OPTIMAL算法，通過指數級時間復雜度的窮舉來獲取精確最優(yōu)的輪廓快照集合；每一類實驗分為2組：（1）固定計算節(jié)點上輪廓推薦指令的個數為100，而每個存儲節(jié)點上輪廓快照的個數在20～100間變化；（2）固定每個存儲節(jié)點上輪廓快照的個數為50，而計算節(jié)點上輪廓推薦指令的個數在40～200間變化。所有算法的代碼編譯采用JDK 1.6。

4.2 EMSRDN算法的優(yōu)化率評估

本小節(jié)通過實驗評估EMSRDN算法的優(yōu)化率。圖1（a）和圖1（b）分別給出這兩個算法分別在兩組實驗中優(yōu)化率的評估結果。

在圖1評估算法優(yōu)化率的實驗中，本文以最優(yōu)算法（OPTIMAL）為基準，因為它獲取的輪廓快照集合是精確最優(yōu)的，即將該精確輪廓快照集合的優(yōu)化率定為100%。我們從圖1可以看出，EMSRDN算法的優(yōu)化率接近于最優(yōu)算法。例如在圖1（a）中，當每個存儲節(jié)點上的輪廓快照數等于100時，EMSRDN算法的優(yōu)化率為37.5%；在圖1（b）中，當計算節(jié)點上輪廓推薦指令數等于80時，EMSRDN算法的優(yōu)化率為68.3%。

4.3 EMSRDN算法的運行時間評估

本小節(jié)通過實驗評估EMSRDN算法的運行時間。圖2（a）和圖2（b）分別給出這兩個算法分別在兩組實驗中優(yōu)化率的評估結果。

雖然在圖1中，最優(yōu)算法獲取的輪廓快照集合的優(yōu)化率略高于EMSRDN算法，然而在圖2（a）和圖2（b）評估算法運行時間的實驗中，我們可以發(fā)現最優(yōu)算法在每種實驗環(huán)境下的運行時間都是非常巨大，這主要是因為最優(yōu)算法為了獲取精確的輪廓快照集合，需要遍歷所有可能的輪廓快照組合空間，因此需要指數級的時間開銷，而EMSRDN算法只需要多項式時間開銷即可返回近似最優(yōu)的輪廓快照集合，而無需遍歷所有可能的輪廓快照組合空間。例如在圖2（a）中，當每個存儲節(jié)點上的輪廓快照數等于100時，最優(yōu)算法的運行時間為79824.6 s，而算法EMSRDN的運行時間僅為35.9 s；在圖2（b）中，當計算節(jié)點上輪廓推薦指令數等于200時，最優(yōu)算法的運行時間為49652.5 s，而算法EMSRDN的運行時間僅為20.4 s。

因此，綜合圖1和圖2的實驗評估，可以得出本文的EMSRDN算法能夠很好平衡輪廓快照集合的優(yōu)化率與運行時間，而且具有很好的可擴展性。

4.4 SPA分布式網絡中的輪廓推薦代價評估

目前常用的SPA分布式網絡中輪廓推薦的算法有兩個，即EPSSQDN［11］和TPDA［13］。因此，在這一小節(jié)中，通過實驗來對比本文EMSRDN算法與EPSSQDN， TPDA算法的時間代價?；A數據庫由文獻［3］的數據生成器產生，包含1×106個對象，每個對象具有5個浮點型屬性。輪廓指令個數固定為100。實驗分為兩組：（1）固定每個存儲節(jié)點上輪廓快照的個數為80，底層數據庫的對象個數在2×105～1×106變化；（2）固定底層數據庫的對象個數為8×105，而每個存儲節(jié)點上輪廓快照的個數在20～100間變化。在實驗中，EPSSQDN和TPDA算法的輪廓推薦時間為直接從底層數據庫中獲取輪廓推薦結果的時間開銷，而EMSRDN算法的輪廓推薦時間由兩部分組成，一部分是由EMSRDN算法獲取最優(yōu)輪廓快照集合的時間開銷，另一部分是由輪廓快照集合獲取輪廓推薦結果的時間開銷。圖3（a）和圖3（b）分別給出這3個算法分別在兩組實驗中輪廓推薦時間代價的評估結果。

從圖3可以看出，本文EMSRDN算法在每一種實驗環(huán)境下的輪廓推薦時間開銷均小于目前常用的EPSSQDN和TPDA算法，這主要是因為輪廓推薦過程是CPU和I/O敏感的，算法輸入的數據量大小直接影響輪廓推薦的時間開銷，EMSRDN算法雖然比EPSSQDN和TPDA算法多花費了輪廓快照的選擇時間，然而相對于輪廓計算的時間，這部分開銷所占的比重較小，因此EM SRDN算法比EPSSQDN和TPDA算法效率更高。例如在圖3（a）中，當底層數據庫的對象個數為1×106時，EMSRDN算法的的輪廓推薦時間為604.5 s，而EPSSQDN和TPDA算法則分別需要1868.5 s和2480.2 s；在圖3（b）中，當每個存儲節(jié)點上輪廓快照個數為20時，EMSRDN算法的的輪廓推薦時間為304.5 s，而EPSSQDN和TPDA算法則分別需要1462.1 s和1994.8 s。另一方面，我們在圖3（b）中還可以發(fā)現，對于每個實驗環(huán)境EPSSQDN和TPDA算法的輪廓推薦時間都是相同的，這主要是因為這兩個算法的輸入是底層的基礎數據，與輪廓快照的個數無關。

圖 1 算法優(yōu)化率實驗評估

圖 2 算法運行時間實驗評估

圖 3 輪廓推薦時間代價實驗評估

5 結束語

傳統(tǒng)C/S架構的網絡能夠方便地升級到SPA體系架構的分布式網絡，因此研究“在SPA架構的分布式網絡中有效進行輪廓推薦”是一個很有意義的工作。本文分析了現有工作存在的主要性能缺陷，并給出一種在SPA分布式網絡中，進行輪廓推薦的有效方法EMSRDN。EMSRDN算法不以底層細粒度的數據為輸入參數，而采用預存儲w個輪廓快照來高效處理系統(tǒng)中的u個輪廓推薦指令，并且利用map/reduce分布式計算模型，通過初始輪廓快照集啟發(fā)式構造來快速產生最優(yōu)的w個輪廓快照。理論分析和仿真實驗表明，本文所提的EMSRDN方法具有有效性和實用性。

［1］ Ma L and Zhu M. Skyline query for location-based recommendation in mobile application［C］. Proceedings of the International Workshops on Web-Age Information Management， Beidaihe， China， 2013: 236-247.

［2］ W u J， Chen L， X ie Y， et al.. M odelling and exp loringhistorical records to facilitate service com position［J］. In ternational Journal of W eb and Grid Services， 2014， 10（1）: 54-79.

［3］ Borzsony S， Kossmann D， and Stocker K. The skyline operator［C］. P roceedings of the 17th International Con ference on Data Engineering， Heidelberg， Germany， 2001: 271-285.

［4］ Godfrey P. Skyline cardinality for relational processing［C］. Preceedings of the International Sym posium on Foundations of Information and Know ledge System s， W ilhem inenburg Castle， Austria， 2004: 78-97.

［5］ Huang Z， Xiang Y， Zhang B， et al.. A clustering based approach for skyline diversity［J］. Expert System s with Applications， 2011， 38（7）: 7984-7993.

［6］ Pei J， Jiang B， Lin X， et al.. Probabilistic skylines on uncertain data［C］. Proceedings of the 33rd International Con ference on Very Large Data Bases， V ienna， Austria， 2007: 15-26.

［7］ Fitting M. Possib le world semantics for first-order logic of proofs［J］. Annals of Pure and Applied Logic， 2014， 165（1）: 225-240.

［8］ Vlachou A， Dou lkeridis C， Kotidis Y， et al.. SKYPEER: efficient subspace sky line com pu tation over distributed data［C］. Proceedings of the 23rd International Con ference on Data Engineering， Istanbul， Turkey， 2007: 416-425.

［9］ Ghafarian T， Deldari H， Javadi B， et al.. CycloidGrid: a proxim ity-aware P2P-based resource discovery architecture in volunteer com puting system s［J］. Future Generation Com puter Systems， 2013， 29（6）: 1583-1595.

［10］ Doulkeridis C， Vlachou A， N?rv?g K， et al.. M ultidimensional routing indices for efficient distributed query processing［C］. Proceedings of the 18th ACM Conference on In form ation and Know ledge M anagem ent， Hong Kong， Ch ina， 2009: 1489-1492.

［11］ 黃震華， 向陽， 孫圣力， 等. 超對等網絡中的輪廓查詢優(yōu)化［J］.電子學報， 2013， 41（8）: 1515-1520. Huang Zhen-hua， Xiang Yang， Sun Sheng-li， et al.. Optim izing sky line queries in SPA distribu ted networks［J］. Acta Electronica Sinica， 2013， 41（8）: 1515-1520.

［12］ Zhao L， Yang Y Y， and Zhou X. Continuous probabilistic subspace skyline query processing using grid projections［J］. Journal of Computer Science and Technology， 2014， 29（2）: 332-344.

［13］ Trim ponias G， Bartolini I， Papadias D， et al.. Sky line processing on d istributed vertical decom positions［J］. IEEE Transactions on Know ledge and Data Engineering， 2013，25（4）: 850-862.

［14］ Chaudhuri S， Dalvi N N， and Kaushik R. Robust cardinality and cost estimation for skyline operator［C］. Proceedings of the 22th International Conference on Data Engineering，A tlanta， USA， 2006: 1-10.

黃震華： 男，1980年生，博士，副教授，研究方向為信息服務、數據挖掘和大數據分析等.

張 波： 男，1978年生，博士，副教授，研究方向為信息論、語義計算和模式識別等.

An Efficient M ethod for Skyline Recommendation in Distributed Networks

Huang Zhen-hua①②Zhang Bo③①（School of Electronics and Information， Tongji University， Shanghai 201804， China）
②（Key Laboratory of Embedded System and Service Computing， Tongji University， Shanghai 201804， China）
③（College of Inform ation， Mechanical and E lectrical Engineering， Shanghai Norm al University， Shanghai 200234， China）

Based on distributed networks of the Super-Peer Architecture （SPA）， this paper proposes Efficient Method for Skyline Recommendation in Distributed Networks （EMSRDN）， to hand le u skyline recommendation instructions by prestore w skyline snapshots. The EMSRDN method fully considers the characteristic of storage and communication of SPA networks， and uses the map/reduce distributed com putation model. The EMSRDN algorithm can fast p roduce the optimal w sky line snapshots through the phase of heu ristically constructing the initial set of snapshot. The detailed theoretical analyses and extensive experim ents demonstrate that the proposed EMSRDN algorithm is both efficient and p ractical.

Distributed networks； Skyline recommendation； Map/reduce distributed com putation； Information service

TP393

： A

：1009-5896（2015）05-1214-06

10.11999/JEIT140615

2014-05-12收到，2015-01-12改回

國家自然科學基金（61272268， 61103069），教育部新世紀優(yōu)秀人才支持計劃（NCET-12-0413），國家973計劃項目（2014CB340404），霍英東教育基金會高等院校青年教師基金（142002）和同濟大學中央高?；究蒲袠I(yè)務費專項資金資助課題

*通信作者：黃震華 huangzhenhua@#edu.cn