首页> 中国专利> 通过将历史重要性计算在内来计算文档重要性

通过将历史重要性计算在内来计算文档重要性

摘要

提供了一种基于对链接的时间分析来确定具有文档之间的链接的文档的时间重要性的方法和系统。时间排名系统在各个快照时刻收集指示文档之间链接的链接信息或快照。时间排名系统通过将从当前快照(即,具有最近的快照时刻)中导出的文档的当前重要性和从过去的快照中导出的文档的历史重要性计算在内来计算文档的当前时间重要性。为了计算网页的当前时间重要性,时间排名系统合计网页对于每一个快照的重要性。

著录项

  • 公开/公告号CN101652771A

    专利类型发明专利

  • 公开/公告日2010-02-17

    原文格式PDF

  • 申请/专利权人 微软公司;

    申请/专利号CN200880011413.2

  • 发明设计人 T-Y·刘;H·李;L·齐;B·高;L·杨;

    申请日2008-04-11

  • 分类号G06F17/18(20060101);

  • 代理机构31100 上海专利商标事务所有限公司;

  • 代理人顾嘉运;钱静芳

  • 地址 美国华盛顿州

  • 入库时间 2023-12-17 23:31:30

法律信息

  • 法律状态公告日

    法律状态信息

    法律状态

  • 2015-06-03

    专利权的转移 IPC(主分类):G06F17/18 变更前: 变更后: 登记生效日:20150515 申请日:20080411

    专利申请权、专利权的转移

  • 2013-11-20

    授权

    授权

  • 2010-04-21

    实质审查的生效 IPC(主分类):G06F17/18 申请日:20080411

    实质审查的生效

  • 2010-02-17

    公开

    公开

说明书

背景

如Google和Overture等许多搜索引擎服务允许对能经由因特网访问的信 息进行搜索。这些搜索引擎服务允许用户搜索用户可能感兴趣的显示页面,如 网页。在用户提交包含搜索项的搜索请求(即,查询)之后,搜索引擎服务标 识可能与这些搜索项相关的网页。为快速标识相关的网页,搜索引擎服务可维 护关键词到网页的映射。该映射可以通过“爬寻(crawl)”web(即,万维网) 来标识每一网页的关键词来生成。为爬寻web,搜索引擎服务可使用根网页列 表来标识能通过这些根网页访问的所有网页。任何特定网页的关键词可使用各 种公知信息检索技术来标识,如标识标题行的文字、在网页的元数据中提供的 文字、突出显示的文字等等。搜索引擎服务基于网页的关键词与查询的文字匹 配得如何来标识可能与搜索请求相关的网页。搜索引擎服务随后将到所标识的 网页的链接以基于可以按照其与查询的相关度、流行度、重要性和/或某一其它 度量来确定的排名的顺序显示给用户。

用于网页排名的三种公知技术是PageRank(页排名)、HITS(“引起超链 接的主题搜索”)和DirectHIT(直接HIT)。PageRank基于网页将具有到重要 网页的链接(即,“引出链接”)的原理。因而,网页重要性基于链接到该网页 (即,“引入链接”)的其它网页的数量与重要性。用简单形式,网页之间的链 接可以由邻接矩阵A表示,其中Aij表示从网页i到网页j的引出链接的数量。 网页j的重要性分数wj可以如以下等式表示:

wj=∑iAijwi

该等式可以通过基于下面的等式的迭代计算来求解:

ATw=w

其中w是网页的重要性分数的向量,并且是AT的主本征向量。

HITS技术另外基于具有到其它重要网页的许多链接的网页本身可能是重 要的原理。因而,HITS将网页的“重要性”分成两个相关属性:“中心(hub)” 和“权威(authority)”。“中心”是由网页所链接到的网页的“权威”分数 来测量的,而“权威”是由链接到该网页的网页的“中心”分数测量的。与独 立于查询来计算网页重要性的PageRank相比,HITS基于结果的网页和通过跟 随引入和引出链接而与结果的网页相关的网页来计算重要性。HITS向搜索引 擎服务提交查询并且使用结果的网页作为初始网页集。HITS向该集合添加作 为引入链接的目的地的那些网页和作为结果的网页的引出链接的源的那些网 页。HITS随后使用迭代算法计算每一网页的权威和中心分数。权威和中心分 数可以由以下等式来表示:

a(p)=Σqph(q)h(p)=Σpqa(q)

其中A(p)表示网页p的权威分数而h(p)表示网页p的中心分数。HITS使 用邻接矩阵A来表示这些链接。邻接矩阵由以下等式表示:

向量a和h分,于该集合中所有网页的权威和中心分数,并且可以用 以下等式表示:

a=ATh和h=Aa

因而,a和h是矩阵ATA和AAT的本征向量。HITS还可被修改来将按访 问数量测量的网页的流行度计算在内。基于对点进数据的分析,每当用户 从网页i移动至网页j时就增加邻接矩阵的bij

尽管这些用于基于对链接的分析来对网页进行排名的技术可能是非常有 用的,但它们易受到“链接作弊”的影响。“作弊”一般指为不合理地增加网 页或网站的流行度或重要性而采取的蓄意动作。在链接作弊的情形中,作弊者 可以操纵链接以不合理地增加网页的重要性。例如,作弊者可通过向作弊者的 网页添加引出链接来增加网页的中心分数。一种用于添加引出链接的常见技术 是创建现有链接目录的副本以快速创建非常大的引出链接结构。作为另一个示 例,作弊者可向有用信息的网页提供到作弊网页的隐藏链接。当许多网页指向 该有用信息时,作弊网页的重要性也间接增加了。作为另一个示例,诸如博客 和web目录等许多网站允许访问者公布链接。作弊者可以公布到其作弊网页的 链接以直接或者间接地增加作弊网页的重要性。作为另一个示例,一组作弊者 可建立链接交换机制,其中它们的网站指向彼此以增加作弊者网站的网页重要 性。

web作弊,具体而言是是链接作弊,向依赖于web数据的各种技术提出了 问题。例如,部分地基于网页的流行度或重要性对搜索结果进行排序的搜索引 擎服务可能因为作弊而不合理地将作弊网页排得很高。搜索结果的网页的正确 排名对于搜索引擎服务是非常重要的。如果无论出于什么原因(例如,链接作 弊)搜索引擎服务的用户察觉到搜索结果的网页排名与他们的重要性或相关性 概念不符,则用户可能转到不同的搜索引擎服务。因为搜索引擎服务的收入与 用户数量紧密相关,所以在搜索结果的网页进行排名方面的较差表现会导致搜 索引擎服务的收入损失。

概述

提供了一种基于对链接的时间分析来确定具有文档之间的链接的文档的 时间重要性的方法和系统。时间排名系统在各个快照时刻收集指示文档之间的 链接的链接信息或快照。时间排名系统通过将从当前快照(即,具有最近的快 照时间)中导出的文档的当前重要性和从过去的快照中导出的文档的历史重要 性计算在内来计算文档的当前时间重要性。为了计算网页的当前时间重要性, 时间排名系统合计网页对于每一个快照的重要性。时间排名系统可向搜索引擎 服务提供文档的时间重要性,以使得该搜索引擎服务能够至少可以部分地基于 文档的时间重要性来对其进行排名。

提供本概述是为了以简化的形式介绍将在以下详细描述中进一步描述的 一些概念。该概述不旨在标识所要求保护的主题的关键特征或必要特征,也不 旨在用于帮助确定所要求保护的主题的范围。

附图简述

图1是示出web图的一部分的示图。

图2是示出一个实施例中的时间排名系统的组件的框图,该系统基于随时 间取得的web图的快照来对网页进行排名。

图3是示出某些实施例中的时间排名系统的计算时间重要性组件的高级 处理的流程图。

图4是示出某些实施例中的时间排名系统的计算时间重要性组件的低级 处理的流程图。

详细描述

