时间序列预测系统中的低时延差分访问控制

摘要

方法、系统和装置包括在计算机存储介质上编码的计算机程序，以实施分布式预测系统中的低时延差分访问控制。方法中的一种方法包括：通过根服务器从授权服务器获得请求者的一种或多种准许动作类型。各自在至少一个文档中与搜索参数共同发生的多个预测动作被获得。具有不是请求者的一种或多种准许动作类型中的一种准许动作类型的动作类型的任何动作从多个预测动作中被过滤。具有准许动作类型中的一种准许动作类型的一个或多个预测动作被提供给请求者。

说明书

背景技术

本说明书涉及大规模的低时延分布式计算机系统，并且更具体地涉及使用分布式计算机系统搜索大型数据集以生成与时间相关的用户动作的实时预测。

时间序列预测系统，或简称为预测系统，是一种分布式计算机系统，其基于时间序列数据的大规模聚合来预测用户动作。这允许实时发现与时间相关的动作并按可能性对它们进行排列。这种预测系统可以用于各种各样的实际应用。一个示例应用是查询建议。例如，给定搜索引擎的用户键入的先前查询，预测系统可以通过发现与先前查询时间相关的其他用户大量键入的先前查询并对其进行排列来预测该用户想要键入的下一查询。例如，如果用户键入第一查询“新生儿衣服”，则预测系统可以预测下一查询很可能是“婴儿床”，因为大量的先前用户已经在时间上接近地键入了这两个查询。因此，系统可以为键入“新生儿衣服”作为查询的用户提供“婴儿床”作为查询建议。重要的是，预测系统可以通过在线方式且实时，例如在接收到查询后，并且从用户的角度来看没有可辨别的时延，计算这种预测。结果，极低的时延对于实时预测系统的大多数操作至关重要。

在本说明书中，时间序列数据是指表示在特定的短时间段内共同发生的单个特定用户的特定动作组的数据。短时间段的长度是系统可调谐的参数，并且通常为分钟、小时或天，而不是月或年量级。预测系统可以以多种不同方式关联表示在特定时间段内共同发生的单个用户的用户动作的数据。例如，系统可以生成单个文档，该文档包括表示单个时间段内共同发生的所有动作的数据。这些技术还允许预测系统发现与时间相关的用户动作，而无需考虑动作实际发生的量级。

为了实时进行这种预测，预测系统可以使用分布式计算机系统来并行查询倒排索引。倒排索引将每个用户动作与具有该用户动作的至少一个实例的文档相关联。例如，可以将预测系统布置在具有根服务器、一个或多个级别的多个中间服务器以及多个叶服务器的基于树的层次结构中。该布置允许实时搜索索引数据的集合，这很重要，因为可搜索参数的空间防止了完整索引被预生成。在该上下文中，完整的索引将需求为每个可能的请求预测的每个可搜索参考参数的每个可能值生成公布列表。在具有非常大的数据集的系统中，不可能或者至少不可行生成这种完整索引。

隐私和匿名性是预测系统的其他重要方面，该预测系统搜索各自为单个相应用户存储与时间相关的数据的文档。为了确保用户隐私和匿名性，预测系统可以具有内置的隐私机制，其确保仅当至少由阈值数量的其他用户执行该用户动作时，才返回特定的用户动作。在本说明书中，该阈值将被称为隐私阈值。因此，如果隐私阈值是100个用户，并且如果只有88个其他用户执行了特定动作，则系统将拒绝提供该特定动作，因为该特定动作无法满足隐私阈值。该机制防止高度个性化的用户数据被泄露给其他用户。在共同拥有的美国专利申请NO.15/277,306中针对“用于预测动作的通用引擎”描述了用于快速计算针对特定动作的估计数量的用户的合适技术，其通过引用并入本文。

大规模预测系统提出了固有的可伸缩性挑战，特别是当用于具有极低时延要求的应用时，例如提供在线查询建议。随着组织变大并且基础数据量变大，这些可伸缩性挑战也增长。

大规模预测系统的一个特定可伸缩性问题是差分访问控制，这意味着为组织内的不同组或实体给出不同的权限以查询或访问基础数据。即使当单个组织完全控制所有基础数据时，允许所有内部团队查询所有可用数据也不遵循最小特权原则。

然而，对基础数据本身执行差分访问控制可能引入无法接受的时延。例如，这可能要求所有叶服务器针对每个查询或每个文档或两者与外部授权系统进行通信。这是因为基本的安全原则要求对任何公认的组或实体的任何成员资格或权限改变都应该尽快实施，以防止未经授权的访问。因此，不可能在叶服务器上存储授权信息，因为当有数千个叶服务器要更新时，这种权限更新将花费很长时间。但是，使叶服务器与外部授权系统通信给过程引入无法接受的时延，特别是当数千个叶服务器每秒需要提供数千个请求时。例如，如果有1000个叶服务器需要每个查询分析1000个动作并每秒提供1000个请求，则授权系统本身将需要每秒处理10亿个请求，这对于实时应用来说是不可行的，因为它在过程中引入了无法接受的时延。

发明内容

