用于提供电视收视率的有效和准确估计的方法和系统

摘要

本发明公开了一种通过包括多个计算机的分布式计算机系统估计电视收视率的有效和准确估计的方法。所述方法包括：在分布式计算机系统接收来自客户端的查询；根据预定分片函数动态地选择一个或多个计算机；在每个选择的计算机处，确定满足查询的合格事件记录的计数；汇总通过选择的计算机确定的合格事件记录的相应计数；将所汇总的合格事件记录的计数统计地预测为分布式计算机系统上合格事件记录的估计总计数；以及将合格事件记录的估计总计数返回给发出请求的客户端。

说明书

技术领域

本公开实施方式一般地涉及电视收视率，具体地涉及用于提供对 电视收视率的有效和准确估计的系统和方法。

背景技术

现在，人们可以通过不同的通信信道（例如卫星、电缆、电话线 和因特网）从不同的供应商得到相同的电视内容。通信信道的选择常 常有很多地理和人口统计的考虑。例如，对于农村地区的家庭而言， 卫星接收器可能是接收电视信号的最常用装置。但是对于大城市地区 的家庭而言，利用电缆连接或通过广播（OTA）天线来接收电视信号 可能更常见。虽然很多人仍然通过电视来观看电视节目，但是年轻观 众会更多地选择通过耦接到因特网的计算机、甚至支持3G/4G无线通信 的智能手机来观看电视节目。由于存在用于接收电视节目的多样化通 信信道，在一个大的人口水平上（例如在全国水平）对特定电视节目 提供对收视率的有效、准确估计更具挑战性。

发明内容

根据下述一些实施方式，公开了一种用于提供电视收视率的有效 和准确估计的计算机实施的方法。所述方法在包括多个计算机的分布 式计算机系统处实施，每个计算机具有一个或多个处理器和存储多个 事件记录的存储器，每个事件记录包括预定时间间隔。所述方法包括： 接收来自客户端的查询，其中所述查询包括一个或多个预定标准，并 且所述预定标准中的一个指定预定时间段；通过将所述一个或多个预 定标准中的至少一个应用于预定分片函数，来动态地选择一个或多个 计算机，其中在所选择的可能满足所述一个或多个预定标准的计算机 上至少有预定数量的候选事件记录；在每个所选择的计算机处：识别 所述计算机的存储器中存储的多个候选事件记录；在所识别的候选事 件记录中确定满足所述一个或多个预定标准的合格事件记录的计数， 其中每个合格事件记录具有和与所述查询相关联的所述预定时间段至 少部分地重叠的预定时间间隔；汇总通过所选择的计算机确定的合格 事件记录的相应计数；将所汇总的合格事件记录的计数预测为所述分 布式计算机系统上合格事件记录的估计总计数，其中所述合格事件记 录的估计总计数具有相关联的置信等级；以及将查询结果返回给发出 请求的客户端，其中所述查询结果包括所述合格事件记录的估计总计 数及其相关联的置信等级。

根据下述一些实施方式，公开了一种用于提供电视收视率的有效 和准确估计的分布式计算机系统，所述分布式计算机系统包括多个计 算机，每个计算机具有一个或多个处理器和存储多个事件记录的存储 器，每个事件记录包括预定时间间隔。所述一个或多个程序包括指令 用于：接收来自客户端的查询，其中所述查询包括一个或多个预定标 准，并且所述预定标准中的一个指定预定时间段；通过将所述一个或 多个预定标准中的至少一个应用于预定分片函数，来动态地选择一个 或多个计算机，其中在所选择的可能满足所述一个或多个预定标准的 计算机上至少有预定数量的候选事件记录；在每个所选择的计算机处： 识别所述计算机的存储器中存储的多个候选事件记录；在所识别的候 选事件记录中确定满足所述一个或多个预定标准的合格事件记录的计 数，其中每个合格事件记录具有和与所述查询相关联的所述预定时间 段至少部分地重叠的预定时间间隔；汇总通过所选择的计算机确定的 合格事件记录的相应计数；将所汇总的合格事件记录的计数预测为所 述分布式计算机系统上合格事件记录的估计总计数，其中所述合格事 件记录的估计总计数具有相关联的置信等级；以及将查询结果返回给 发出请求的客户端，其中所述查询结果包括所述合格事件记录的估计 总计数及其相关联的置信等级。

根据下述一些实施方式，公开了一种非暂时性计算机可读存储介 质，所述非暂时性计算机可读存储介质存储用于由计算机系统的一个 或多个处理器执行的一个或多个程序，所述计算机系统用于提供电视 收视率的有效和准确估计。所述一个或多个程序包括指令用于：接收 来自客户端的查询，其中所述查询包括一个或多个预定标准，并且所 述预定标准中的一个指定预定时间段；通过将所述一个或多个预定标 准中的至少一个应用于预定分片函数，来动态地选择一个或多个计算 机，其中在所选择的可能满足所述一个或多个预定标准的计算机上至 少有预定数量的候选事件记录；在每个所选择的计算机处：识别所述 计算机的存储器中存储的多个候选事件记录；在所识别的候选事件记 录中确定满足所述一个或多个预定标准的合格事件记录的计数，其中 每个合格事件记录具有和与所述查询相关联的所述预定时间段至少部 分地重叠的预定时间间隔；汇总通过所选择的计算机确定的合格事件 记录的相应计数；将所汇总的合格事件记录的计数预测为所述分布式 计算机系统上合格事件记录的估计总计数，其中所述合格事件记录的 估计总计数具有相关联的置信等级；以及将查询结果返回给发出请求 的客户端，其中所述查询结果包括所述合格事件记录的估计总计数及 其相关联的置信等级。

附图说明

当结合附图时，作为本发明的各个方面的以下详细描述的结果， 将更加清楚地理解本发明的上述实施方式以及附加实施方式。全部附 图中相同的附图标记表示对应的部件。

图1A是示出根据一些实施方式的分布式电视内容递送系统的方框 图，所述分布式电视内容递送系统包括用于向家庭递送电视信号的多 个通信信道以及用于估计电视收视率的分布式测量服务器。

图1B是示出根据一些实施方式的分布式测量服务器的组件的方框 图，所述分布式测量服务器用于从多个源收集电视收视计量数据并向 发出请求的客户端提供电视收视率的估计。

图2是示出根据一些实施方式的作为分布式测量服务器的根/混合 物/叶子分片成员运行的计算机的组件的方框图。

