Web预取技术综述

Web预取是减少用户访问延时、提高网络服务质量的关键技术之一,近年来已成为国内外的研究热点.通过利用WWW访问的空间局部性,Web预取使缓存机制从时间局部性向空间局部性扩展.归纳了Web预取技术的分类,概括和比较了不同类别的优势和局限性,给出了预取模型的基本框架及每部分的主要功能,并对各种评价标准进行了详细介绍.同时,深入分析和探讨了现有的几种典型预取算法,系统地比较了这些算法的优缺点.最后从在线性、协作预取、动态流行度、划分用户会话和基于语义与基于路径相结合等方面指出了Web预取技术的研究方向.

基于非压缩后缀树的在线PPM预测模型

PPM模型适合预测用户的下一个请求,但已有的PPM模型不具备在线性,更新通过重构来实现,不能满足实时更新的要求。该文提出基于非压缩后缀树的在线PPM预测模型,采用非压缩后缀树实现增量式在线更新,提高了模型的更新速度。该模型的优点是具备在线性。

基于滑动窗口的自适应网页预测模型

PPM模型广泛应用于Web预取技术,但大多数的PPM模型不具有自适应性,不能反映用户浏览模式的改变。通过对标准PPM模型的扩展,提出基于滑动窗口的自适应网页预测模型。该模型仅保留处于滑动窗口之内的最近访问序列,从而反映用户兴趣的变化,同时利用非压缩后缀树增量式添加新的用户请求和删除过时的浏览信息,以提高更新速度。实验表明,该模型能更准确地描述用户在Web上的浏览特征,在预取性能上明显地优于以往的模型。

一种新的二维线段裁剪方法

线段裁剪技术在计算机图形处理中占有重要的地位,是计算机图形学中许多重要问题的基础,裁剪速度的高低直接影响到图形软件包的运行速度.关于线段的二维裁剪有许多比较成熟的算法,如Cohen-Sutherland、Cyrus-Beck、Liang-Barsky和Nicholl-Lee-Nicholl等算法,其中Nicholl-Lee-Nicholl的二维线段裁剪算法效率很高.但是在Nicholl-Lee-Nicholl直线裁剪算法中,为了确定线段位于哪个区域内必须进行多个斜率的计算,并且由于运用了回避原则,使得算法的复杂度增加〔1〕.文中算法基于数学中提到的区间思想,算法简单。

一种Byte查找第K个元素的算法研究

查找第K个元素的问题在计算机查找技术中占有十分重要的地位,这个问题的最直接解法是先将序列排序,从而能得到第K个元素,最少需O(nlogn)次比较,即时间复杂度为O(nlogn).比较好的方法是采用分治策略解决该问题,但其最坏时间复杂度为O(n2),平均时间复杂度为O(2n)〔1〕.本文提出一种Byte解决第K个元素问题的算法,该算法的平均时间复杂度为O(n+n/255),优于以前对该问题的求解方法〔1〕,而且该算法可以适用于由整数、浮点数、无符号整型数、双精度数和字符型数构成的超大数集.

一种新的P2P系统中基于双ratings的声誉管理机制

声誉系统的效率取决于回馈的质量,现有P2P系统中的声誉模型不能处理合谋、不递交ratings等攻击,并且对无过失节点还存在不公平性.针对这些问题,提出了一个新的基于双ratings的声誉管理机制.采用两个度量来评价节点:服务信任和回馈信任.服务信任反映server提供服务的可靠性;回馈信任反映consumer汇报ratings的可信度.一次交易后,要求服务双方都递交ratings,依据这两个ratings对server的服务信任和consumer的回馈信任进行更新,并且server的服务信任更新与consumer的回馈信任紧密相关.为了防止恶意节点反复实施恶意行为或不递交rating,还提出了一个惩罚机制,作为对声誉模型的补充.仿真表明,提出的声誉管理机制能够抵制上述恶意攻击,减少不公平性.

超级节点对等网中的声誉管理

对现有P2P文件搜索协议进行扩展,提出了一个适用于超级节点对等网的声誉管理协议——SP2PRep。它将叶子节点的声誉投票集中在超级节点上,声誉查询仅在超级节点间进行,搜索空间小。给出了协议执行步骤和实现的消息格式。分析和仿真表明,与现有对等网中的声誉管理协议相比,SP2PRep减少了带宽消耗,加快了声誉查找速度,提高了平均的服务成功率,达到了同等的投票安全性。

基于EPLD的PCI总线设计

给出了采用EPLD可编程逻辑器件来实现PCI总线接口的设计思路,完成了整个系统的设计和调试,为利用计算机实时处理各种形式的数据提供了很好的手段和方法.