本说明书描述了用于在使用类型化时间序列数据的预测系统中实施低时延差分访问控制的技术。实施差异访问控制意味着预测系统控制不同请求实体或组的不同访问级别，而以低时延实施它们意味着执行差分访问控制不明显降低预测系统的时延。

本公开的其他实施方式包括方法、系统和装置，包括在计算机存储介质上编码的计算机程序，以实施分布式预测系统中的低时延差分访问控制。该方法中的一种方法包括：通过根服务器从授权服务器获得请求者的一种或多种准许动作类型。各自在至少一个文档中与搜索参数共同发生的多个预测动作被获得。具有不是请求者的一种或多种准许动作类型中的一种准许动作类型的动作类型的任何动作从多个预测动作中被过滤。具有准许动作类型中的一种准许动作类型的一个或多个预测动作被提供给请求者。

可以实施本说明书中描述的主题的特定实施例，以便实现一个或多个以下优点。预测系统可以对任意大的数据集上的任意数量的实体或组执行差分访问控制，而不导致系统时延的显着降低。因此，差分访问控制是可扩展的，以增大数据集并增大组织大小。预测系统还可以使用缓存来减少执行差分访问控制的时延。因此，即使每秒服务数百或数千个查询，提供差分访问控制对系统时延具有几乎无法测量的影响。下面描述的技术还通过允许预测系统为所有请求者维护单个数据集而不必为多个组管理多个冗余数据集来减少存储冗余。

在下面的附图和描述中陈述了本说明书的主题的一个或多个实施例的细节。主题的其他特征、方面和优点将通过描述、附图和权利要求而变得显而易见。

附图说明

图1是图示了示例系统的图。

图2是用于通过预测系统对动作类型执行访问控制的示例过程的流程图。

在各个附图中，相同的附图标记和名称指示相同的元件。

具体实施方式

图1是图示了示例系统100的图。系统100包括示例搜索系统102，该示例搜索系统102是使用预测系统110通过类型化时间序列数据进行实时预测的系统的示例。在该示例中，搜索系统102使用预测系统110对在线视频子系统122和搜索引擎子系统124进行预测。然而，下面描述的相同技术也可以用于不增强关于搜索系统102描述的搜索能力的其他预测系统。

在本说明书中，类型化数据意味着一些用户动作属于多种不同动作类型中的一种动作类型。例如，预测系统可以将查询视为一种动作类型，将网页访问视为另一动作类型，并且将视频观看视为再一动作类型。动作类型不必是互斥的。例如，访问具有嵌入式视频的网页既可以视为网页访问动作，也可以视为视频观看动作。预测系统搜索的文档通常具有多种不同类型的用户动作。例如，文档可以指示特定用户都在特定时间段内键入了查询，然后访问了网站，然后查看了视频。具有不同类型的时间相关动作允许预测系统进行聚合的交叉类型预测。因此，例如预测系统可以确定用户在查看特定视频后可能键入哪些查询。

预测系统可以以多种不同方式关联表示在特定时间段内共同发生的单个用户的用户动作的数据。例如，系统可以生成单个文档，该文档包括表示单个时间段期间共同发生的所有动作的数据。该文档可以是数据库中的记录、内存对象或电子文档，这些文档可能但不一定对应于文件系统中的文件。在本说明书中，为了简洁起见，文档将广泛地指代表示单个用户的与时间相关的用户动作的这种关联的数据。

为了简洁起见，本说明书包括描述对动作执行操作的各种示例。这种示例应被理解为对表示这种用户动作的数据进行操作。例如，每个不同的用户动作可以用独特标识符表示。另外，如果将不同用户在不同时间执行的不同动作映射到相同的独特标识符，则可以将其视为相同的动作。例如，提交对“篮球”的查询的第一用户将被视为与稍后提交相同查询的第二用户相同的动作。

预测系统可以使用表示许多不同类型的用户动作的数据。通常，动作可以是表示由用户或代表用户在任何交互式系统上执行的任何适当动作的数据，所述交互式系统例如web搜索系统、图像搜索系统、地图系统、电子邮件系统、社交网络系统、博客系统、购物系统，仅举几例。动作还可以表示与用户相关的事件，例如电子邮件消息的接收或更高级别的任务。用户动作可以是例如特定查询的提交；响应于特定查询，选择特定搜索结果或任何搜索结果；访问或长期访问特定的网站、页面或图像；观看视频；提交到感兴趣景点的方向的请求；接收确认酒店、航班或餐厅预订或者确认购买特定产品或某种产品或者特定服务或某种服务的消息；或者购买特定产品或服务。

例如，文档可以包括关于每个动作的其他信息，例如动作的位置、一天中的时间、一周中的天、日期或季节。该位置可以从用于与交互式系统进行交互的用户设备获得的位置获得，或者从例如移动电话网络的服务提供者获得，或者可以例如从用户设备的IP地址推断。可以使用预定地理网格中的一个或多个四边形的标识符以广义形式记录该位置。