图3A是示出根据一些实施方式的电视收视计量数据如何通过分布 式测量服务器的根分片从数据源迁移到根分片选择的一个或多个叶分 片的方框图。

图3B是示出根据一些实施方式的数据源使用的用于组织电视收视 计量数据的数据结构的方框图。

图3C是示出根据一些实施方式的分布式测量服务器使用的用于存 储电视收视计量数据的数据结构的方框图。

图3D是示出根据一些实施方式的分布式测量服务器使用的用于存 储家庭人口统计数据的数据结构的方框图。

图3E是示出根据一些实施方式的分布式测量服务器使用的用于存 储电视广播机构信息的数据结构的方框图。

图4A是示出根据一些实施方式的分布式测量服务器如何处理数据 源提供的进入电视收视计量数据的流程图。

图4B是示出根据一些实施方式的分布式测量服务器如何将来自客 户端的查询应用于电视收视计量数据并将查询结果返回发出请求的客 户端的流程图。

图4C是示出根据一些实施方式的分布式测量服务器的叶子分片如 何识别满足查询的电视收视计量数据的流程图。

具体实施方式

全国市场的电视收视情况可以是非常碎片化的。在一些实施方式 中，电视收视预测系统从各种电视内容提供者（例如有线和卫星公司， 通过广播机构和因特网流送站）接收原始收视数据。电视收视预测系 统针对不同的地理人口统计组（即，特定观众人口统计、地理区域和/ 或两种特性的某个组合）汇总来自每个不同内容提供者的原始数据， 并在有重要统计学意义的水平对特定组计算收视占有率信息。例如， 电视收视预测系统在有足够数据时（例如在城市地区）计算每分钟占 有率信息以及在没有足够数据时计算每小时占有率信息，以可靠地确 定每分钟占有率信息（例如在对特定服务/内容提供者几乎没有订户的 人口稀少地区）。然后，为了对比来自完全不同的提供者的信息所覆 盖的区域大的区域产生可靠的占有率信息，电视收视预测系统通过加 权不同成分而将来自完全不同的内容提供者的占有率信息组合。在一 些情况下，收视占有率信息覆盖相同的地理人口统计组（例如来自卫 星提供者和电缆提供者的用于相同地理区域的收视信息）。而且，通 过将关于不同的内容提供者的收视占有率信息进行组合并加权，变得 可以对任何组都不能单独充分表示的地理人口统计组生成可靠的信息 （例如，关于电缆提供者A和卫星提供者B的占有率信息可能不单独包 括关于相同的地理人口统计组X的充分信息，但是它们组合以后包括）。

图1是示出根据一些实施方式的分布式电视内容递送系统的方框 图，所述分布式电视内容递送系统包括用于向家庭递送电视信号的多 个通信信道。在一些实施方式中，一个或多个电视广播机构/电视计量 数据提供者102收集在一个或多个账户信息数据库132中保持的用于特 定订户家庭180的账户信息。该信息132被分布式测量服务器150访问， 分布式测量服务器150响应于查询而汇总和分析信息，以对地理人口统 计组（例如通过年龄、性别和地理区域对观众的不同组合）范围的一 个或多个电视节目确定电视收视率。在一些实施方式中，如图1中所示， 有多于一个的电视收视计量数据的提供者，每个计量数据提供者监视 全部电视人口的特定地理和人口统计部分。因此，在通过不同提供者 收集的电视收视计量数据集合之间有差异。为了利用这些数据集合来 产生国家或区域电视收视率，分布式测量服务器150可将某些权重应用 于来自不同提供者的电视收视计量数据，并将它们“混合”为一个用 于特定人口的一个电视节目的电视收视率。为了完成该任务，分布式 测量服务器具有用于存储节目模块以及进行此估计所需要的数据的存 储器212。下面结合图1B至图4提供分布式测量服务器和相关节目模块 及数据的更详细描述。

在一些实施方式中，在数据库132中保持其账户和收视信息的家庭 180是电视收视小组（panel）中的参与者，电视收视小组已经同意可以 收集、汇总和分析它们的电视观看、账户和人口统计信息，以允许分 布式测量服务器150能够对特定家庭180确定电视观看数据。账户信息 数据库132一般包括用于每个参与者家庭的账户号134、名称136和计费 地址138。在一些实施方式中，账户信息132还包括物理地址140，诸如 家庭的住宅地址和/或与家庭180使用的一个或多个具有因特网能力的 装置相关联的IP地址126，以一般性地访问和观看流电视内容和/或基于 因特网的服务。在一些情况下，家庭180具有固定IP地址126，在这种情 况下固定IP地址126与数据库132中的家庭账户相关联。在其他情况下， 家庭180具有动态分配的IP地址，动态分配的IP地址可以在有规律的基 础上（例如每次家庭成员“拨号”或者向因特网服务提供者128（ISP） 进行新连接时）改变。在这种情况下，广播机构/提供者102跟踪对家庭 IP地址126的改变并因此更新数据库132中的记录。在一些情况下，账户 信息数据库132包括与每个家庭相关联的账户资料144。账户资料144可 包括表征家庭成员的一个或多个人口统计参数，包括但不限于家庭成 员的数量以及至少一个家庭成员的年龄、性别、教育程度、收入和职 业。如下所述，账户资料144中的信息用于响应于客户端请求而查询收 视数据，或者在根据收集的收视数据预测电视收视率时将与一个提供 者收集的收视数据相关联的偏差最小化。在一些情况下，账户信息数 据库132包括电视收视数据142，电视收视数据142表示与每个账户相关 联的家庭180的电视观看活动。例如，电视观看活动可包括关于家庭观 看的每个节目的信息，对于每个节目而言，包括节目的名称和描述、 播放节目的频道、观看的日期/时间等等。在其他实施方式中，数据库 132中保存的电视观看活动仅包括被观看至少阈值时间量（例如1分钟 或5分钟）的节目以及节目的开始时间和节目的结束时间。在一些实施 方式中，所跟踪的观看活动仅包括优良（premium）内容。电视收视数 据142可包括从家庭收集的原始数据样本，诸如收集数据样本时的日期 和时间以及关于收集数据样本时家庭中广播的电视节目的信息；或者 预处理数据样本，诸如家庭中的电视节目的广播持续时间。如图1中所 示，数据库132可包括从多个电视广播机构（或电视计量数据提供者） 102收集的电视收视数据。如果来自不同源的数据的格式不同于数据库 132使用的格式，则可以向它们应用数据预处理过程。本申请通篇中可 互换地使用像“收视数据”和“计量数据”这样的术语。

