关联性视频点播系统中基于视频相似的缓存替换策略
2016-01-20张茜,崔勇,田继鹏
关联性视频点播系统中基于视频相似的缓存替换策略
张茜1,2, 崔勇3, 田继鹏1,2
(1.中原工学院; 2.郑州市计算机网络安全评估重点实验室, 郑州 450007;
3.郑州大学 信息工程学院, 郑州 450001)
摘要:关联性视频点播系统中的视频存在一定的关联性,用户会以极大的概率去观看与其当前观看视频相关联且相似度较大的视频。考虑到这一特性,针对P2P环境下的关联性视频点播系统,提出了一种基于视频相似的缓存替换策略。该策略根据视频的标题和简介等语义信息,基于空间向量模型实现视频相似度的计算,在进行缓存替换时,优先考虑替换掉同历史替换视频集合相似度最大的视频,且替换掉的视频的整体流行度尽可能小、副本数尽可能大。 该缓存替换问题为一个多目标规划问题,将其转换为单目标规划,可形式化描述为0-1背包问题,基于贪心算法解决该问题。仿真实验表明,该策略在提高缓存内容命中率上是有效的。
关键词:关联性视频点播系统;视频相似;缓存替换;空间向量模型;0-1背包
收稿日期:2014-12-12
基金项目:河南省科技攻关计划项目(132102310284);河南省教育厅科学技术研究重点项目(14A520015)
作者简介:张茜(1987-),女,河南南阳人,讲师,博士,主要研究方向为网络流媒体。
文章编号:1671-6906(2015)04-0008-06
中图分类号:TP391.1
文献标志码:A
DOI:10.3969/j.issn.1671-6906.2015.04.003
Abstract:The user in VoD system with related videos with great probability to choose the video has a larger similarity and related with the current video. Considering this characteristic, a cache replacement strategy based on video similarity is proposed in P2P VoD system with related videos. According to the video semantic information such as the title and abstract, the video semantic similarity can be calculated by VSM(Vector space model). When a peer's cache space is full, it will replace the videos which have a lager semantic similarity with the already replaced videos and the replaced content should have the smaller popularity and larger replications. The cache replacement problem can be described as a multi-goal optimizing problem, we transform it into a single-goal optimizing problem and then describe it as a 0-1 knapsack problem. A heuristic algorithm base on greedy algorithm is proposed to solve it. The simulation verifies the effectiveness of the scheme in promoting the hit ratio.
关联性视频点播系统如YouTube、优酷等,会为用户当前观看视频推荐一些相关联的视频的列表。随着这种关联性视频点播系统用户数量爆炸性地增长,使用P2P模式来缓解媒体服务器的压力成为必然趋势。 Nettube系统是一种基于P2P的关联性视频点播系统,系统中的节点可以缓存一些视频资源以减小对服务器带来的压力[1]。P2P模式下的关联性视频点播系统,也存在节点缓存资源有限的问题,需要缓存替换机制来应对缓存资源有限问题并提高节点服务能力。
有不少研究者针对P2P点播系统中的节点缓存替换问题进行了研究并给出了相应的解决方案[2-5]。 对于关联性视频点播系统,由于系统中的视频存在一定的关联性,用户在观看视频时,会以极大的概率去观看与其相关联的视频[6]。在这些相关联的视频中,用户更有可能选择与已观看过的视频相似度较大的视频。基于这一特征,本文提出一种策略,即当节点做缓存替换时,看其邻居和自身有没有历史替换掉的视频,若有,则优先考虑替换掉该节点中与历史替换掉的视频语义相似度最大的视频,根据系统中视频的标题和简介等语义信息,基于空间向量模型来实现视频语义相似度计算;若无,则优先考虑自身和邻居中被访问次数最少且被缓存时间最长的视频。同时,应考虑使所替换视频的整体流行度尽可能小、副本数尽可能大。
1关联性视频内容缓存替换问题
1.1问题背景
本文研究的关联性视频点播系统是基于P2P模式的,系统中的用户会以极大的概率去选择当前视频3跳以内的关联视频进行观看,这样将3跳关联视频看作一个簇,则观看同一个簇内的节点可以共享视频资源[7]。如图1所示,节点p1、p2、p3、p4属于同一个簇,且其正在观看的视频为v1、v2、v3、v4。假设节点p1、p2当前观看的视频是v3,p3当前观看的视频是v4,p4当前观看的视频是v2, 则p1观看过的视频v3也有可能被p3、p4请求,即p1缓存的视频资源可供p3、p4使用。同理,同一簇内的节点,即观看3跳以内关联视频的用户节点之间是可以共享视频资源的。若p1的邻居是p2、p3、p4,这些节点之间可以共享视频内容,其缓存里面都存放有已经观看过的视频前缀以供其邻居节点请求;然而由于节点缓存空间的有限性,当缓存空间不足时,应该替换掉哪些视频前缀以提高缓存命中率是需要研究的问题。
图1 节点共享视频内容示意图
1.2问题分析
节点及其邻居可共享视频资源,节点在观看视频时,会去选择该节点及其邻居欢迎的视频及与其语义相似度较大的视频。由于缓存替换的目的是增大缓存内容的利用率,即增大节点及其邻居的访问率,因此在做缓存替换时,应优先考虑替换掉可能不受本节点及其邻居欢迎的视频;不受本节点及其邻居欢迎的缓存内容极有可能是已经被本节点及其邻居替换掉的视频语义相似度较大的视频。
将视频vi在某时刻t的局部流行度定义为该视频被节点P缓存后被节点P及其邻居所访问的次数。整体流行度为该视频自加入系统以来被系统中用户访问的数量。视频的整体流行度在一定程度上也会影响用户的观看选择。节点及其邻居在某一时间段内访问次数较少的视频即针对该节点和邻居局部流行度较小的视频,有可能与已替换掉的视频语义相似度较大,被作为替换视频;然而,如果该视频的整体流行度比较大,用户及其邻居可能会在下一时刻青睐这个整体流行度比较大的视频。因此,在做缓存替换时,应考虑使替换掉的视频整体流行度尽可能小。
节点缓存的内容都是已经观看过的视频前缀,同一簇内的节点有着相似的观看兴趣,因此节点与其邻居节点缓存的视频前缀必定还有重复。一节点与其邻居节点缓存所构成的视频资源共享池里视频的多样性可使资源共享池的视频资源能够更好地满足节点的需求。如果同一个视频前缀在一个节点和其邻居节点的多个缓存中有存储,则说明该视频比较受欢迎,而其至少在一个节点的缓存中存储就足以满足与其共享的节点在下一时刻对该视频的请求;如果缓存该视频的节点数量过多,则会对缓存空间造成一定的浪费。节点在进行缓存替换时也应考虑到缓存内容在邻居节点缓存中的副本数,使替换掉的缓存内容的副本数尽可能大,以提高缓存空间利用率,且尽量保留只被一个节点所缓存的视频,以保证由节点和其邻居构成的缓存资源池的视频内容多样性。
通过分析可知,当节点缓存空间满时,应优先替换掉不受节点及其邻居欢迎的视频,根据同已经替换掉的视频的语义相似度来判断视频是否可能不受欢迎;同时,应满足最大化所替换缓存视频内容的副本数和最小化所替换缓存视频内容的整体流行度。
2基于空间向量模型的视频语义相似度计算
根据对缓存替换问题的分析,解决该问题需要考虑的一个主要因素是视频语义相似度。一个视频使用标题和描述等相关语义信息来描述,这些语义信息是用户对该视频内容和特征的高度概括,描述视频的这些文本信息之间的相似度能很好地体现视频语义上的相似度,因此对视频语义相似度的计算即是对这些描述视频的文本信息的相似度的计算。向量空间模型(vector space model)可以将一个文本用对应的一个多维空间中的向量表示,由特征权重计算得到的特征向量可以在一定程度上表示文本的内容特征[8-9]。由于向量空间模型具有较强的计算和可操作性[10],并得到了广泛的应用且取得了较好的效果,因此本文基于向量空间模型来实现对视频语义相似度的计算。
一个视频使用标题、描述、用户评论等文本信息来描述,这些文本信息反映了该视频的主要内容。描述这些视频的文本相似度在一定程度上反映了视频语义相似度,因此对视频相似度的计算实质上是对描述这些视频的文本信息相似度的计算。
基于空间向量模型的视频相似度计算流程主要分为三大模块:描述视频文本信息分词模块、基于TF/IDF的词项权重赋值模块、基于cosine的相似度计算模块。计算流程如图2所示。
图2 视频相似度计算主要模块及流程示意图
(1)
3基于视频相似的缓存替换策略
3.1缓存替换问题形式化描述
通过上述对缓存替换问题的分析,节点的缓存替换问题可描述如下:
假设节点能力相同,当前节点P缓存n个视频,且每个节点有q个邻居,缓存的视频集合为V={v1,v2,…,vn}, 其中视频vj对应的在节点及其邻居中的副本数为rj,r为缓存视频副本数的下限值,其整体流行度为pj。假设已经被节点P及其邻居替换掉的视频集合为V′,其中第i个邻居替换掉的视频集合为Vi′,则V′=V1′∪V2′…∪Vn′,节点P和其邻居当前缓存的视频集合V″={v1″,v2″,…,vm″},视频vj与视频集合V′的相似度表示为sim(vj,V′)。
输入:节点P缓存的视频v1,v2,…,vn,第i个邻居替换掉的视频集合为Vi′。
问题定义:找到节点P需要替换掉的视频vj∈{v1,v2,…,vn},目标是maxrj,minpj,max sim(vj,V′)。
输出:替换视频vj。
根据以上描述,替换掉的视频vj有3个目标,即最大化该视频的副本数、最小化替换视频的流行度以及最大化替换视频和已经替换掉的视频集合的相似度。当满足最大化相似度时,说明该视频同已经替换掉的视频集合的相似度较大,同已经替换掉的视频集合一样,该视频可能不受当前节点及其邻居的欢迎,即局部流行度较小,因而该视频在该节点及其邻居中的副本数可能会比较小。然而局部流行度较小,整体流行度可能较大,这对于最大化替换视频副本数和最小化整体流行度这两个优化目标不能满足;当满足所替换视频最大化副本数时,由于该视频副本数较大,说明该视频被某一节点及其邻居观看的次数比较多,局部流行度大,其与已经替换掉的不受欢迎的视频集合的相似度比较小。局部流行度大的视频,其整体流行度可能也比较大,因此对于最大化相似度和最小化整体流行度这两个目标不一定能够满足。当满足最小化整体流行度时,在其局部流行度较小时,其副本数会比较小,无法满足最大化替换视频副本数。如果局部流行度较大时,则无法满足最大化替换视频同已经替换掉的视频集合相似度。
缓存替换问题中的这3个目标中最优化任意一个目标,另外的两个不一定满足最优。这是一个多目标规划的问题,可将其转换为一个单目标规划问题进行解决。本文在做缓存替换时,更看重视频之间的相似度,认为视频之间的相似度对用户的观看选择影响较大。由于缓存视频的多样性在提高缓存命中率上比视频整体流行度因素有着更明显的影响,因此该问题可以转换为:先从节点P缓存的视频v1,v2,…,vn中挑选出满足视频相似度和副本数条件的m个视频,再从这m个视频中选择一个整体流行度最小的视频作为要替换掉的视频,其中相似度条件变为限制条件。问题的假设不变,选择m个满足相似度和副本数条件的问题描述为:
输入:节点P缓存的视频v1,v2,…,vn, 第i个邻居替换掉的视频集合为Vi′。
输出:视频集合Vm={v1,v2,…,vm}。
其中,S为与V′相似度最大的m-k个视频的相似度之和。视频同视频集合的相似度计算如式(1)所示。
该问题可描述为0-1背包问题,这是一个NP完全问题。本文提出一种启发式算法来得到在相似度限制条件下的近似优化副本数条件中的m个视频,从这m个视频中找出整体流行度最小的视频,就是所要替换掉的视频。
3.2算法设计
实验节点P基于视频相似的缓存替换算法具体描述如下:
(1)计算节点P和其邻居替换掉的集合V′,转入步骤(2)。
(2)判断已经被本节点和邻居替换掉的视频集合V′是否为空。若为空,则转入步骤(3);若非空,转入步骤(4)。
(3)遍历节点P与其邻居缓存的视频集合V″,找到被缓存时间最长且被访问次数最少的视频vi″,将集合V中与vi″相似度最大的m-k个视频并集放入集合Vm,再从剩余的视频中选择副本数最大的k个视频放入集合Vm,转入步骤(5)。
(4)将集合V中与V′相似度最大的m-k个视频并集放入集合Vm,再从剩余的视频中选择副本数最大的k个视频放入集合Vm,转入步骤(5)。
(5)视频集合Vm中整体流行度最小的视频即为将要被替换掉的视频。 表1所示为算法中各个参数的含义。
表1 缓存替换算法中各参数的含义
节点P的缓存替换算法实现如下:
算法1缓存替换算法
输入:视频集合V,V1′,…,Vq′,V″。
输出:将要替换掉的视频vi。
Compute SetV′={VUV1′UV2′…UVq′}
if(V′=Ø)
pick an elmentvi″ from setV″, the cache time ofVi″ is the longest and it has the minimum number of being requested
for each elmentvj in setV
Calculate sim(vj,vi″)
end for
pickm-kelements which have the most similarity withvi″ from setVto setVm
pickkelements which have the maximum value of replication from setVto setVm
vi is the element inVm, which has the minimum value of popularity
else
for each elmentvj in setV
Calculate sim(vj,V′)
end for
pickm-kelements from setVto setVk, which have the most similarity withV′
pickkelements which have the maximum value of replication from setVto setVm
vi is the element inVm, which has the minimum value of popularity
end if
通过对该算法的描述与实现,发现参数q、k、m的设置可能会对算法的结果产生一定的影响,在做算法性能分析时,将对这3个参数对算法的影响进行分析说明。
4实验与分析
算法的评价指标为命中率,缓存命中率hitratio是在时间段T内该缓存内容满足当前节点及其邻居请求的次数与时间段T内当前节点和邻居发出请求的总次数之比。实验内容主要有两部分:①将缓存替换算法同典型的FIFO、LRU算法进行对比,比较不同算法对缓存内容命中率的影响。②针对3.2节中出现的一些参数,考察这些参数的设置对算法性能的影响。
4.1实验配置
4.2结果与分析
图3所示为随着节点缓存空间大小的变化,不同算法下节点缓存内容命中率的变化情况。可以看出,随着缓存空间的增大,所提算法的缓存命中率有一定的提高,当缓存空间达到最多可缓存15个视频前缀时,其命中率的提高不明显。从图中也可看出,本文所提算法在提高缓存命中率上优于FIFO和LRU算法,且稳定性较好,在缓存空间增大到一定程度时,性能上并没有受到明显影响。这是由于所提算法利用节点趋向于观看与当前视频关联的且语义相似度较大的流行视频这一特点,替换掉与已经替换掉的视频语义相似度较大的视频,提高了缓存命中率。
图3 不同算法下对缓存命中率的影响
图4所示为节点维护邻居数q的变化对缓存命中率的影响。随着邻居数量的增多,所提算法的命中率有一定的提高,这是因为邻居数量的增多使得可共享的视频量增加,且在同等时间间隔下已经替换掉的视频数增大,在一定程度上提高了将要替换的视频的准确度,当邻居数量增大到10时,其对缓存命中率的影响不明显。而采用FIFO和LRU算法时,在邻居数量增大到一定的程度时,缓存命中率会略有下降。缓存替换算法中的参数m即选择满足相似度和副本数条件的视频数目,参数k是与已经替换掉的视频集合相似度最大的视频数目。
图4 参数q对缓存命中率的影响
图5 参数k对缓存命中率的影响
图6 参数m对缓存命中率的影响
参考文献:
[1]Cheng X, Liu J. Nettube: Exploring Social Networks for Peer-to-peer Short Video Sharing[C]//Proceedings of IEEE INFOCOM. Rio de Janeiro: IEEE, 2009: 1152-1160.
[2]叶剑虹, 叶双. 基于混合模式的流媒体缓存调度算法[J].计算机科学,2013, 40(2):61-64.
[3]孙昕, 陈德运. 静态与动态结合的流媒体缓存替换算法研究[J].计算机工程与设计, 2012, 33(4):1495-1498.
[4]杨菲菲, 陈志云,曾秋梅. 一种基于流行度和分段适应性的流媒体缓存替换算法[J].计算机应用与软件,2010, 27(7):227-229.
[5]胡懋智, 徐恪, 夏树涛,等. TOW:一种新的P2P实时流媒体缓存替换算法[J]. 小型微型计算机系统, 2009,30(8):1484-1489.
[6]Khemmarat S, Zhou R, Gao L, et al. Watching User Generated Videos with Prefetching[C]. Proceedings of ACM Conference on Multimedia Systems, 2011: 187-198.
[7]Zhang Q, Lin Y, Wang Z. Cost-effective Capacity Migration of Peer-to-Peer Social Media to Clouds[J]. Peer-to-Peer Networking and Applications, 2013, 6(3): 247-256.
[8]Sebastiani F. Machine Learing in Automated Text Categorization[J]. ACM Computing Surveys, 2002, 34(1):1-47.
[9]Salton G, Lesk M E. Computer Evaluation of Indexing and Text Processing[J]. Journal of the ACM, 1968, 15(1): 8-36.
[10]Salton G. Automatic Information Organization and Retrieval[M]. New York: McGraw-Hill Press, 1968.
(责任编辑:张同学)
Cache Replacement Strategy Based on Video Similarity in
VOD System with Related Videos
ZHANG Qian1,2, CUI Yong3, TIAN Ji-peng1,2
(1.Zhongyuan University of Technology;
2.Zhengzhou Municipality Key Lab of Computer Network Security Assessment, Zhengzhou 450007;
3.Zhengzhou University, Zhengzhou 450001, China)
Key words:the VOD system with related videos; video similarity; cache replacement; VSM; 0-1 knapsack problem