在一些情况下，动作可以与实体相关联，特别是与现实世界的有形和无形两者的人、地点、事物相关联。例如，搜索系统可以确定特定查询是关于特定城市的，然后预测系统可以将城市的全局独特标识符与文档中的查询相关联。类似地，购物系统或电子邮件系统可以确定用户已购买了特定产品或服务，将其与特定实体和该产品或服务实体的独特标识符相关联，并将该信息包括在对应的活动记录中。与用户的活动相关联的实体可以被视为在活动时用户的可能兴趣。

在图1示例中，视频子系统122是在线系统，其通过计算机网络，例如内部网或互联网向外部用户设备提供视频。例如，外部用户设备160可以向视频子系统122提供对视频URL152的请求。然后，视频子系统122可以使用所请求的视频URL 152以从预测系统110获得推荐视频。视频子系统122然后可以响应于接收到视频URL 152来提供所请求的视频和一个或多个推荐视频154。

在该上下文中，推荐视频可以是预测系统110已确定最有可能与所请求的视频URL152共同发生在文档中的视频。如上所述，与搜索参数共同发生的特定视频意味着在特定时间段内，单个匿名用户同时观看了视频URL 152和共同发生的视频两者。

因此，视频子系统122可以向根服务器130提供查询132，该查询132指定搜索参数、所请求的动作类型以及可选的一个或多个条件。在图1的示例中，搜索参数是来自请求用户的视频URL 152，并且所请求的动作类型是观看的视频或表示该动作类型的标识符。在该示例中，查询132还包括可选条件，该条件指定搜索参数和所请求的动作类型在基础文档中必须彼此之间在一个小时内发生。

为了响应查询132，根服务器130将查询132广播给多个叶服务器120a至120n。在一些实施方式中，预测系统110还包括在根服务器130与叶服务器120a至120n之间的一个或多个级别的中间服务器。

叶服务器120a至120n然后搜索相应索引碎片105以首先标识具有所请求的视频URL的文档。通常，索引碎片105各自存储索引文档。为了执行并行搜索，预测系统可以跨多个相应的叶服务器存储索引数据的多个碎片，每个碎片是整个数据集的一部分。碎片可以是非重叠分区集合中的一个分区，尽管碎片也可以或替代地在多个服务器之间复制。系统中的每个服务器可以具有多个复制品。因此，可以将索引数据的相同碎片分配给多个叶服务器的池。叶服务器的每个池都处置针对关联碎片的查询，使得可以在碎片上并行搜索索引数据。

然后，叶服务器120a至120n计算在文档中共同发生的所有其他视频查看动作的分数，并针对共同发生的视频观看中的每个视频观看计算相应的初始分数，其基于观察到视频观看中的每个视频观看与所请求的视频URL 152共同发生在文档中的频率。

叶服务器120a至120n还针对每个共同发生的视频计算由共同发生的视频表示多少个不同用户的度量。预测系统110计算用户计数，使得根服务器130可以确保提供回最终用户的任何推荐视频是满足对应隐私阈值的视频。叶服务器120a至120n将所有共同发生的视频、分数和用户计数提供回根服务器130。

然后，根服务器130可以聚合每个视频的分数和用户计数。然后，假设所请求的动作类型被授权给视频子系统122，则根服务器130可以使用具有满足隐私阈值的用户计数的一个或多个视频以及它们的相应分数来响应查询132。在一些实施方式中，根服务器130以满足隐私阈值的一个或多个视频中的每个视频的概率分布来响应。

通过类似的方式，搜索引擎子系统124还可以使用预测系统110来增强它提供给用户的数据。即使搜索引擎的功能与视频服务子系统的功能有很大不同，这两个系统仍可以使用相同的通用预测系统110。

搜索引擎子系统124因此可以从外部用户设备162接收web查询156，并且可以用搜索结果和查询建议158来响应web查询156。

为了获得查询建议，搜索引擎子系统可以向根服务器130提供查询134。在该示例中，查询134具有指定从外部用户设备162接收到的web查询156的搜索参数。查询134还指定了所请求的动作类型，在这种情况下为其他web查询。因此，查询134从预测系统110请求在文档中最有可能与从外部用户设备162接收到的web查询156共同发生的其他web查询。

然后，根服务器130可以以与上述类似的方式与叶服务器120a至120n进行通信，以标识最有可能与web查询156共同发生在文档中的web查询。如上所述，特定的web查询与搜索参数共同发生意味着在特定时间段内，单个匿名用户既发布了web查询，也发布了特定的web查询。然后，假设所请求的动作类型被授权给搜索引擎子系统124，则根服务器130可以使用具有满足隐私阈值的用户计数的一个或多个查询建议以及它们的相应分数来响应查询134。搜索引擎子系统124然后可以用由搜索引擎子系统124获得的搜索结果以及从预测系统110获得的查询建议来响应web查询156。

如该示例所图示的，预测系统110针对多个不同的请求子系统以实时且在线的方式计算预测。在该上下文中，实时计算预测意味着最终用户将不会由于计算机处理限制而观察到明显的延迟。换言之，可以以毫秒为单位而不是秒、分钟或更长的时间来计算预测。