提供了一种基于对链接的时间分析来确定具有文档之间的链接的文档的 时间重要性的方法和系统。在某些实施例中,时间排名系统在各个快照时刻收 集指示文档(或者更一般地,对象)之间的链接的链接信息或快照。例如,当 文档是网页时,web爬行器可爬寻web以标识网页和网页之间的链接。爬行器 可将网页和链接表示为具有顶点和边的web图。web图对应于web在被爬寻时 的快照,这个时间被称为web的快照时刻。时间排名系统通过将从当前快照 (即,具有最近的快照时刻)中导出的文档的当前重要性和从过去的快照中导 出的文档的历史重要性计算在内来计算文档的当前时间重要性。例如,时间排 名系统可使用页面排名算法来计算网页对于每一个快照的重要性。术语“时间 重要性”指的是基于多个快照的重要性分数,而术语“重要性”指的是基于单 个快照的重要性分数。为了计算网页的当前时间重要性,时间排名系统合计该 网页对于每一个快照的重要性。因为时间排名系统基于当前快照和一个或多个 过去的快照来计算文档的当前时间重要性,所以其当前重要性通过在当前快照 中引入的链接作弊来增加的文档将由于其历史上较低的总体重要性(基于过去 的快照)而具有较低的当前时间重要性。

在某些实施例中,时间排名系统提供加权因子,它可用于指定从当前快照 中导出的当前重要性和从过去的快照中导出的历史重要性对当前时间重要性 的相对贡献。例如,可将加权因子设为零和一之间的值。值零指示当前重要性 对当前时间重要性没有贡献并且当前时间重要性是历史重要性。值二分之一指 示当前重要性和历史重要性对当前时间重要性的贡献相等。值一表指示历史重 要性对当前时间重要性没有贡献并且当前时间重要性退化为当前重要性。加权 因子可基于从当前快照中导出的当前重要性反映网页的实际重要性的准确程 度来设置。

在某些实施例中,时间排名系统提供衰减因子,它用于随着时间减少快照 对网页的当前时间重要性的相对贡献。当应用衰减因子时,来自快照的贡献随 着收集到其他快照而减少。例如,衰减因子可指示从一个快照时刻到下一个快 照时刻快照的贡献减少50%。次新快照的贡献可能是其重要性的50%,第三新 的快照的贡献可能是其重要性的25%,第四新的快照的贡献可能是其重要性的 12.5%,以此类推。

在某些实施例中,时间排名系统在为每一个快照确定适当的衰减因子时应 用机械模型。通过使用机械模型,时间排名系统考虑当前快照的当前重要性以 具有动力并考虑过去的快照的历史重要性以具有阻力。从所有快照中导出的合 力是由增强因子调整的动力减去由阻尼因子调整的阻力。机械模型类似于物理 运动的力学,其中对其施加动力的物体也可具有阻力。物体上的合力是动力减 去阻力。根据有关物理运动的牛顿第二定律,物体的力是它的质量乘以它的加 速度(例如,速度的导数)。对时间重要性的计算应用类似的定律,从所有过 去的快照中导出的合力是网页的“质量”乘以网页的历史重要性的“加速度”。 由此可以认为历史重要性是“速度”。网页的“质量”可表示网页的固有质量。 在某些实施例中,假设所有网页具有相同的质量。网页的“加速度”是历史重 要性的变化速率。如将在以下更详细描述的,通过将网页的合力(即,由增强 因子调整的动力和由阻尼因子调整的阻力)设为网页的质量乘以网页的加速 度,可以获得网页的速度或时间重要性的解。该解提供一个公式,通过该公式 可以从增强因子和阻尼因子中导出加权因子和衰减因子。在概念上,阻尼因子 表示历史重要性将对当前时间重要性作出多少贡献,而增强因子是不影响网页 的相对时间重要性的常量。阻尼因子(对于所有快照可以相同)可提供更直观 的模型以理解控制时间排名系统的参数。

时间排名系统基于当前web图(即,快照)和先前web图中所包含的历 史重要性两者来计算网页的时间重要性分数。时间排名系统通过以下等式来表 示网页的当前时间重要性:

TRk(i)=(1-β)Hk(i)+βPRk(i)(1)

其中k表示web图G的快照数量,TRk(i)表示文档i在快照时刻k的当前时间重 要性分数,PRk(i)表示从web图Gk中导出的文档i在快照时刻k的当前重要性 分数,Hk(i)表示从web图G1,G2,…,Gk-1中导出的文档i的历史重要性分数,β 表示快照时刻k的当前重要性分数的加权因子,而1-β表示快照时刻1至k-1 的历史重要性分数的加权因子。加权因子β可基于所感知到的当前快照的可靠 性来设置。如果β等于1,则认为当前快照是完全可靠的并且忽略过去的快照。 时间排名系统如下表示历史重要性分数:

Hk(i)=Σt=1k-1γtPRt(i)---(2)

其中γt表示衰减因子,其指示来自每个快照的重要性对历史重要性分数有 多少贡献。一般而言,快照越早,它应当对历史重要性分数作贡献的重要性的 量就越少。时间排名系统可如下组合公式1和2:

TRk(i)=(1-β)Σt=1k-1γtPRt(i)+βPRk(i)---(3)

时间排名系统可使用“机械模型”来导出用于控制衰减和加权因子的参数。 时间排名系统假设重要性对应于物体的速度。如果页面i获得当前快照Gt的重 要性分数PRt(i),则时间排名系统将向该页面的虚力Ft(i)添加相应的动力。时 间排名系统假设时间重要性分数TRt(i)的衰减是对虚力有负作用的阻力。时间 排名系统如下表示该模型:

Ft(i)=-λTRt(i)+ηPRt(i)(4)

其中η(η>0)表示动力的增强常数而λ(λ≥0)表示衰减因子。时间排名系统如 下表示虚力:

Ft(i)=m(i)dTRt(i)dt---(5)

其中m(i)是网页i的固有质量,它具有与质量相似的意义。在概念上,虚力被 表示为质量乘以加速度。时间排名系统将公式4和5组合为如下的一阶常微分 公式:

dTRt(i)dt+λm(i)TRt(i)=ηm(i)PRt(i)---(6)

公式6的通解如下:

TRk(i)=e-λm(i)k[0kηm(i)PRt(i)e-λm(i)tdt+C0]---(7)

其中C0是整数常数。如果假设所有网页在开始(t=0)时具有相同的初始重要性 分数,则TR0(i)=1N,其中N是web图中的网页数量。给出该假设,则解可如 下表示:

TRk(i)=1Ne-λm(i)k+ηm(i)0kPRt(i)e-λm(i)(k-t)dt---(8)

因为web图数据是相对于时间的离散快照,所以时间排名系统将公式8转换成 其离散形式,如下:

TRk(i)=1Ne-λm(i)k+ηm(i)Σt=1kPRt(i)e-λm(i)(k-t)---(9)

可重新制定公式9以将初始重要性分数、历史重要性分数和当前重要性分 数分开,如下:

TRk(i)=1Ne-λm(i)k+ηm(i)Σt=1k-1PRt(i)e-λm(i)(k-t)+ηPRk(i)m(i)---(10)

公式10右侧的第一项表示与网页i相关的常数并且表示初始重要性分数; 第二项表示网页i在由Hk(i)表示的过去的web图中的重要性分数的线性组合; 而第三项表示网页i在当前web图中的当前重要性分数。如果忽略常数,则衰 减和加权因子可以如下表示:

γt=ηm(i)-ηe-λm(i)(k-t)β=ηm(i)---(11)

加权因子λ(λ≥0)表示历史重要性分数对当前时间重要性分数作贡献的 权重。因子m(i)是每个网页的固有质量。在一个实施例中,时间排名系统可将 m(i)设为对于所有网页都相同。如果固定λ和m(i),则增强常数η不影响页面 的排名。为确保加权因子在零和一之间,时间排名系统将η设为大于零且小于 m的值。

图1是示出web图一部分的示图。web图通过爬寻web并且标识所遇到 的网站的网页上的引出链接来生成。在该示例中,web图100的一部分包含表 示五个网站的顶点101-105和表示引出链接的顶点之间的边。例如,顶点101 和103之间的边表示由顶点101表示的网站到由顶点103表示的网站的引出链 接。因而,由顶点103表示的网站是由边表示的引出链接的目标。该同一边还 是到由顶点103表示的网站的引入链接。因而,由顶点101表示的网站是由该 边表示的引入链接的源。时间排名系统可使用每一个网站都被表示为矩阵的行 与列的邻接矩阵来表示web图。行和列中的非零项可指示由行表示的网站具有 到由列表示的网站的引出链接。时间排名系统可使用包括稀疏矩阵存储技术在 内的各种技术来表示web图。时间排名系统还可存储从一个快照时刻到下一个 快照时刻的web图之间的差异而不是多次存储整个web图。