在一些实施方式中，电视广播机构只负责广播电视信号，同时分 立的电视计量数据提供者负责从家庭收集关于不同电视节目的电视计 量数据。在一些其他实施方式中，电视广播机构和电视计量数据提供 者作为负责广播电视信号和收集电视计量数据两者的单个实体工作。 但是本申请的实施方式适用于任何配置。为简单起见，本申请的其余 部分将使用术语“电视计量数据提供者”来表示两种实体。根据该术 语出现的上下文，本领域技术人员将理解它指的是哪种实体。

如图1中所示，电视计量数据提供者102可以通过电缆112、通过从 卫星104的传输、或者通过通信网络130（例如因特网）上的流送向家 庭180传输电视节目。在卫星传输106的情况下，家庭180具有接收信号 的接收器天线108。在家庭180中，存在处理或解码进入的电视信号的 接收器或转换器110。解码的电视信号被传输给机顶盒（STB）117，STB 117使得家庭成员118能够控制在电视116上显示什么内容。在一些实施 方式中，接收器/转换器110与STB117组合。通常，诸如成员118-1或 118-2的家庭成员通过远程控制装置来控制STB117。在一些实施方式 中，通过电话线114，在电视计量数据提供者102与STB117之间存在附 加通信。例如，STB117可以提供关于什么电视节目正在被观看的信息， 或可以从电视计量数据提供者102接收关于交互式电视节目的进一步 信息。电视计量数据提供者102处理来自STB117的关于家庭成员的观 看活动的信息，并将处理的信息存储在数据库132中。

在一些实施方式中，家庭成员的观看活动由接收器/转换器110识 别，并通过STB117传输回电视计量数据提供者102，STB117通过有线 或无线家庭路由器120连接到通信网络130（例如因特网）。在其他实 施方式中，STB117能够通过评估从接收器/转换器110接收的信号确定 观看的节目。在这些实施方式中，STB117再次经由家庭路由器120将 观看信息（例如节目、频道、日期/时间等等）传输给电视计量数据提 供者102。因为通过家庭路由器120传输观看信息，所以家庭路由器120 的IP地址126也连同观看信息一起传输给电视计量数据提供者102。在一 些实施方式中，在周期性的基础上（例如从一小时一次到一天一次甚 至一周一次）将IP地址126和/或观看信息传输给电视计量数据提供者 102。在两次连续传输之间，将数据存储在STB117中。如上所述，在 一些替选实施方式中，STB117通过电话线114将数据传输给电视计量 数据提供者102。在这些实施方式中，STB117能够从路由器120检索IP 地址126，并和观看数据一起传输它。

实际的电视节目信号一般通过卫星104、通过电缆112、或者经由 地面电视传输（即传统的电视广播）来传输。在一些实施方式中，电 视节目通过诸如因特网的通信网络130流送。在这些实施方式中，可以 通过直接连接到家庭路由器120（图1中未示出）的计算机103、STB117 或接收器/转换器110来执行选择电视节目的处理。家庭路由器120是从 家庭180到因特网的网关。在家庭180内部，路由器120连接到STB117， 并且在一些情况下连接到多个计算机103、智能电话或数字音频播放器 124、或游戏控制台122，诸如XBOX、PLAYSTATION或WII。路由器 120通过向家庭路由器120分配IP地址126的因特网服务提供者128连接 到通信网络130。

家庭180中的计算机103可以访问因特网以执行多种活动，诸如观 看通过通信网络130、因特网服务提供者128以及家庭路由器120从电视 计量数据提供者102流送的电视节目、购物、观看在线视频（例如在 YouTube上）、玩在线游戏、参与在线社交网络、或从事很多其他活动。 电视节目观看活动由电视计量数据提供者102记录在数据库132中，并 通过家庭180的IP地址126跟踪，因为它容易获得，并且是独特的标识符 （至少在特定时间点）。本领域技术人员应当认识到，在账户信息数 据库132中识别的数据都可以在单个数据库中找到，或者根据实施方式 分布到不同数量的数据库。

在一些实施方式中，为了接收电视计量数据提供者收集的很多家 庭的计量数据以及他们的人口统计数据，将分布式测量服务器150连接 到电视计量数据提供者102或账户信息数据库132或者这两者。在一些 其他实施方式中，分布式测量服务器150经由通信网络130、ISP128以 及家庭路由器120接收来自家庭STB117的计量数据。如下所述，分布 式测量服务器150为了响应于来自其客户端的查询而估计电视收视率 并将这样的收视率信息提供给发出请求的客户端，管理它自身的计量 和人口统计数据的副本。如下详细所述，分布式测量服务器150将一组 标准应用于它的存储器中存储的电视计量数据，以确定范围例如从小 于一秒到几分钟的短时间帧中的客户端请求的收视率的合理估计。在 一些实施方式中，分布式测量服务器150向来自不同提供者的数据分配 不同的权重，以消除或减少关联的偏差，权重是一个或多个地理人口 统计因素（包括位置、性别、年龄、收入、教育等等）的函数。

图1B是示出根据一些实施方式的用于从诸如STB117和电视计量 数据提供者102的多个源收集电视收视计量数据并向发出请求的客户 端170提供电视收视率的估计的分布式测量服务器150的组件的方框 图。为了处理大量电视收视数据，分布式测量服务器150可包括几百个 （例如512个）计算机，每个计算机负责管理根据预定分片函数确定的 电视收视数据的子集（也称为“分片”）。如图1B中所示，根据几百 个计算机的相应功能，将它们分为三个级别，并根据如图1B中所示的 树形分层结构将三个级别的计算机链接在一起。