通过使根服务器使用授权服务器对所请求的动作类型执行授权检查，预测系统110可以在对时延造成最小影响的情况下执行访问控制。因为许多叶服务器120a至120n不需要执行授权检查，所以这减少了时延。相反，根服务器130可以对每个查询执行单个授权检查。

另外，根服务器130可以通过按动作类型执行授权来执行非常快速的授权检查。换言之，授权服务器130可以将请求者标识符映射到准许动作类型集合，并且根服务器130仅以具有准许动作类型的预测动作来响应请求者。与索引碎片105中的文档数量相比，动作类型的数量可能微不足道。因此，仅需要从授权服务器140向根服务器130传递少量数据。

根服务器130还可以通过与计算结果并行执行授权检查来加速计算。换言之，在将查询广播给叶服务器120a至120n之前，根服务器130不需要等待授权服务器140做出响应。相反，根服务器130可以在响应查询之前过滤没有准许动作类型的动作。

在图1中，例如最小特权原则将指定，服务推荐视频的视频子系统仅需要访问与视频观看相对应的动作，而无需访问其他动作类型，例如查询提交、web搜索结果的选择或对驾驶方向的请求，仅举几个例子。类似地，搜索引擎子系统124将仅需要访问与所提交的查询对应的动作，而无需访问其他动作类型，例如视频观看。根服务器130可以通过使用授权服务器140控制请求子系统中的每个请求子系统所允许的动作类型来有效地执行这种访问控制。

图2是用于通过预测系统对动作类型执行访问控制的示例过程的流程图。为了方便起见，该过程将被描述为由位于一个或多个位置中并且根据本说明书适当编程的一个或多个计算机的系统执行。例如，适当编程的预测系统。例如图1的预测系统110可以执行示例过程。

该系统在根服务器处接收查询，该查询指定令牌以及可选地指定一个或多个所请求的动作类型(210)。动作类型被描述为可选的，因为在没有指定动作类型的情况下，该系统可以使用默认动作类型，并简单地返回满足适当隐私阈值的所有可用动作类型。

令牌是倒排索引中的可搜索参数的独特标识符。该令牌可以由查询本身显式指定，或者通过指定对应的搜索参数隐式指定，根服务器可以将其映射到特定的令牌。

每个可搜索参数可以指定与文档相关的任何适当属性。因此，倒排索引可以将每个独特令牌与具有对应的可搜索参数的每个文档相关联。例如，令牌可以对应于特定的用户动作或与文档相关联的用户的属性。例如，令牌可以表示查询“绿湾包装工(green baypackers)”。令牌还可以表示位置数据，例如GPS坐标或者特定地点或区域的名称或标识符，例如威斯康星州密尔沃基。令牌还可以表示用户的属性，例如已将自己标识为喜欢或是绿湾包装工足球队的粉丝的用户。

例如，倒排索引因此可以具有表示查询“绿湾包装工”的独特令牌，并且可以将与发生用户提交查询“绿湾包装工”的所有文档与独特令牌相关联。

该系统获得请求者的准许动作类型(220)。准许动作类型是允许为请求者返回的动作类型。通常，准许动作类型基于提交查询的请求实体或组。因此，在一些实施方式中，每个查询都与请求者标识符相关联，该请求者标识符将实体或组与提交查询的其他实体或组独特地区分开。

为了获得准许动作类型，根服务器可以将对准许动作类型的请求发送给授权服务器，该授权服务器维护请求者标识符和准许动作类型之间的映射。例如，根服务器可以将请求发送给授权服务器，该请求指定负责服务查询建议的内部团队的请求者标识符“query-suggest”。

授权服务器可以利用针对请求者标识符的零个或多个准许动作类型进行响应。如果请求者具有至少一种准许动作类型，那么根服务器可以运行查询。相反，如果请求者标识符没有准许动作类型，则根服务器可以拒绝执行搜索或中止正在进行的搜索。另外，如果查询指定了所请求的动作类型，并且授权服务器指示所请求的动作类型不是准许动作类型，则根服务器也可以拒绝执行搜索。

替代地，根服务器可以在等待来自授权服务器的响应的同时使用查询执行搜索，因为在为低时延而设计的系统中，执行查询通常比等待来自授权服务器的响应要快。然后，根服务器可以过滤不是请求者的允许动作类型的任何动作类型。

在一些实施方式中，准许动作类型也基于区分同一请求者的不同应用的查询流标识符。例如，请求者标识符为“query-suggest”的团队可以负责视频搜索的查询建议以及图像搜索的查询建议。在这种情况下，视频搜索的准许动作类型可能只是视频搜索查询，而不是图像搜索查询。相反，图像搜索的准许动作类型可能只是图像搜索查询，而不是视频搜索查询。因此，来自查询建议团队的请求视频搜索查询的每个查询可以包括独特的查询流标识符，该标识符指示用于预测的视频搜索查询的预期应用。类似地，来自相同的查询建议团队的请求图像搜索查询的每个查询可以包括不同的独特查询流标识符，该标识符指示用于预测的图像搜索查询的应用。

因此，当从授权服务器请求准许动作类型时，根服务器除了请求者标识符之外还可以可选地指定查询流标识符。