由于频繁地将新网页添加到web且频繁地从web中移除旧网页,因此每 个快照将有可能具有不同数量的网页。时间排名系统可通过维护所有快照中所 有网页的聚集列表来解决不同快照中不同数量的网页。在计算一个快照的网页 的重要性分数时,时间排名系统为聚合列表中的那些不在快照中的网页添加为 零的重要性分数。以此方式,表示每一个快照的重要性分数的向量将具有相同 的长度。

图2是示出了一个实施例中的时间排名系统的组件的框图,该系统基于随 时间取得的web图的快照来对网页进行排名。时间排名系统210经由通信链路 240来连接至网站服务器220和用户计算设备230。时间排名系统可包括web 爬行器211、创建web图组件212、web图存储213和搜索索引存储214。web 爬行器爬寻网站服务器的网页以标识网页和网页之间的链接。web爬行器可生 成关键词到网页的映射并且将该映射存储在搜索索引存储中。web爬行器还可 向创建web图组件提供网页和链接的指示,创建web图组件生成对应于web 快照的web图的表示。创建web图组件可通过存储在web图存储中的邻接矩 阵来表示web图。可调度web爬行器以周期性地或者在自组织(ad hoc)的基 础上爬寻网页。在任一种情况下,web爬行器将快照时刻与每一个快照相关联。 尽管时间排名系统在某些实施例中假设快照时刻是等间隔的,但本领域技术人 员将理解,快照时刻不必是等间隔的。在这种情况下,对快照的阻尼因子或者 衰减因子的计算可考虑其相对于当前快照时刻的实际快照时刻。

时间排名系统包括计算时间重要性组件215、计算重要性组件216、时间 重要性存储250和重要性存储251。计算时间重要性组件基于从当前快照中导 出的重要性分数和从过去的快照中导出的历史重要性来计算每一个网页的当 前时间重要性分数。计算时间重要性组件调用计算重要性组件来基于单个快照 计算网页的重要性分数。计算重要性组件可实现诸如页面排名算法或者中心和 权威算法等常规算法并且将每一个快照的重要性分数存储在重要性存储中。计 算时间重要性组件可将时间重要性分数存储在时间重要性存储中以供在对网 页进行排名时使用。

时间排名系统还可包括搜索引擎组件217、找出匹配网页组件218和排列 结果组件219。用户计算设备的用户可向搜索引擎组件提交搜索请求。搜索引 擎组件调用找出匹配网页组件来找出匹配搜索请求的网页。找出匹配网页组件 可使用搜索索引来标识匹配的网页。搜索引擎组件随后调用排列结果组件来基 于搜索结果的网页的时间重要性存储中的时间重要性分数来对网页进行排名。 例如,排列结果组件可将基于网页与搜索请求的相关性的相关性分数与由时间 排名系统生成的当前时间重要性分数组合以提供总排名分数。搜索引擎组件随 后可基于排名分数来对搜索结果的网页进行排名。

在其上实现时间排名系统的计算设备可包括中央处理单元、存储器、输入 设备(例如,键盘和定点设备)、输出设备(例如,显示设备)和存储设备(例 如,盘驱动器)。存储器和存储设备是可以用实现该系统的计算机可执行指令 来编码的计算机可读介质,这意味着包含该指令的计算机可读介质。此外,指 令、数据结构和消息结构可被存储或经由诸如通信链路上的信号之类的数据传 送介质发送。可使用各种通信链路,如因特网、局域网、广域网、点对点拨号 连接、蜂窝电话网络等。

时间排名系统的各实施例可在各种操作环境中实现或者结合这些操作环 境使用,这些操作环境包括个人计算机、服务器计算机、手持式或膝上型设备、 多处理器系统、基于微处理器的系统、可编程消费电子产品、数字照相机、网 络PC、小型计算机、大型计算机、蜂窝电话、个人数字助理、智能电话、个 人计算机、可编程消费电子产品、包括任何上述系统或设备中的任一种的分布 式计算环境等等。