分层结构的根节点被称为“根分片”151。根据分布式测量服务器 中计算机的总数量，分层结构可包括零个或多个层的中间节点。在图1 中所示的示例中，分布式测量服务器150包括一层中间节点，中间节点 被称为“混合物分片”（153-1，153-M）。每个混合物分片管理预定 数量（例如16个）的叶子分片（例如155或157）。当分布式测量服务 器150从数据源（例如STB117和电视计量数据提供者102）导入新的计 量数据时，根分片151负责根据预定分片函数选择一个或多个叶子分 片，以在分布式测量服务器150中分配新的计量数据。下面结合图4A提 供了分布式测量服务器150中的数据导入处理的更详细描述。当分布式 测量服务器150接收来自客户端170的查询时，根分片151负责根据用于 处理查询的预定分片函数选择一个或多个叶子分片。叶子分片将查询 结果提交给相应混合物分片153。混合物分片153汇总查询结果，并将 汇总的查询结果提交给根分片151，以返回给发出请求的客户端170。 下面结合图4B和图4C提供了分布式测量服务器150中的查询处理的更 详细描述。在一些实施方式中，根/混合物/叶子分片对应于三种类型的 软件模块，使得图1B中所示的不同类型的分片可以在分布式测量服务 器150中的相同计算机上操作。例如，负责管理计量数据的分片（例如 叶子分片155-1）的计算机也可以充当用于从其他叶子分片（155-2， 155-N）接收查询结果的混合物分片153-1，甚至可以是根分片151。

在一些实施方式中，分片函数是从电视收视数据记录与一个或多 个叶子分片定义映射关系的散列表函数，使得对于给定的数据记录， 根分片151可以确定哪些叶子分片存储该数据记录（在响应于查询时） 或者哪些叶子分片要存储该数据记录（在接收新的计量数据时）。作 为示例，将示例性分片函数定义为：

Shard_Number=hash_K（TV_ID，STB_ID，Broadcaster_ID）

其中“hash_K”指的是利用范围[1,…,K]中的序列号将输入的计 量数据（或查询）映射到相应叶子分片的预定散列表函数，并且K是分 布式测量服务器150中独特叶子分片的总数量（即，不对用于每个独特 叶子分片的冗余副本计数），其充当散列表函数的模。参数“TV_ID” 识别家庭中的独特电视，且参数“STB_ID”识别电视连接到的独特STB。 参数“Broadcaster_ID”识别向STB提供电视节目的独特电视内容提供 者。在一些实施方式中，为了接收来自不同电视内容提供者的内容， 一个家庭可以具有连接到多个STB的多个电视。基于这三个参数，根分 片151确定哪个叶子分片负责分配为特定家庭中的特定电视生成的计 量数据。为了说明的目的，下面结合图4A至图4C描述的一些示例假设 一个家庭具有一个STB，使得household_ID等效于STB_ID。

在一些实施方式中，通过分片函数来配置分布式测量服务器150， 使得来自一个数据源的计量数据散布在多个叶子分片上，多个叶子分 片可以与相同或不同的混合物分片相关联。例如，不允许一个叶子分 片存储来自相同数据提供者的超过5%的计量数据。通过这样做，分布 式测量服务器150可以响应于查询提供估计收视率，即使被识别为具有 与查询相关联的计量数据的一个或多个叶子分片因为系统维护或其他 原因而临时或永久不可用。在一些实施方式中，分布式测量服务器150 被配置为将相同计量数据的预定数量的副本保持在与不同叶子节点相 关联的不同计算机上。根分片151被配置为监视计量数据副本在不同叶 子分片的使用，使得在接收对计量数据的查询时，根分片151不仅能够 发现哪些叶子分片具有请求的计量数据，而且能够选择那些工作负载 小的叶子分片来处理查询。另一方面，与相同家庭相关联的计量数据 存储在相同的计算机存储器上，并且通过相同的叶子分片管理。换言 之，当分布式测量服务器发现第一叶子分片具有与通过查询识别的家 庭相关联的计量数据时，它不需要寻找第二叶子分片，因为任何其他 叶子分片都具有与第一叶子分片相同的计量数据（即副本），或者根 本没有计量数据。

将来自相同数据源的计量数据散布在多个叶子分片上并保持相同 叶子分片的多个副本的配置不仅提高了分布式测量服务器的负载平 衡，而且使其更加容错。对于给定的查询，可能有多个叶子分片具有 与查询相关的计量数据。基于这些叶子分片的当前工作负载，根分片 151可以识别用于响应查询的多个叶子分片的子集。如果所识别的叶子 分片中的一个不可用，则根分片151可以选择具有请求的计量数据的副 本的其他叶子分片来代替原始叶子分片。如果客户端170接受部分查询 结果，那么这特别有用（例如，客户端可以在查询中指定：如果其准 确性超过预定阈值或者如果从处理得到少于全部计量数据集合的预定 量的计量数据，则查询结果是可以接受的）。

在一些实施方式中，分布式测量服务器150提供预定应用编程接口 （API），用于客户端170与服务器150交互。该API可以支持现有的查 询语言（例如SQL），或者基于叶子分片上计量数据的组织来定义更灵 活的新的查询语言。例如，API和客户端应用171可以用Java实现。在接 收客户端应用171提交的查询时，根分片151检查该查询，以确认它是 正确的并且没有语法错误，然后解释查询，以确定哪些叶子分片可能 有与查询匹配的计量数据。例如，如果查询是对特定广播机构广播的 特定节目确定电视收视率，则根分片151首先识别存储通过该特定广播 机构提供的计量数据的一个或多个叶子分片，然后基于诸如叶子分片 的当前负载平衡、叶子分片中存储的相关计量数据量以及如果通过客 户端指定时的收视率准确性的因素，将查询提交给所识别的叶子分片 中的一个或多个。

在每个选择的叶子分片，查询引擎负责将查询应用于叶子分片中 存储的计量数据。该处理是将查询的条件与计算机的存储器中的每个 计量数据记录相比较，并确定该数据记录是否满足查询的条件。在一 些实施方式中，查询引擎保持满足查询的数据记录的计数，使得任何 时候发现新的计量数据记录满足查询就将计数增加一，直到检查了最 后的数据记录为止。

因为计量数据分布在多个叶子分片上，每个叶子分片具有它自己 的查询引擎，所以不同的叶子分片独立地产生满足查询的数据记录的 多个计数，然后数据记录的多个计数被提交给与这些叶子分片相关联 的相应混合物分片。在一些实施方式中，混合物分片将多个计数汇总 为一个计数，并将满足查询的数据记录的汇总总计数提交给根分片 151，其作为对查询的至少一部分响应返回发出请求的客户端170。