该系统还可以通过使用授权缓存来减少授权检查的时延。授权缓存将请求者标识符和可选的查询流标识符映射到准许动作类型。因此，在从授权服务器接收到请求之后，根服务器可以将条目添加到授权缓存，该条目指示特定的请求者标识符以及可选的查询流标识符已被授权服务器映射到特定的动作类型集合。

该系统可以通过多种不同方式使缓存条目无效。例如，该系统可以使用基于寿命的驱逐策略，以便周期性地使缓存条目无效，以便利用授权服务器推动完全授权检查。例如，可以将授权缓存中的条目设置为在短时间段，例如10秒、30秒、1分钟或10分钟后到期。在一些实施方式中，到期时间是授权服务器提供的附加信息。例如，授权服务器可以为更敏感的数据返回更短的到期时间。替代地或另外，例如当授权服务器不提供到期时间时，系统可以将默认的到期时间用于授权缓存。因此，如果缓存条目的寿命小于到期时间，则系统可以确定该缓存条目是有效的。

在一些实施方式中，该系统在用户级别缓存条目。因此，如果在缓存条目的同一请求组中接收到来自其他用户的请求，则根服务器仍可以执行完全认证检查，以确保准许该用户访问所请求的动作类型。

与执行完全授权检查相比，使用授权缓存可以大大减少时延，而仅对权限改变的风险最小。例如，如果根服务器每秒响应1000个查询，并且默认到期时间是30秒，则根服务器最终将服务多于30,000个请求，而不由于使用缓存进行授权检查而导致可衡量的时延降低。

授权服务器还可以指定采样率，该采样率表示根服务器必须执行完全授权检查的查询次数之后，无论授权缓存中的条目的寿命如何。换言之，采样率指示授权缓存中的条目可以用于特定请求者的最大次数。

该系统可选地获得请求者的准许搜索令牌(230)。除了准许动作类型之外，授权服务器还可以为请求者标识符以及可选地还为查询流标识符提供准许搜索令牌。因此，如果所提供的搜索令牌不在准许搜索令牌中，则根服务器可以拒绝提供任何预测的动作，或者完全拒绝提供响应。例如，该系统可以限制基于美国的团队以提供基于美国的位置作为搜索令牌，并且可以限制基于欧洲的团队以提供基于欧洲的位置作为搜索令牌。

该系统可选地获得一个或多个自定义隐私阈值(240)。如上所述，隐私阈值是根服务器在响应中返回动作之前必须已经执行特定动作的最小数量的不同用户。因此，隐私阈值确保个性化的隐私数据不泄露给其他用户。

授权服务器可以对所有动作类型使用默认的隐私阈值。替代地或另外，授权服务器可以针对一种或多种动作类型中的每种动作类型维护不同的相应隐私阈值。

另外，授权服务器可以取决于请求者、查询流或两者使用不同的隐私阈值。例如，授权服务器可以维护每种动作类型、请求者标识符以及可选的查询流标识符组合和对应的隐私阈值之间的映射。例如，授权服务器可以将每个{query_stream,action_type,requester_id}元组映射到该元组的特定隐私阈值。

然后，根服务器可以在确定响应于查询返回哪些动作时执行自定义隐私阈值。

该系统返回允许动作类型满足相应隐私阈值的动作(250)。如上所述，根服务器可以可选地通过一层或多层中间服务器将搜索令牌广播给所有叶服务器。然后，叶服务器可以使用倒排索引来标识在具有与令牌对应的搜索参数的文档中共同发生的动作。

为了对准许动作类型执行限制，根服务器还可以向叶服务器指定准许哪些动作类型，然后叶服务器可以通过仅标识属于准许动作类型的动作来执行限制。

替代地，叶服务器可以简单地返回具有任何动作类型的所有动作，并且根服务器可以对叶服务器返回的未准许的动作类型执行过滤。该方法通常更快，因为它需求根服务器向叶服务器传达较少的信息，并且需求叶服务器执行更简单的逻辑以标识动作。

叶服务器搜索倒排索引的相应碎片。例如，倒排索引可以使用用于每个独特可标识的搜索令牌的相应公布列表来布置。搜索令牌的每个公布列表可以包括具有对应搜索参数的所有文档。叶服务器可以标识搜索令牌的公布列表，并扫描该公布列表以计算文档中共同发生的动作的相应计数以及每个动作的相应用户计数。如果查询指定了所请求的动作类型，则叶服务器只能在公布列表中扫描具有所请求的动作类型的动作的文档。然后，叶服务器可以将所发现的动作和所计算的计数提供给基于树的层次结构中的下一最高级别的服务器，该服务器可以是中间服务器或根服务器。

根服务器从叶服务器或任何中间服务器的最后一级接收共同发生的动作以及表示针对每个动作执行多少不同用户的度量的相应用户计数。在一些实施方式中，系统通过计算用户计数的下限而不是精确值来加速计算。

然后，根服务器可以为动作计算分数，并为具有准许动作类型并且满足隐私阈值的动作返回分数分布。在一些实施方式中，根服务器还通过仅返回也具有满足分数阈值的分数的动作来强加分数阈值。

