一种分布式网络中轮廓推荐的有效方法

黄震华张 波

①（同济大学电子与信息工程学院 上海 201804）

②（同济大学嵌入式系统与服务计算国家教育部重点实验室 上海 201804）

③（上海师范大学信息与机电工程学院 上海 200234）

一种分布式网络中轮廓推荐的有效方法

黄震华*①②张 波③

①（同济大学电子与信息工程学院 上海 201804）

②（同济大学嵌入式系统与服务计算国家教育部重点实验室 上海 201804）

③（上海师范大学信息与机电工程学院 上海 200234）

当底层数据的容量以及轮廓推荐指令个数增大时，轮廓推荐的时间代价将呈指数级增长，从而严重影响其推荐效率。为此，基于超对等分布式网络（SPA），该文提出预存储w个轮廓快照来高效处理系统中u个轮廓推荐指令的分布式网络轮廓推荐算法（EMSRDN）。EMSRDN算法充分考虑SPA网络的数据存储和通信特性，利用map/reduce分布式计算模型，通过初始快照集启发式构造来快速产生最优w个轮廓快照。理论分析和仿真实验表明，该算法具有有效性和实用性。

分布式网络；轮廓推荐；Map/reduce分布式计算；信息服务

1 引言

轮廓推荐技术是近年来信息服务方向的一个研究重点和热点［1］，这主要是因为它在许多领域有着广泛的应用，如：大数据分析、城市导航系统、多标准决策支持以及高维数据可视化等［2］。给定对象集合R=｛o1，o2，…，on｝，其中每个对象oi（i∈［0，n］）具有δ个维度F=｛d1，d2，，dδ…｝，每个维度衡量它的一个子特征（比如距离，价格等），那么维度空间U F⊆上的轮廓推荐就是在R中找出一类对象集合R'，它满足如下条件：⊆R R'且R'中每个对象不会在U所有维度上的取值均差于R中的某一对象。显然，通过轮廓推荐，用户只需考虑属于轮廓对象集合的对象，而不必关心那些被过滤掉的对象，这样用户就可以在小规模的轮廓对象集合上对自己感兴趣的对象进行选择。不难看出，δ个维度的对象集合，最多拥有2 1δ-个维度空间上的轮廓推荐。

随着分布式网络的深入应用，文献［8］首次考虑在超对等架构（Super Peer Architecture， SPA）［9］的分布式网络中实施轮廓推荐技术，并通过传输扩展轮廓对象集合来降低数据传输的代价。SPA架构是目前使用较广的一种分布式网络，因为传统客户/服务（Client/Server， C/S）模型的网络架构能够方便地升级为SPA架构的分布式网络。文献［10］在文献［9］的基础上，增加了多维路由索引机制（Multidimensional Routing Indices， MRI）来降低参与轮廓推荐的网络节点数量，从而进一步降低数据传输的代价。文献［11］在识别文献［8，9］性能缺陷的基础上，提出了有效预处理分布式网络中子空间轮廓推荐的有效方法（Efficient Preprocessing of Subspace Sky line Queries in Distributed Networks，EPSSQDN）。EPSSQDN算法基于布隆过滤器（Bloom Filter， BF）技术［11］来缩减数据传输代价；同时基于正规格结构［12］来索引网络节点上的数据对象，并且使用格间的支配关系来有效降低数据对象间的比较次数，从而提高轮廓推荐的计算效率。文献［13］基于非共享策略，围绕降低网络反应延迟与通信负荷的目标，提出了一种两阶段分布式算法（Two-Phase Distributed A lgorithm， TPDA），并对算法的关键实现环节，如协调-远程节点间的通信、轮廓推荐增量的计算等进行优化，使算法在通信负荷与反应延迟上达到较好的综合性能。

2 问题描述

3 EMSRDN算法

本文发现，从候选的γ个轮廓快照中精确挑选最优的w（γ＞w）个轮廓快照，需要遍历指数级个数的轮廓快照组合空间，从而使得获取精确最优w个轮廓快照是非多项式困难（NP-hard）问题。因此在本节中，将提出一种快速获取近似最优方案ASN的有效算法EMSRDN。

EMSRDN算法的核心思想是利用map/reduce分布式计算模型，通过初始轮廓快照集启发式构造以及基于遗传算法的轮廓快照集深度优化这两个阶段来快速产生最优的w个轮廓快照，其伪代码如表1所示。

map函数和reduce函数具体实施过程如表2和表4所示。

OPTIM IZATION的具体实施过程如表3。

4 实验评估

这一节通过具体的实验来评估本文EMSRDN算法的优化率和运行时间。

表1 EMSRDN算法

表2 map函数

表3 OPTIM IZATION实施过程

4.1 实验环境设置

本文的实验环境由30台PC机组成3层SPA分布式网络架构，每台PC机的配置为4核i5-3450 CPU， 4 G内存和500 G硬盘，操作系统为CentOS Linux 6.4。计算节点包含10台PC机组成的集群，其中1台PC机选为控制计算机（Master），这10台PC机构成Hadoop平台，其版本号为1.0.3。而其余两层为20个分布式存储节点，共分配20台PC机。实验中，本文在计算节点上产生200个轮廓推荐指令，在每个存储节点上产生100个轮廓快照，总计2000个候选轮廓快照。

表4 reduce函数