如上所述，分布式测量服务器150可包括多个计算机，并且每个计 算机可支持多种类型的分片。图2是示出根据一些实施方式的作为分布 式测量服务器的根/混合物/叶子分片成员运行的计算机200的组件的方 框图。计算机200包括用于执行存储器212中存储的模块、程序和/或指 令从而执行处理操作的一个或多个处理单元（CPU）202；一个或多个 网络或者其他通信接口210；存储器212；以及用于将这些组件互连的 一个或多个通信总线214。在一些实施方式中，计算机200包括用户接 口204，用户接口204包括显示装置208以及一个或多个输入装置206（例 如键盘或鼠标）。在一些实施方式中，存储器212包括高速随机存取存 储器，诸如DRAM、SRAM、DDR RAM，或者其他随机存取固态存储 器装置。在一些实施方式中，存储器212包括非易失性存储器，诸如一 个或多个磁盘存储装置、光盘存储装置、闪存装置，或者其他非易失 性固态存储装置。在一些实施方式中，存储器212包括一个或多个位置 远离CPU202的存储装置。存储器212或者替选地存储器212中的非易失 性存储器装置包括非易失性计算机可读存储介质。在一些实施方式中， 存储器212或者存储器212的计算机可读存储介质存储以下元件或者这 些元件的子集，并且可包括附加元件：

·操作系统216，包括用于处理各种基本系统服务并用于执行硬 件依赖任务的过程；

·网络通信模块218，用于经由通信网络接口219以及一个或多个 通信网络（有线或无线），诸如因特网、其他宽域网、局域网、城域 网等等，将预测服务器200连接到其他计算机；

·根分片模块220，用于从多个数据源接收新的电视计量数据以 及从客户端接收查询，并将查询结果返回发出请求的客户端170；

·混合物分片模块226，用于管理预定数量的叶子分片，包括汇 总叶子分片返回的查询结果；

·数据处理模块232，用于结合导入新的计量数据或者响应于查 询来处理存储器212中存储的计量数据；以及

·电视收视计量数据240（例如通过家庭组织的机顶盒数据）， 其中用于每个家庭的机顶盒数据242包括多个压缩的电视计量数据记 录244和家庭人口统计数据记录246两者。

在一些实施方式中，根分片模块220可进一步包括以下元件：

·最终查询结果处理模块222，用于根据查询将叶子分片和混合 物分片返回的查询结果准备为要返回发出请求的客户端的最终查询结 果；以及

·分片状态数据224，用于定义叶子分片如何存储计量数据，使 得根分片模块220能够确定哪一个或多个叶子分片存储进入的计量数 据以及哪一个或多个叶子分片响应新接收的查询，在一些实施方式中， 按照预定分片函数的形式来表达分片状态数据224。

在一些实施方式中，混合物分片模块226可进一步包括以下元件：

·部分查询结果处理模块228，用于通过例如汇总来准备叶子分 片返回的查询结果，以及将处理的查询结果提交给根分片；以及

·子分片标识符230，用于识别将查询结果报告该混合物分片的 叶子分片或混合物分片的预定集合。

在一些实施方式中，数据处理模块232可进一步包括以下元件：

·数据导入器模块234，用于导入和分配存储器212中的进入的计 量数据和人口统计数据；

·数据压缩（解压缩）器模块234，用于在必要的情况下将进入 的计量数据从其本原格式转换为预定格式，并通过记录压缩进入的计 量数据记录以存储在存储器212中，或者在响应查询时将压缩的计量数 据记录解压缩；以及

·查询引擎模块238，用于将查询应用于电视计量数据记录，以 确定记录是否满足查询标准。

为了向客户端170提供服务，分布式测量服务器150需要具有很多 家庭的电视计量数据。如上结合图1A所述，对于分布式测量服务器150 而言有很多方式访问电视计量数据。例如，电视计量数据提供者102可 以从相应订户家庭接收计量数据（例如以机顶盒日志的形式）。因为 分布式测量服务器150耦接到电视计量数据提供者102，所以电视计量 数据提供者102可将机顶盒日志转发给分布式测量服务器。在一些实施 方式中，电视计量数据提供者102将计量数据存储在账户信息数据库 132中（例如收视数据142），并向分布式测量服务器150提供对数据库 132的访问。在这种情况下，分布式测量服务器150可以直接从账户信 息数据库132接收新的计量数据。在一些实施方式中，分布式测量服务 器150还可以直接从个体家庭180接收收视数据。在这种情况下，家庭 180中的STB117通过家庭路由器120、ISP128以及通信网络130将机顶 盒生成的机顶盒日志提供给分布式测量服务器150。如下所述，分布式 测量服务器150可以找到用于托管进入的新计量数据记录的位置，而不 管数据记录是来自电视计量数据提供者102还是家庭中的STB117。

在一些实施方式中，不同的电视计量数据提供者102可以具有不同 的提供计量数据的调度。某个提供者可以在范围从一天到一周的预定 时间间隔之后向分布式测量服务器150提供新的计量数据。这种相对长 的延迟可能与电视计量数据提供者102通常关联于大量家庭（例如范围 从几万到几百万），并且可能要等待较久时间从所有订户收集机顶盒 日志，然后为了多种目的向日志应用预定处理过程的事实有关。另一 方面，家庭180中的STB117可以更频繁地（例如每小时或每分钟）向 分布式测量服务器150报告它已经累积的新计量数据。从分布式测量服 务器150的角度来看，来自不同源的计量数据可以用于不同的目的。例 如，来自电视计量数据提供者102的大量计量数据可以帮助分布式测量 服务器150产生更准确、偏差更小的电视收视率估计。但是直接来自个 体家庭机顶盒的计量数据可用于进行几乎实时的收视率估计。

图3A是示出根据一些实施方式的电视收视计量数据如何通过分布 式测量服务器150的根分片从数据源移植到根分片选择的一个或多个 叶子分片的方框图。为了说明，本示例中的数据源是电视计量数据提 供者102。如上所述，电视计量数据提供者102可能累积了一定量的电 视计量数据，并且准备好将数据传输给分布式测量服务器150。根据预 定调度，电视计量数据提供者102将它累积的新计量数据发送给分布式 测量服务器150。在一些实施方式中，计量数据存在于一个或多个日志 文件中，每个日志文件包括数据提供者ID102-1（独特地关联于电视计 量数据提供者102，以将其区别于其他数据源）、报告时间102-3（指示 日志文件何时被编辑）以及多个机顶盒日志记录102-5（每个记录关联 于特定家庭的机顶盒）。