为了进一步减少时延，根服务器可以在计算动作分数之前首先过滤动作类型。根服务器可以根据从授权服务器接收到的准许动作类型过滤没有准许动作类型的动作。例如，这可能意味着，针对同一查询获得的同一文档可能导致根服务器取决于请求者以不同的动作进行响应。根服务器还可以过滤没有满足该动作的隐私阈值的用户计数的动作。根服务器可以按任何适当的顺序或并发地执行这些过滤操作。

为了计算动作的分数，根服务器可以使用叶服务器以及可能聚合的中间服务器计算的统计信息。叶服务器可以计算观察到每个动作与参考参数共同发生了多少次以及每个动作通常发生了多少次的计数。然后，根服务器可以聚合这些计数，以便为每个动作计算最终的相应分数。

通常，给定搜索参数的动作的分数表示具有搜索参数的文档中共同发生的动作与任何文档中发生的动作的比较显着性。例如，动作的分数可以表示与在所有文档P(action)中发生事件的一般可能性相比，在具有搜索参数P(action|search_parameter)的索引文档中发生动作的可能性。当推断系统将事件数据存储在文档中时，推断系统可以通过将(1)包括特定动作和搜索参数的索引文档的计数除以(2)包括特定动作的索引文档的计数来估计P(action|search_parameter)。该系统可以通过将(1)包括动作的文档计数除以(2)数据集中的索引文档的计数来估计P(action)。然后，根服务器可以为动作计算最终分数S：

S＝P(action|search_parameter)/P(action)。

根服务器可以通过计算出的分数对动作进行排列，并可以响应于查询提供经过排列的动作集合。如上所述，未允许的动作类型和不满足隐私阈值的动作类型已被过滤，因此不返回给请求者。

尽管已在针对低时延预测系统的差分隐私的上下文中描述了上述技术，但是可以使用相同的技术来应用低时延差分隐私控制以在具有属于不同相应实体，例如组织中的实体的文档见解或其中的内容的任何系统内进行搜索。

可以在数字电子电路系统、有形实施的计算机软件或固件、计算机硬件(包括在本说明书中所公开的结构及其结构等效物)或者它们中的一个或多个的组合中实施本说明书中描述的主题和功能操作的实施例。可以将本说明书中描述的主题的实施例实施为一个或多个计算机程序，即，在有形的非暂时性存储介质上编码以由数据处理装置执行或者控制该数据处理装置的操作的计算机程序指令的一个或多个模块。计算机存储介质可以是机器可读存储设备、机器可读存储衬底、随机或串行存取存储器设备或者它们中的一个或多个的组合。替代地或者另外，程序指令可以在人工生成的传播信号，例如机器生成的电气、光学或者电磁信号上编码，生成该传播信号是为了对用于传输给合适的接收器装置以由数据处理装置执行的信息进行编码。

术语“数据处理装置”是指数据处理硬件，并且涵盖了用于处理数据的所有种类的装置、设备和机器，包括例如可编程处理器、计算机或者多个处理器或计算机。该装置还可以是或还包括专用逻辑电路系统，例如FPGA(现场可编程门阵列)或者ASIC(专用集成电路)。除了硬件之外，该装置可以可选地包括为计算机程序创建执行环境的代码，例如构成处理器固件、协议栈、数据库管理系统、操作系统或者它们中的一个或多个的组合的代码。

可以用包括编译语言或解释语言或者陈述性语言或程序语言的任何形式的编程语言来编写计算机程序(也可以称为或者描述为程序、软件、软件应用、app、模块、软件模块、脚本或代码)，并且可以按照包括作为独立式程序或者作为模块、组件、子例程或适合用于计算环境的其他单元的任何形式来部署计算机程序。程序可以但并非必须与文件系统中的文件对应。可以将程序存储在文件的保持其他程序或数据，例如存储在标记语言文档中的一个或多个脚本的一部分中，存储在专用于所探讨的程序的单个文件中，或者存储在多个协作文件，例如存储一个或多个模块、子程序或者部分代码的文件中。可以将计算机程序部署为在一个计算机上执行或者在位于一个站点处或分布在多个站点上并且通过数据通信网络互连的多个计算机上执行。

一个或多个计算机的系统被配置为执行特定操作或动作意味着该系统已经在其上安装了软件、固件、硬件或其组合，其在操作中使该系统执行操作或动作。一个或多个计算机程序被配置为执行特定操作或动作意味着一个或多个程序包括在由数据处理装置执行时使该装置执行操作或行动的指令。

如本说明书中所使用的，“引擎”或“软件引擎”是指提供与输入不同的输出的软件实施的输入/输出系统。引擎可以是功能性的编码块，诸如库、平台、软件开发套件(“SDK”)或对象。可以在例如服务器、移动电话、平板计算机、笔记本计算机、音乐播放器、电子书阅读器、膝上型计算机或台式计算机、PDA、智能电话或者其他固定或便携式设备的任何适当类型的计算设备上实施每个引擎，其包括一个或多个处理器和计算机可读介质。附加地，两个或多个引擎可以在同一计算设备上实施或在不同的计算设备上实施。