时间排名系统可以在诸如程序模块等由一个或多个计算机或其他设备执 行的计算机可执行指令的通用上下文中描述。一般而言,程序模块包括执行特 定任务或实现特定抽象数据类型的例程、程序、对象、组件、数据结构等等。 通常,程序模块的功能可以在各个实施例中按需进行组合或分布。例如,一单 独的计算系统可爬寻web并生成web图。另一计算系统可提供使用时间重要 性分数来排列搜索结果的搜索引擎。

图3是示出某些实施例中的时间排名系统的计算时间重要性组件的高级 处理的流程图。调用该组件来基于对多个web快照的分析来计算时间重要性分 数。在框301,该组件计算网页对于每一个快照的重要性分数。例如,该组件 可使用页面排名算法或者中心和权威算法。如上所述,该组件可将每一个快照 的重要性分数保存在重要性存储中以避免在每次收集新快照时重新计算重要 性分数。在框302-305,该组件循环地将过去重要性分数的贡献合计成每一个 网页的历史重要性分数。在框302,该组件初始化用于跟踪快照的变量。在框 303,该组件递增该变量以选择下一个快照。在判定框304,如果已经选择了所 有快照,则该组件在框306继续,否则该组件在框305继续。在框305,该组 件基于加权因子来将网页对于所选快照的重要性分数累计成历史重要性分数。 该组件随后循环到框303以选择下一个快照。在框306,该组件为每一个网页 生成作为网页的历史重要性分数和网页的当前重要性分数的加权组合的当前 时间重要性分数。该组件随后完成。

图4是示出某些实施例中的时间排名系统的计算时间重要性组件的低级 处理的流程图。在框401,该组件计算网页对于当前快照的重要性分数。在框 402,该组件根据等式10的第一项来初始化每一个网页的时间重要性分数。在 框403-409,该组件根据等式10的第二项基于过去的快照来循环计算历史重要 性分数。在框403,该组件选择从最老的快照开始的下一个快照。在判定框404, 如果已经选择了所有过去的快照,则该组件在框410继续,否则该组件在框405 继续。在框405-409,该组件循环计算每一个网页的历史重要性分数。在框405, 组件初始化网页的索引。在框406,该组件选择所选快照的下一个网页。在判 定框407,如果已经选择了所有网页,则该组件循环到框403以选择下一个快 照,否则该组件在框408继续。在框408,该组件计算根据所选网页在所选快 照中的的重要性分数来计算该网页的加权重要性分数。在框409,该组件将加 权的重要性分数与最后一个快照的历史重要性分数组合以提供所选快照的所 选网页的历史重要性分数。该组件随后循环到框406以选择所选快照的下一个 网页。在框410-414,该组件循环计算当前快照的每一个网页的加权重要性分 数并且根据等式10的第三项将该加权重要性分数加到网页的历史重要性分数。 在框410,该组件初始化网页的索引。在框411,该组件递增索引以选择下一 个网页。在判定框412,如果已经选择了当前快照的所有网页,则该组件完成, 否则该组件在框413继续。在框413,该组件基于如在框401中计算的所选网 页的重要性分数来计算所选网页的加权重要性分数。在框414,该组件将如在 框409中计算出的所选网页的历史重要性分数和加权重要性分数组合成所选网 页的当前时间重要性分数。该组件然后循环到框411以选择当前快照的下一个 网页。

尽管用对结构特征和/或方法动作专用的语言描述了本主题,但可以理解, 所附权利要求书中定义的主题不必限于上述具体特征或动作。相反,上述具体 特征和动作是作为实现权利要求的示例形式公开的。本领域的技术人员将理解 解,时间重要性分数可在使用文档重要性的任何应用中使用。例如,文档可以 是专利而链接可以是对其它专利的引用,或者文档可以是学术文章而链接可以 是对其它学术文章的引用。时间重要性分数还可用于基于作者的作品的重要性 来评定作者。因此,本发明只由所附权利要求来限制。

去获取专利,查看全文>

相似文献

  • 专利
  • 中文文献
  • 外文文献
获取专利

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号