图3B是示出根据一些实施方式的数据源（例如电视计量数据提供 者102）使用来组织电视收视计量数据的示例性数据结构（例如机顶盒 日志记录102-5）的方框图。机顶盒日志记录102-5包括STB ID312（独 特地识别与电视计量数据提供者102相关联的机顶盒中的一个或家庭 中的一个）、报告时间314（指示日志记录102-5何时被STB117编辑并 向电视计量数据提供者102报告）、日志开始时间316和日志结束时间 318（指示记录周期的持续时间）以及多个事件320，每个事件包括事 件ID322、事件开始时间324、事件结束时间326、频道信息328、内容 类型330等等。与STB117相关联的多个事件320记录通过STB117观看 电视节目的家庭活动，诸如电视何时打开/关闭，家庭观看了什么节目， 每个节目看了多久，家庭观看了什么类型的节目等等。例如，当家庭 从一个频道切换到另一个频道时，STB117将为新频道产生新事件记 录。注意，个体机顶盒日志记录102-5可提供关于个体家庭观看习惯的 信息。通过汇总机顶盒日志记录102-5并将收视数据与对应的地理人口 统计数据相关联，可以得到诸如特定地理区域中特定观众组中的电视 节目的收视率的统计信息，这是分布式测量服务器150提供的很多重要 服务中的一个。

分布式测量服务器150包括用于从不同数据源请求/接收计量数据 的一个或多个根分片151以及用于分配计量数据的多个叶子分片（例如 参加图1B）。如图3A中所示，在接收进入的计量数据时，根分片151 可将计量数据应用于预定分片函数，并选择一个或多个叶子分片来处 理计量数据。在一些实施方式中，预定分片函数被实施为散列表。对 于给定的数据提供者ID，有预定的叶子分片集合（例如155-1至155-N） 托管与该数据提供者ID相关联的计量数据。为了提高服务器性能，分 布式测量服务器150将来自相同数据源的计量数据散布在多个叶子分 片上。例如，服务器150可以设置最大阈值，使得一个叶子分片应当具 有来自特定数据源（例如电视计量数据提供者）的不超过预定百分比 或绝对量的数据。在一些实施方式中，服务器150也可以关于来自特定 数据源的数据量为叶子分片设置最小阈值。在一些实施方式中，根分 片151向每个识别的叶子分片（例如155-1至155-N）传送它从电视计量 数据提供者102接收的进入的计量数据的副本，使得叶子分片可以并行 处理数据。每个叶子分片逐个筛选计量数据中的机顶盒日志记录，并 选择要存储在叶子分片的存储器中存储的数据结构（例如300、302或 304）中的机顶盒日志记录的子集。下面结合图4A描述分布式测量服务 器150处的数据导入处理的更详细描述。

图3C是示出根据一些实施方式的分布式测量服务器150使用来存 储电视收视计量数据的数据结构（例如存储器内机顶盒记录340）的方 框图。分布式测量服务器150尽可能将进入的计量数据保持为其原始状 态，除了将计量数据从其本原格式转换为服务器150保持的格式。对于 机顶盒日志记录102-5中的每个事件320，叶子分片确定是否应当有对应 的存储器内机顶盒记录340，如果认为机顶盒日志记录102是要分配在 叶子分片，则产生对应的机顶盒记录。在一些实施方式中，存储器内 机顶盒记录340包括记录ID342（可包括识别数据提供者ID、STB ID以 及与记录相关联的事件ID的信息）、频道信息344、内容开始时间346、 内容结束时间348、电视信息索引350（可用于识别用于观看内容的电 视的属性，例如类型、尺寸、制造商等等）、家庭ID352（用于识别为 其生成记录340的家庭的人口统计数据）、播放时间354（指示家庭观 看内容的当地时间）、观看类型356（指示家庭是通过实时还是通过DVR 观看内容）以及机顶盒类型358（指示贡献机顶盒记录340的机顶盒的 类型）。在一些实施方式中，将关联于叶子分片的机顶盒记录存储在 计算机的存储器中，这使得查询处理更有效。在一些实施方式中，叶 子分片压缩每个记录并将压缩的记录存储在存储器中，以节省托管更 多记录的空间。在响应查询时，叶子分片每次解压缩一个记录，并确 定解压缩的记录是否满足查询。为此可以使用很多公知的数据压缩/解 压缩方案（例如Lempel-Ziv）。

图3D是示出根据一些实施方式的分布式测量服务器150使用来存 储家庭人口统计数据的数据结构（例如家庭人口统计记录360）的方框 图。如上所述，账户信息数据库132为了诸如计费和系统维护的不同目 的存储来自几百万家庭的人口统计数据。在一些实施方式中，分布式 测量服务器150至少保持与每个家庭相关联的人口统计数据的子集。例 如，叶子分片存储来自特定家庭的所有计量数据以及家庭的人口统计 数据。如下所述，家庭人口统计数据可以是查询本身的一部分或者对 应的结果。在一些实施方式中，家庭人口统计记录360包括家庭ID362、 家庭地址364、家庭成员的数量366、家庭收入368、家庭成员教育370 以及家庭成员年龄和性别信息372。为了效率，叶子分片也可将家庭人 口统计数据存储在它的存储器中。在接收具有家庭相关前提的查询时， 如果家庭人口统计数据不满足前提，叶子分片可以迅速跳过与特定家 庭相关联的计量数据。例如，如果查询限于一地理区域中的家庭，如 果家庭地址指示它在查询的地理区域之外，则叶子分片不需要解压缩 家庭的关联计量数据。在一些实施方式中，不压缩存储器内家庭人口 统计数据，因为其尺寸通常明显小于计量数据的尺寸（例如，一个家 庭可能有几千个机顶盒记录）并且从压缩家庭数据没有太多的收益。

图3E是示出根据一些实施方式的分布式测量服务器150使用来存 储电视广播机构信息的数据结构（例如电视广播机构信息记录380）的 方框图。在一些实施方式中，可以通过不同的电视广播机构在不同的 频道上广播相同的节目。有时候，即使相同的电视广播机构也有不同 的频道，用于在不同的位置广播相同的节目。如果查询是找出在相同 区域由多个广播机构现场直播的节目的收视率，则分布式测量服务器 150需要不仅有广播调度384，而且有频道排队数据386，用于通过其广 播机构ID382识别的每个广播机构避免错过任何机顶盒记录。