可以通过一个或多个可编程计算机来执行本说明书中描述的过程和逻辑流程，该一个或多个可编程计算机执行一个或多个计算机程序以通过操作输入数据并且生成输出来执行功能。过程和逻辑流程也可以由例如FPGA或ASIC的专用逻辑电路系统或者专用逻辑电路系统和一个或多个编程计算机的组合执行。

适合执行计算机程序的计算机可以基于通用或专用的微处理器或者两者或者任何其他种类的中央处理单元。通常，中央处理单元将接收来自只读存储器或者随机存取存储器或者两者的指令和数据。计算机的必要元件是用于履行或执行指令的中央处理单元以及用于存储指令和数据的一个或多个存储器设备。中央处理单元和存储器可以由专用逻辑电路系统补充或者并入到该专用逻辑电路系统中。通常，计算机还将包括用于存储数据的一个或多个海量存储设备，例如磁盘盘、磁光盘或者光盘，或者计算机可操作地耦合以接收来自该一个或多个海量存储设备的数据或者将数据传送给该一个或多个海量存储设备或者进行两者。然而，计算机不需要具有这种设备。而且，计算机可以嵌入到另一设备中，例如仅举数例，移动电话、个人数字助理(PDA)、移动音频或视频播放器、游戏机、全球定位系统(GPS)接收器或者便携式存储设备，例如通用串行总线(USB)闪存驱动器。

适合于存储计算机程序指令和数据的计算机可读介质包括所有形式的非易失性存储器、介质和存储器设备，包括例如半导体存储器设备，例如EPROM、EEPROM和闪存设备；磁盘，例如内部硬盘或者可移除盘；磁光盘；以及CD-ROM盘和DVD-ROM盘。

为了提供与用户的交互，可以在计算机上实施本说明书中描述的主题的实施例，该计算机具有：用于向用户显示信息的显示设备，例如CRT(阴极射线管)或者LCD(液晶显示器)监测器；以及键盘和指向设备，例如鼠标、轨迹球或存在敏感型显示器或其他表面，用户可以通过该键盘和该指向设备来将输入提供给计算机。其他种类的设备也可以用于提供与用户的交互；例如提供给用户的反馈可以是任何形式的传感反馈，例如视觉反馈、听觉反馈或者触觉反馈；并且可以以包括声学输入、语音输入或者触觉输入的任何形式来接收来自用户的输入。另外，计算机可以通过将文档发送给用户所使用的设备并且接收来自该设备的文档；例如通过响应于从web浏览器接收的请求来将网页发送给用户的设备上的web浏览器来与用户交互。而且，计算机可以通过将文本消息或其他形式的消息发送给运行消息收发应用的个人设备，例如智能手机并且继而接收来自用户的响应消息来与用户交互。

可以将本说明书中描述的主题的实施例实施在包括后端组件的计算系统例如作为数据服务器、或者包括中间件组件的计算系统例如应用服务器、或者包括前端组件的计算系统，例如具有图形用户界面、web浏览器或app的客户端计算机，用户可以通过该图形用户界面、该web浏览器或该app来与本说明书中描述的主题的实施方式交互、或者包括一个或多个这种后端组件、中间件组件或前端组件的任何组合的计算系统中。系统的组件可以通过任何形式或介质的数字数据通信，例如通信网络来互连。通信网络的示例包括局域网(LAN)和广域网(WAN)，例如互联网。

计算系统可以包括客户端和服务器。客户端和服务器通常远离彼此并且通常通过通信网络进行交互。凭借在相应计算机上运行并且彼此具有客户端-服务器关系的计算机程序来产生客户端和服务器的关系。在一些实施例中，服务器将数据，例如HTML页面传输给用户设备，例如以向与设备交互的用户显示数据并且接收来自该用户的用户输入，该设备充当客户端。可以在服务器处从该设备接收在用户设备处生成的数据，例如用户交互的结果。

除了上述实施例之外，以下实施例也是创新性的：

实施例1是一种方法，包括：

通过预测系统的根服务器从请求者接收指定与搜索参数对应的令牌的查询，该查询是对预测系统的请求，以计算在文档中最有可能与搜索参数共同发生的用户动作，每个文档包括表示由单个相应用户在特定时间段期间执行的动作的数据；

通过根服务器从授权服务器获得请求者的一种或多种准许动作类型；

通过根服务器，获得各自在至少一个文档中与搜索参数共同发生的多个预测动作，包括：

通过根服务器，将令牌提供给多个叶服务器中的每个叶服务器，

通过每个叶服务器，搜索被分配给叶服务器的具有与令牌对应的搜索参数的文档，以确定在具有搜索参数的文档中与搜索参数共同发生的一个或多个动作，以及

通过每个叶服务器向根服务器提供在具有搜索参数的文档中共同发生的一个或多个动作；

从多个预测动作中过滤具有不是请求者的一种或多种准许动作类型中的一种准许动作类型的动作类型的任何动作；以及