与EMSRDN比较的方法是OPTIMAL算法，通过指数级时间复杂度的穷举来获取精确最优的轮廓快照集合；每一类实验分为2组：（1）固定计算节点上轮廓推荐指令的个数为100，而每个存储节点上轮廓快照的个数在20～100间变化；（2）固定每个存储节点上轮廓快照的个数为50，而计算节点上轮廓推荐指令的个数在40～200间变化。所有算法的代码编译采用JDK 1.6。

4.2 EMSRDN算法的优化率评估

本小节通过实验评估EMSRDN算法的优化率。图1（a）和图1（b）分别给出这两个算法分别在两组实验中优化率的评估结果。

在图1评估算法优化率的实验中，本文以最优算法（OPTIMAL）为基准，因为它获取的轮廓快照集合是精确最优的，即将该精确轮廓快照集合的优化率定为100%。我们从图1可以看出，EMSRDN算法的优化率接近于最优算法。例如在图1（a）中，当每个存储节点上的轮廓快照数等于100时，EMSRDN算法的优化率为37.5%；在图1（b）中，当计算节点上轮廓推荐指令数等于80时，EMSRDN算法的优化率为68.3%。

4.3 EMSRDN算法的运行时间评估

本小节通过实验评估EMSRDN算法的运行时间。图2（a）和图2（b）分别给出这两个算法分别在两组实验中优化率的评估结果。

虽然在图1中，最优算法获取的轮廓快照集合的优化率略高于EMSRDN算法，然而在图2（a）和图2（b）评估算法运行时间的实验中，我们可以发现最优算法在每种实验环境下的运行时间都是非常巨大，这主要是因为最优算法为了获取精确的轮廓快照集合，需要遍历所有可能的轮廓快照组合空间，因此需要指数级的时间开销，而EMSRDN算法只需要多项式时间开销即可返回近似最优的轮廓快照集合，而无需遍历所有可能的轮廓快照组合空间。例如在图2（a）中，当每个存储节点上的轮廓快照数等于100时，最优算法的运行时间为79824.6 s，而算法EMSRDN的运行时间仅为35.9 s；在图2（b）中，当计算节点上轮廓推荐指令数等于200时，最优算法的运行时间为49652.5 s，而算法EMSRDN的运行时间仅为20.4 s。

因此，综合图1和图2的实验评估，可以得出本文的EMSRDN算法能够很好平衡轮廓快照集合的优化率与运行时间，而且具有很好的可扩展性。

4.4 SPA分布式网络中的轮廓推荐代价评估

目前常用的SPA分布式网络中轮廓推荐的算法有两个，即EPSSQDN［11］和TPDA［13］。因此，在这一小节中，通过实验来对比本文EMSRDN算法与EPSSQDN， TPDA算法的时间代价。基础数据库由文献［3］的数据生成器产生，包含1×106个对象，每个对象具有5个浮点型属性。轮廓指令个数固定为100。实验分为两组：（1）固定每个存储节点上轮廓快照的个数为80，底层数据库的对象个数在2×105～1×106变化；（2）固定底层数据库的对象个数为8×105，而每个存储节点上轮廓快照的个数在20～100间变化。在实验中，EPSSQDN和TPDA算法的轮廓推荐时间为直接从底层数据库中获取轮廓推荐结果的时间开销，而EMSRDN算法的轮廓推荐时间由两部分组成，一部分是由EMSRDN算法获取最优轮廓快照集合的时间开销，另一部分是由轮廓快照集合获取轮廓推荐结果的时间开销。图3（a）和图3（b）分别给出这3个算法分别在两组实验中轮廓推荐时间代价的评估结果。

从图3可以看出，本文EMSRDN算法在每一种实验环境下的轮廓推荐时间开销均小于目前常用的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）中，当每个存储节点上轮廓快照个数为20时，EMSRDN算法的的轮廓推荐时间为304.5 s，而EPSSQDN和TPDA算法则分别需要1462.1 s和1994.8 s。另一方面，我们在图3（b）中还可以发现，对于每个实验环境EPSSQDN和TPDA算法的轮廓推荐时间都是相同的，这主要是因为这两个算法的输入是底层的基础数据，与轮廓快照的个数无关。

图 1 算法优化率实验评估

图 2 算法运行时间实验评估

图 3 轮廓推荐时间代价实验评估

5 结束语

传统C/S架构的网络能够方便地升级到SPA体系架构的分布式网络，因此研究“在SPA架构的分布式网络中有效进行轮廓推荐”是一个很有意义的工作。本文分析了现有工作存在的主要性能缺陷，并给出一种在SPA分布式网络中，进行轮廓推荐的有效方法EMSRDN。EMSRDN算法不以底层细粒度的数据为输入参数，而采用预存储w个轮廓快照来高效处理系统中的u个轮廓推荐指令，并且利用map/reduce分布式计算模型，通过初始轮廓快照集启发式构造来快速产生最优的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］ 黄震华， 向阳， 孙圣力， 等. 超对等网络中的轮廓查询优化［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），教育部新世纪优秀人才支持计划（NCET-12-0413），国家973计划项目（2014CB340404），霍英东教育基金会高等院校青年教师基金（142002）和同济大学中央高校基本科研业务费专项资金资助课题

*通信作者：黄震华 huangzhenhua@tongji.edu.cn