图4A是示出根据一些实施方式的分布式测量服务器150如何处理 数据源（例如电视计量提供者或机顶盒）提供的进入的电视收视计量 数据的流程图。注意，可以由数据源将计量数据推向服务器150，或者 由服务器150从数据源检索。在分布式测量服务器150中，可以有安装 根分片模块的多个计算机，每个都作为根分片操作，并管理混合物分 片或叶子分片的预定集合，用于处理数据源的预定集合。根分片151中 的一个从相应数据源接收（411）电视计量数据报告。在一些实施方式 中，数据源是电视计量数据提供者，并且报告包括与预订电视计量数 据提供者的不同家庭相关联的多个事件记录。在一些实施方式中，数 据源是特定家庭里的机顶盒，并且报告包括与家庭相关联的多个事件 记录。可选地，根分片151将事件记录从其本原格式转换（413）为测 量服务器150定义的格式。接着，根分片151将进入的计量数据应用于 预定分片函数并选择（415）一个或多个叶子分片处理事件记录，使得 每个叶子分片负责托管事件记录的子集。在一些实施方式中，可将数 据源的身份用于确定指定了哪些叶子分片处理来自该数据源的计量数 据。对于具有相同计量数据的副本的叶子分片，根分片151也考虑它们 的当前负载平衡（例如，它们中的一些可能在服务其他查询）并选择 相比其他有较大负载能力的一个。在一些实施方式中，根分片151按照 使得相同计算机上有来自不同地理区域的合理百分比的计量数据的方 式配置其分片函数，使得分布式测量服务器150中的一个计算机的关闭 不会负面影响查询结果的准确性。最终，一个叶子分片中存储的新计 量数据将被复制到其他叶子分片。最后，根分片151通知（417）每个 选择的叶子分片处理多个事件记录，例如在其存储器中分配记录的子 集，用于后续查询服务。

在根分片151识别的每个叶子分片155处，数据导入器模块接收 （421）多个事件记录或者至少其子集。在一些实施方式中，根分片151 选择的不同叶子分片155每一个具有对进入的计量数据的独立访问。对 于每个新的事件记录，数据导入器模块产生新的计量数据记录，压缩 数据记录，并将压缩的数据记录存储在其存储器中（423）。不同的叶 子分片并行处理事件记录，使得每个记录终止于被叶子分片中的一个 存储。在一些实施方式中，数据导入器模块将处理结果返回（425）根 分片151，并且处理结果可识别该特定叶子分片中存储的事件记录的子 集。根分片151可以使用这样的信息来更新其分片函数，使得例如在接 收查询时，根分片151可以确定哪个叶子分片可能具有与查询匹配的计 量数据。在一些实施方式中，数据导入器模块还将新生成的数据记录 传播（427）到其他叶子分片（如果它们中的每个被指定为具有数据记 录的副本）。

在一些实施方式中，不同的叶子分片可以具有关联于不同数据源 甚至不同家庭集合的计量数据的副本，以改善分布式测量服务器的负 载平衡，并避免它们中的一个成为不利影响服务器整体性能的瓶颈。 例如，假设有三个叶子分片和三个数据源，可以根据以下关系表将来 自三个数据源的计量数据存储在三个叶子分片上：

本发明的一个目标是使分布式测量服务器150以实时方式提供对 像多少家庭/人员在观看电视节目以及他们的地理人口统计分布的查询 的答案。分布式测量服务器150可以通过响应来自客户端170的查询来 实现此目标，即使它存储了数十亿的电视收视计量数据记录。

图4B是示出根据一些实施方式的分布式测量服务器150如何将来 自客户端170的查询应用于电视收视计量数据并将查询结果返回给发 出请求的客户端的流程图。初始地，服务器150的根分片151接收（431） 来自客户端170的查询。客户端170可以通过向根分片151进行API调用 来提供查询。例如，对于在特定时间间隔期间（例如从2011年7月1日 到2011年7月2日）期间特定广播机构（例如 “Broadcaster_Channel_Num”）的特定频道确定收视率的查询可以表 达如下：

'content<time<interval<start_time:"2011-07-01",end_time: "2011-07-02">>,metered_channel<channel_info: "Broadcaster_Channel_Num">>'.

上述查询可以如下进一步修改，使得通过与存储器内机顶盒记录 （例如STB_Type）相关联的其他参数将查询结果分组：

'content<time<interval<start_time:"2011-07-01",end_time: "2011-07-02">>,metered_channel<channel_info: "Broadcaster_Channel_Num">>,group_by_spec<screen_group_by_expr: "STB_Type">'.

上述查询可以如下进一步修改，使得通过处理分布式测量服务器 150中存储的至少预定量（例如50%）的可用电视计量数据得出查询结 果：

'content<time<interval<start_time:"2011-07-01",end_time: "2011-07-02">>,metered_channel<channel_info: "Broadcaster_Channel_Num">>,group_by_spec<screen_group_by_expr: "STB_Type">,min_data_set:0.5'.

上述查询可以如下进一步修改，使得将查询结果限制为特定观看 类型（例如仅DVR）收视类型：

'content<time<interval<start_time:"2011-07-01",end_time: "2011-07-02">>,metered_channel<channel_info: "Broadcaster_Channel_Num">>,viewing_type_filter<dvr_capable_only: true>,group_by_spec<screen_group_by_expr:"STB_Type">, min_data_set:0.5'.

在接收到查询时，根分片151对查询执行（433）健全性检查，以 确保查询在语法上正确。如果查询未通过健全性检查，则根分片151将 错误消息返回给发出请求的客户端，并且还可以解释查询中识别的错 误。对于通过健全性检查的每个查询，根分片151将查询应用于预定分 片函数，并选择一个或多个叶子分片来处理查询（435）。在一些实施 方式中，该步骤类似于步骤415的选择叶子分片来处理进入的计量数 据，即根分片不仅考虑叶子分片是否具有关联于查询的计量数据，而 且考虑不同叶子分片处的负载平衡。例如，如果叶子分片没有与查询 中识别的电视广播机构相关的计量数据，则根分片151不选择该叶子分 片。但是即使叶子分片具有计量数据，根分片151也需要考虑叶子分片 的整体健康状况，例如，叶子分片处的当前工作负载是否使其成为处 理该查询的最合格的叶子分片。最后，根分片151向选择的每个叶子分 片发出（437）查询。