响应于查询向请求者提供具有准许动作类型中的一种准许动作类型的一个或多个预测动作。

实施例2是实施例1的方法，其中通过根服务器获得各自在至少一个文档中与搜索参数共同发生的多个预测动作是与从授权服务器获得请求者的一种或多种准许动作类型至少部分地并发执行的。

实施例3是实施例1至2中任一项的方法，其中通过根服务器从授权服务器获得请求者的一种或多种准许动作类型包括：

通过授权服务器，维护请求者标识符与准许动作类型之间的映射；以及

通过使用请求者的请求者标识符作为对映射的输入来获得一种或多种准许动作类型。

实施例4是实施例3的方法，其中映射还基于区分相同请求者的预测动作的不同应用的查询流标识符。

实施例5是实施例1至4中任一项的方法，还包括：

通过根服务器从第二请求者接收指定所请求的动作类型的第二查询；

通过根服务器从授权服务器获得第二请求者的一种或多种准许动作类型；

通过根服务器确定所请求的动作类型不在一种或多种准许动作类型中；以及

作为响应，拒绝响应于第二查询来返回预测动作。

实施例6是实施例1至5中任一项的方法，还包括：

通过根服务器从第二请求者接收指定所请求的动作类型的第二查询；

通过根服务器从授权服务器获得第二请求者没有准许动作类型的指示；以及

作为响应，拒绝响应于第二查询来返回预测动作。

实施例7是实施例1至6中任一项的方法，还包括：

通过根服务器从第二请求者接收指定与第二搜索参数对应的第二令牌的第二查询；

通过根服务器从授权服务器获得第二请求者的一种或多种准许搜索令牌；

通过根服务器确定第二令牌不是第二请求者的准许搜索令牌；以及

作为响应，拒绝响应于第二查询来返回预测动作。

实施例8是实施例1至7中任一项的方法，还包括：

通过根服务器接收第二查询；

通过根服务器确定与第二查询的请求者对应的授权缓存中的条目有效；

作为响应，通过根服务器，从授权缓存而不是从授权服务器获得第二查询的请求者的一种或多种准许动作类型。

实施例9是实施例8的方法，其中通过根服务器确定与第二查询的请求者对应的授权缓存中的条目有效包括：确定条目不大于阈值寿命。

实施例10是实施例8的方法，其中通过根服务器确定与第二查询的请求者对应的授权缓存中的条目有效包括：确定少于采样条目不大于阈值寿命。

实施例11是实施例1至10中任一项的方法，还包括：

通过请求者的根服务器获得请求者特定的隐私阈值；以及

从多个预测动作中过滤具有不满足请求者特定的隐私阈值的相应用户计数的任何动作。

实施例12是实施例1至11中任一项的方法，其中返回给第一请求者的一个或多个预测动作包括具有第一动作类型的第一预测动作和具有第二动作类型的第二预测动作，其中第一预测动作和第二预测动作在相同文档中发生，并且还包括：

从第二请求者接收指定相同令牌的第二查询；

确定第一动作类型不是第二请求者的准许动作类型，并且确定第二动作类型是第二请求者的准许动作类型；以及

作为响应，仅将第二动作类型提供给第二请求者。

实施例13是一种系统，包括：一个或多个计算机以及存储指令的一个或多个存储设备，该指令在由一个或多个计算机执行时可操作以使一个或多个计算机执行实施例1至12中任一项的方法。

实施例14是一种用计算机程序编码的计算机存储介质，该程序包括指令，该指令在由数据处理装置执行时可操作以使数据处理装置执行实施例1至12中任一项的方法。

虽然本说明书包含了许多具体实施细节，但是不应该将这些细节解释为对任何发明的范围或者可能被要求保护的内容的范围的限制，而是作为可以针对特定发明的特定实施例的特征的描述。在本说明书中在单独实施例的上下文中描述的某些特征还可以组合地实施在单个实施例中。相反，在单个实施例的上下文中描述的各种特征也可以单独地或者按照任何合适的子组合实施在多个实施例中。而且，虽然上文可以将特征描述为以某些组合的方式起作用，甚至描述为最初要求这样，但是来自所要求保护的组合的一个或多个特征在一些情况下可以从组合中切除，并且所要求保护的组合可以针对子组合或者子组合的变型。

类似地，虽然在附图中按照特定顺序描绘了操作，但是不应该将其理解为需求按照所示的特定顺序或者按照相继顺序来执行这种操作，或者执行所有图示的操作以实现期望的结果。在某些情况下，多任务处理和并行处理可能是有利的。而且，不应该将在上述实施例中的各种系统模块和组件的分离理解为在所有实施例中都需求这种分离，并且应该理解，所描述的程序组件和系统通常可以一起被集成在单个软件产品中或者封装到多个软件产品中。

已经描述了本主题的特定实施例。其他实施例在以下权利要求的范围内。例如，在权利要求中叙述的动作可以按照不同的顺序来执行并且仍然实现期望的结果。作为一个示例，附图中描绘的过程不一定需求所示的特定顺序或相继顺序来实现期望的结果。在某些一些情况下，多任务处理和并行处理可能是有利的。