黃震華張 波

①（同濟(jì)大學(xué)電子與信息工程學(xué)院 上海 201804）

②（同濟(jì)大學(xué)嵌入式系統(tǒng)與服務(wù)計(jì)算國(guó)家教育部重點(diǎn)實(shí)驗(yàn)室 上海 201804）

③（上海師范大學(xué)信息與機(jī)電工程學(xué)院 上海 200234）

一種分布式網(wǎng)絡(luò)中輪廓推薦的有效方法

黃震華*①②張 波③

①（同濟(jì)大學(xué)電子與信息工程學(xué)院 上海 201804）

②（同濟(jì)大學(xué)嵌入式系統(tǒng)與服務(wù)計(jì)算國(guó)家教育部重點(diǎn)實(shí)驗(yàn)室 上海 201804）

③（上海師范大學(xué)信息與機(jī)電工程學(xué)院 上海 200234）

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

分布式網(wǎng)絡(luò)；輪廓推薦；Map/reduce分布式計(jì)算；信息服務(wù)

1 引言

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

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

2 問(wèn)題描述

3 EMSRDN算法

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

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

map函數(shù)和reduce函數(shù)具體實(shí)施過(guò)程如表2和表4所示。

OPTIM IZATION的具體實(shí)施過(guò)程如表3。

4 實(shí)驗(yàn)評(píng)估

這一節(jié)通過(guò)具體的實(shí)驗(yàn)來(lái)評(píng)估本文EMSRDN算法的優(yōu)化率和運(yùn)行時(shí)間。

表1 EMSRDN算法

表2 map函數(shù)

表3 OPTIM IZATION實(shí)施過(guò)程

4.1 實(shí)驗(yàn)環(huán)境設(shè)置

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

表4 reduce函數(shù)

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

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

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

在圖1評(píng)估算法優(yōu)化率的實(shí)驗(yàn)中，本文以最優(yōu)算法（OPTIMAL）為基準(zhǔn)，因?yàn)樗@取的輪廓快照集合是精確最優(yōu)的，即將該精確輪廓快照集合的優(yōu)化率定為100%。我們從圖1可以看出，EMSRDN算法的優(yōu)化率接近于最優(yōu)算法。例如在圖1（a）中，當(dāng)每個(gè)存儲(chǔ)節(jié)點(diǎn)上的輪廓快照數(shù)等于100時(shí)，EMSRDN算法的優(yōu)化率為37.5%；在圖1（b）中，當(dāng)計(jì)算節(jié)點(diǎn)上輪廓推薦指令數(shù)等于80時(shí)，EMSRDN算法的優(yōu)化率為68.3%。

4.3 EMSRDN算法的運(yùn)行時(shí)間評(píng)估

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

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

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

4.4 SPA分布式網(wǎng)絡(luò)中的輪廓推薦代價(jià)評(píng)估

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

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

圖 1 算法優(yōu)化率實(shí)驗(yàn)評(píng)估

圖 2 算法運(yùn)行時(shí)間實(shí)驗(yàn)評(píng)估

圖 3 輪廓推薦時(shí)間代價(jià)實(shí)驗(yàn)評(píng)估

5 結(jié)束語(yǔ)

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

［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áng)， 孫圣力， 等. 超對(duì)等網(wǎng)絡(luò)中的輪廓查詢優(yōu)化［J］.電子學(xué)報(bào)， 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年生，博士，副教授，研究方向?yàn)樾畔⒎?wù)、數(shù)據(jù)挖掘和大數(shù)據(jù)分析等.

張 波： 男，1978年生，博士，副教授，研究方向?yàn)樾畔⒄?、語(yǔ)義計(jì)算和模式識(shí)別等.

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改回

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

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