在特定的叶子分片155，查询引擎模块接收（441）查询，然后将 查询应用于（443）叶子分片处存储的数据记录，以确定满足查询的数 据记录的计数。下面结合图4C提供叶子分片155如何将查询应用于叶子 分片处存储的计量数据的更详细描述。最后，叶子分片155将确定的计 数返回（445）根分片151。如上结合图1B所述，分布式测量服务器151 在树形分层结构中实现。不同的叶子分片155并行处理相同的查询，并 返回满足查询的计量数据记录的相应确定的计数。因为不同的叶子分 片处理计量数据记录的不同集合，所以没有数据记录被计数两次，并 且通过汇总来自不同叶子节点的部分查询结果来获得最终查询结果。 取决于分层结构是否包括任何混合物分片，可以由根分片151单独执行 汇总，或者由一个或多个混合物分片153然后由根分片151执行汇总。

如图4B中所示，假设没有中间混合物分片涉及汇总处理，根分片 151从相应叶子分片接收（451）数据记录的部分计数，并将部分计数 汇总为（453）满足数据记录的数据记录的总计数。在一些实施方式中， 对于分布式测量服务器150而言不需要检查每个可能的计量数据记录 来提供准确的查询结果。如果客户端170（例如广告者）对于在统计学 上准确到足以使他或她满意的查询结果更感兴趣，那么这是特别正确 的。在一些实施方式中，对于分布式测量服务器150而言很难提供非常 精确的查询结果，因为可能有太多数据要处理，使得客户端170必须等 候很长时间（例如几小时）来获得任何查询结果。为了满足不同类型 客户端的需要，分布式测量服务器150的最终查询结果处理模块222实 施统计预测功能，来将叶子分片155返回的查询结果预测为（455）从 服务器150管理的全部计量数据集合统计估计的查询结果。最后，根分 片151将估计的查询结果返回（457）给发出请求的客户端170。

在一些实施方式中，根分片151使用测量服务器150的分片函数、 分片健康和负载信息来识别服务器150中的叶子分片的簇中的数据样 本的子集，以评估查询。在对簇中的总样本尺寸计数之后，根分片151 连同图1B中所示的分层结构定义的原始查询一起将每个簇的总样本尺 寸传播到所有其他叶子分片155。具体而言，每个叶子分片确定被定义 为“k_c/K_c”的相应簇权重，其中k_c和K_c分别是总样本尺（如同前面确定 的）和簇c中目标人口的总尺寸。对于每个簇，根分片151确定加权平 均，将加权平均缩放到整个目标人口，并对总人口将缩放值加在一起。 在一些实施方式中，对于每个机顶盒，叶子分片计算定义为“k_c/K_c” 的权重，其中k_c和K_c是叶子分片中的目标人口的样本尺寸和总尺寸。接 着，根分片151基于每个叶子分片的样本尺寸在所有叶子分片之中进行 加权平均。对于统计预测的其他实施方式，请参照美国临时专利申请 No.61/501,105和美国专利申请No.12/055,906，每个专利通过引用将其 全部内容合并。

图4C是示出根据一些实施方式的分布式测量服务器150的叶子分 片155如何识别满足查询的电视收视计量数据的流程图。叶子分片155 接收（461）来自根分片151的查询。在一些实施方式中，查询包括一 个或多个标准（例如家庭过滤器）。接着，叶子分片155基于其人口统 计数据识别（463）与叶子分片相关联的一组候选家庭，并选择（465） 家庭中的一个用于进一步处理。在一些实施方式中，当特定查询到达 叶子分片155操作所在的特定计算机时，用于处理该查询的全部人口统 计数据都已经在计算机的存储器中。叶子分片155只需要将查询应用于 计算机的存储器上存储的电视收视数据，这使得查询处理迅速。对于 选择的家庭，叶子分片155将其与家庭过滤器进行比较（467）。例如， 如果家庭过滤器将查询限制为具有预定邮编集合中的一个的家庭，会 将未在集合中发现其邮编的家庭视作不合格（469，否），并且叶子分 片155移动以继续处理下一个家庭。但是如果候选家庭通过家庭过滤器 （469，是），则叶子分片155开始处理与该家庭相关联的存储器内数 据记录（471）。在一些实施方式中，叶子分片155识别与家庭相关联 的存储器内机顶盒数据记录，像图3C所示的那个。叶子分片155将数据 记录（如果是压缩的）解压缩（473），并将查询（即，与查询相关联 的标准）应用于解压缩的数据记录（475）。通常，从该步骤有两个可 能的结果：（i）满足所有查询标准的数据记录或者（ii）不满足查询标 准中的至少一个的数据记录。在第一结果中，叶子分片155例如通过将 满意的数据记录的计数增加一来累积（477）查询结果。在第二结果中， 叶子分片155简单地跳过记录并移动以继续处理下一个数据记录，直到 处理最后的数据记录（479，是）。因为该方法一次处理一个记录，所 以它只需要很少的存储器，因此叶子分片155可以节约更多的存储器来 存储压缩的数据记录。但是因为所有数据记录都存储在存储器中，所 以该方法对于在短的时间段里（例如几秒之内）将查询结果返回给发 出请求的客户端非常有效。在处理与最后家庭相关联的最后数据记录 之后（481，是），叶子分片155将查询结果（例如满足查询的数据记 录的计数）返回（485）到分层结构中的上级分片（可以是根分片或混 合物分片）。

虽然各个附图的一部分按照特定顺序示出多个逻辑阶段，但不依 赖顺序的阶段可以重新排序，并且可以组合或分割其他阶段。在特别 提及某些重新排序或其他分组时，对于本领域技术人员而言其他的情 况显而易见，因此不提供替选的穷举列表。此外应当认识到，可以在 硬件、固件、软件或者其组合中实施这些阶段。

为了解释的目的，参照特定实施方式描述了前面的描述。但是， 以上的说明性讨论并非旨在穷举或者将本发明限制为所公开的精确形 式。根据以上教导，可以有很多修改和变化。为了最好地解释本发明 和原理及其实际应用，选择和描述了实施方式，从而使得本领域技术 人员能够最好地利用本发明，并且具有各种修改的各种实施方式适合 于预期的特定用途。实施方式包括落入所附权利要求的精神和范围内 的替代、修改和等同物。为了提供这里呈现的主题的透彻理解，给出 了很多具体细节。但是对于本领域技术人员而言明显的是，可以在没 有这些具体细节的情况下实现主题。在其他实例中，未详细描述公知 的方法、过程、组件和电路，从而不会不必要地使实施方式的方面模 糊。