基于链接重要性和数据场的链接预测算法

针对现有基于节点相似性的链接预测方法忽略了网络拓扑本身链接强度的信息,带权的拓扑路径方法中权值较难确定等缺陷,提出一种基于链接重要性和数据场的链接预测算法。首先,将所有链接边赋予不同的链接权重;其次,考虑潜在链接节点间的相互影响,对部分没有链接的节点进行链接预估计;最后,利用数据场势函数计算两节点间的相似值。在典型的网络数据进行的实验结果表明,所提方法在分类指标和推荐指标中都有很好的表现:以AUC为评价指标时,比同复杂度的局部路径(LP)算法提高了3到6个百分点;以DCG为评价指标时比LP算法提高了1.5到2.5个DCG值。算法整体上提高了预测准确性,且由于参数确定简单,复杂度又不高,在实际中易于部署。

贝叶斯网络查询语义扩展的专家发现方法

专家发现是实体检索领域的一个研究热点,针对经典专家发现模型存在索引术语独立性假设与检索性能低的缺陷,提出一种基于贝叶斯网络模型的专家发现方法。该方法模型采用四层网络结构,能够实现图形化的概率推理,同时运用词向量技术能够实现查询术语的语义扩展。实验结果显示该模型在多个评价指标上均优于经典专家发现模型,能够有效实现查询术语语义扩展,提高专家检索性能。

基于权邻域的代表性用户抽样算法

代表性用户抽样方法在社会网络分析领域中得到广泛的应用,如何使其抽取的子集代表网络中所有用户具有重要的研究意义。现有方法较少关注网络拓扑结构中用户潜在的大量有用信息,通过对统计分层抽样模型进行优化,提出了一种基于权邻域的代表性用户抽样算法。为了从网络拓扑结构中获得用户更多有价值的内容,该算法使用权邻域对用户代表度计算方法进行改进,同时与用户属性相结合。之后根据用户属性值将用户分成不同属性组,计算用户在每个属性组的代表度。接着通过质量函数来衡量代表性用户的代表程度。采用启发式贪心算法抽取代表性用户。在4个数据集上与6种传统抽样算法进行实验比较,结果表明基于权邻域的代表性用户抽样算法在精确率、召回率和F1-Measure评价指标上均有提升。

基于全局的引文网络影响力最大化算法

从大量的期刊论文中搜寻出最具有影响力的若干篇论文对于学术研究具有重要意义,但现有影响力最大化算法需要结合贪心算法,时间复杂度较高.依据论文引用网络中引用关系的时间单向性和无环特征,提出一种基于节点全局影响力的影响力最大化算法.该算法主要包括:①计算所有节点的全局影响力.结合引文网络的发表时间特性,构造上三角稀疏影响方阵.在线性阈值传播模型的基础上,利用节点间的直接、间接路径影响以及累积计算规则模拟影响力在网络上的传播过程.方阵每进行一次运算,会将全部节点的影响向下传播一跳,得到下一个路径的影响,并统计全部影响,最终得到表示所有节点全局影响力的方阵;②将全部节点按全局影响力排序.选择前n个节点作为候选节点来选取k个种子节点,在选取的过程中避免影响力较大节点的聚集情况.以真实的学术引文网络数据集为实验数据,将提出的算法与两种基准算法从激活范围和运行时间两个方面进行对比.实验结果表明,该算法大大降低了时间复杂度,且激活范围接近于贪心算法.

基于固定邻域规模的动态网络影响力最大化探测算法

以往对影响力最大化问题的研究大多是基于静态图进行优化研究,但在现实中,网络数据量随着时间不断增加,系统不可能实时获取到整个网络中节点之间的连接情况。在传统MaxG探测模型的基础上,采用固定邻域规模和节点邻域层级相结合的方式计算节点影响力大小,提出了新的动态网络探测算法RAS-MaxG(regular area scale-MaxG),解决了传统探测算法由于采用度来衡量节点影响力值所导致的节点之间区分性差的问题。最后通过在真实数据集上的实验对比,验证了所提算法在最终影响力覆盖范围方面具有更好的性能表现。

利用LMS规则的预取策略

以往基于All-Kth-Order Markov模型的Web预取策略没有全面考虑访问序列长度、转移概率、网页访问频率、预测准确率和输出概率分布等重要特性。针对这一缺陷,提出了一种基于LMS(least meansquare)规则的预取策略All-Kth-Order LMS。基于日志驱动的实验表明,All-Kth-Order LMS在Web预取性能上具有明显的优势。