潜在搜索结果的缓存的制作方法

1.本公开内容涉及基于用户输入的搜索查询来执行对来自一个或多个源的潜在结果的搜索，并且涉及潜在结果的缓存。


背景技术：

2.许多计算机系统和服务包括搜索设施，使得用户能够输入搜索查询以寻找针对某个目标实体的目标数据记录，例如针对特定其他人或一组人的联系人或简档信息，或某个所需产品的产品信息。被搜索的数据源可以在用户从其执行搜索的用户终端外部。因此，已知在搜索查询之前在用户终端本地缓存来自数据源的一些潜在结果。如果搜索查询恰好与缓存的记录之一相匹配，则与仅在输入搜索查询后才被动地查询外部数据源相比，这可以使结果能够以较低的延时被显示给用户。
3.例如，在人物选择中有两种常用的方式。第一种可以被称为小缓存，且第二种可以被称为大缓存。移动客户端通常使用小缓存方式，而桌面客户端或基于网络的系统更常使用大缓存方式。
4.通常在移动设备上使用的小缓存方式采用目录回退机制。在启动时，客户端从本地存储在移动用户设备上的设备联系人中或从用户在他的/她的邮箱服务器上的邮箱中的用户的前n个联系人中检索并缓存数据集合，这意味着这两个列表中的一个现在可以容易地用于过滤和匹配(在任何搜索查询被输入之前缓存的)。两个数据源都具有不可公度的排名，因此通常不进行交叉。当用户键入搜索查询的字母时，在用户设备上对该预缓存的结果集合进行本地过滤(根据逐字匹配要求或模糊匹配)，直到缓存的结果中一个或多个匹配的缓存结果的集合保持，或者结果集合为空。如果是后者，则向用户呈现用于回退以在服务器上搜索更广泛的联系人目录的选项，其中该目录是用户所属组织内的所有联系人的全局列表。直接在目录中搜索该目录中的条目，而不缓存。因此，一种情况是总处于两种搜索模式中的一种，本地(缓存的)或外部目录(未缓存的)。此外，每次用户向他/她正在搜索的字母系列添加字母时，用户必须再次点击搜索，这会释放任何缓存的结果并触发全新的搜索(例如，如果用户键入“joh”，然后敲击“搜索目录”，这不会返回正确或足够数量的人，然后用户输入另一个字符，所以字符串是“john”，则用户需要触发对搜索目录的新搜索以得到新结果，因此需要额外的按键操作)。
5.对于由桌面客户端执行的搜索，或从移动或桌面设备访问的网络托管客户端的搜索，通常使用另一种方式。桌面搜索通常使用大缓存，而基于网络的搜索使用混合方式。对于桌面和网络二者，前n个联系人被缓存在用户设备上，例如，其中n等于1500。键入搜索查询会调用该缓存的过滤。一旦缓存被释放，对在线目录的回退查询就完成了。对于网络搜索，存在一种所谓的混合方式。随着用户键入，查询被提交到缓存中预先缓存的前n个列表和在线目录(其是未缓存的)二者。如果对在线目录的查询耗时超过1000ms，则来自缓存的本地结果将显示给用户而没有来自目录的任何结果，直到这些结果变得可用。这确保了低延时，但有时会导致结果在用户选择之前切换位置。在这两种体验中，针对每个键入的字母
刷新结果列表。


技术实现要素：

6.根据本文中公开的一个方面，提供了一种由用户终端执行的方法。所述方法包括：接收在一个或多个数据源的集合中的多个条目之间搜索目标条目的搜索查询的部分，所述部分是按序列一个接一个地接收的；通过接收所述部分中的每个相应的部分(例如，每个字符)进行的触发，执行相应的缓存操作，包括：查询所述集合中的一个或多个数据源中的每个数据源以检索与所述搜索查询相匹配的条目，所述搜索查询由迄今为止按序列接收的所述部分或一些部分组成，以及将检索到的条目缓存在每个被查询的数据源的相应缓存组中。所述方法还包括：呈现应用视图，所述应用视图显示所述检索到的条目中的至少一些条目的可视化表示；以及对于每个缓存操作，基于所述搜索查询像现在一样包括所述搜索查询的所述相应部分在所述检索之后在所述缓存中选择一个或多个任意新检索的条目，以及更新所述应用视图以包括来自所述缓存中的一个或多个选择的条目。
7.由于缓存被搜索查询的每个个体部分的条目(例如，每个字母或字符)填满，这在本文中可以被称为缓存的“动态回填”。与简单地提前缓存前n个结果的固定列表相比，这能够使得更有可能更快地呈现相关结果，但延时比目录回退更低。
8.在实施例中，应用视图可以按照所选择的条目在用户终端处被接收的顺序来显示所选择的条目。在一些替代实施例中，应用视图可以显示按缓存组排序的所选择的条目。作为另一示例，在实施例中，应用视图可以显示按缓存组排序并且然后在每个缓存组内按照条目在用户终端处被接收的顺序排序的所选择的条目。
9.在实施例中，数据源的集合可以是多个数据源的集合，并且被查询的数据源可以是所述集合中的多个数据源。在这种情况下，从每个被查询的数据源检索的条目被缓存在不同的相应缓存组中。在一些此类实施例中，多个被查询的数据源中的至少一些数据源可以在用户终端外部，在这种情况下，从这些外部数据源中的每个外部数据源检索的条目是经由网络检索的。此外，在实施例中，多个数据源可以各自具有从数据源到用户终端检索条目的不同延时。
10.结合动态回填，为不同的源提供不同的缓存组意味着不同的缓存组被填充并且它们的结果被并行显示，彼此独立，而不是在移动到下一个之前穷尽一个源，等等。即，该机制不会先等待查询和显示来自一个数据源的结果然后才对任何其他数据源执行该操作，也不会以任何方式将查询和显示来自一个数据源的结果的定时针对任何其他数据源的该操作的定时进行关联。对多个源进行处理的另一种方式可以延迟显示一个源的结果，直到对另一个源的查询已穷尽或超时(参见背景技术部分中讨论的目录回退和混合方式)。然而，这在来自至少一个数据源的潜在相关结果可以被输出给用户之前导致了更多的延时。另一方面，通过将动态回填方式并行地应用于多个独立缓存组中的每一个，这导致更有可能将相关结果更迅速地呈现给用户(即，具有更低的延时)。
11.在所选择的条目也以它们被接收的顺序显示的实施例中，这进一步改进了将结果输出给用户的延时。折衷是“稳定性”的损失—这指的是某些用户的期望，如果在不同场合输入相同的搜索查询，则每次应该以相同的顺序显示针对该相同搜索查询的搜索结果。然而，在本文中认识到稳定性的损失对于减少的延时来说可以是值得的折衷。
附图说明
12.为了帮助理解本公开内容的实施例并显示如何实施这些实施例，仅通过示例的方式来参考附图，在附图中：
13.图1是一种计算机系统的示意性框图，以及
14.图2至图16分别示意性地示出了应用视图和多个缓存。
具体实施方式
15.存在用户可能希望从不同的数据源中搜索实体记录的各种场景。希望能够快速向终端用户显示结果(性能)，同时还确保正确的实体可供选择(完整性)。常见的解决方案各有利弊，例如缓存(内存密集型)和流式传输(cpu和带宽密集型)。执行查询的正常方法是对每个查询逐出整个缓存，以优化查询字符串的结果。下文公开了一种方式，它是这些方式之间的折衷方案，具有不同片段和/或源的分段流，对不同片段进行频繁更新。它可以为各种应用场景提供显著的延时改善，无论是搜索用户经常合作的人还是用户第一次接触的人。
16.用户工作可以如下表述。用户希望尽可能容易地选择他或她正在寻找的实体，而无需知道该实体的记录源自何处。
17.通过下文的示例，实体将被假定为用户希望选择、以某种方式与之交互、可能共享某些信息、邀请参加某些协作事件或作为目标信息的接收方的人物。本文中的“人物”可以是任何一方，可以是个人或人群。或者，实体可以是任何其他事物，例如产品、文档等。为了讨论起见，以下将假设所寻求的实体是人。
18.实体(例如，人)的记录可以在一组一个或多个数据源中的任何一个数据源中找到。这种意义上的源可以是例如人的任何存储库或目录，即，可通过某个接口访问的人物信息的某个集合。用户工作然后可以制定如下。用户希望尽可能容易地选择他/她正在寻找的人，而无需知道个人信息的源是什么。
19.在实施例中，可以存在在其中进行搜索的多个潜在的源。例如，如今在给定组织或服务的内部和外部存在大量人物目录，从存储在电话sim卡上的联系人列表到图表或社交联网网络，这可能是最大的可公开访问的人物列表。所搜索的特定目录或一些目录对于当前目的不是必需的。尽管如此，在实施例中，所搜索的目录在接口的延时方面确实有些不同。这些源也可以被相互独立地访问。
20.例如，要查询的可用资源可以包括：i)设备联系人，即用户已存储在他/她的用户设备(例如用户的手机、平板电脑或pc)上的联系人，通常按字母顺序排序；ii)邮箱的前n个联系人，即用户邮箱中他/她过去曾与之发送过电子邮件的人，按照用户与他们的通信量排序；iii)全局地址列表(gal)，它是与用户处于相同组织(例如，公司)中的联系人的目录，通常也是按字母顺序排序；和/或iv)社交媒体目录，例如用户的第一级联系人。一个人可能出现在几个源中，但如果用户要在搜索中找到该人，则该人必须至少在一个源中可获得。如果源的接口存在明显的差异，无论是因为它们具有不同的访问控制、不同的延时、不同的可靠性或不同的大小，则所公开的方案特别(但不是排他地)有用。
21.存在多种形式的排名搜索结果。示例包括按字母顺序排名、按重要性排名以及随机。在按字母顺序排名的情况下，列表中的人可以例如通过他们的名字的字母来排名，或者在其他实现中通过他们的姓氏的字母排名。在按重要性排名的情况下，这可能意味着，例
如，与用户通信更频繁的人比其他人排名更高。在随机排名的情况下，列表中的人是伪随机排名的。在当前公开的机制的实施例中，可以使用任何这样的排名或排序方案或其他方案，例如，来确定用户的前n个联系人。
22.实施例可以将全局排名假设为在所讨论的人、设备、应用或场景之外遵守的排名。例如，如果社交网络目录中的人物列表按字母顺序排序，则它们始终按字母顺序排序，不随用户正在做什么而变化。另一方面，本地排名可以指当用户想要选择他们正在寻找的人时，人物建议出现在当前用户工作中的顺序。因此，如果用户正在寻找joe，而joe是建议的第3个人，则他将具有本地排名3，与他或她具有的全局排名无关。
23.通过“目标”实体，这意味着用户实际上正在寻找的实体(例如，人)，例如john。目标记录或条目是一个(或多个)数据源中的目标实体的记录。
24.图1示出了根据本文公开的实施例的、用于实现搜索缓存方案的示例计算机系统100。系统100包括用户终端102和一个或多个数据源104的集合。用户终端103例如可以采用桌面式计算机、膝上型计算机、平板电脑、智能手机或诸如智能手表或智能眼镜之类的可穿戴设备的形式。其包括显示屏幕106和用户输入装置105。显示屏幕106例如可以是采用任何合适的显示技术(例如led、lcd或crt)的触摸屏或非触摸屏。用户输入装置105可以例如包括以下任何一项或多项：键盘、按键、鼠标、触控板、跟踪球、操纵杆和/或触摸屏的输入传感器(它可以是与显示屏幕106相同或不同的屏幕)。显示屏幕106和输入装置105可以与用户终端102的其余部分集成在相同外壳中，或者可以采取经由有线或无线连接来连接到用户终端102的主体的外围设备的形式，或者集成组件和外围组件的任意组合。
25.每个数据源104包括用户搜索的类型(例如，人)的多个不同实体的数据记录的目录，其中本文所指的目录可以采取任何列表、数据库、图表或其他可搜索数据结构的形式。
26.数据源104可以包括在用户设备102内部的一个或多个数据源。例如，通过说明的方式在图1中示出了一个这样的数据源104a。例如，这可以包括存储在一个或多个内部存储单元中的目录，例如，采用电子存储介质的存储单元，如固态驱动器(ssd)、闪存器、eeprom；或者采用磁存储介质的存储单元，如硬盘驱动器等；或者两种或多种不同存储介质或单元的任意组合。内部数据源可以例如包括本地存储在用户终端102上的设备联系人的列表。
27.替代地或附加地，数据源104可以包括一个或多个外部数据源104。为了说明的目的，图1中示出了三个这样的源104a、104c、104d，但是应当理解，可以涉及其他数量。每个外部源可以在用户终端102经由一个或多个网络101可访问的服务器的一个或多个存储单元上实现，其中，本文中服务器可以指代一个或多个地理位置处的一个或多个物理服务器单元。存储单元也可以采用任何合适的形式，例如采用电子存储介质的存储单元，如固态驱动器(ssd)等；或者采用磁存储介质的存储单元，如硬盘驱动器等；或者两种或多种不同存储介质或单元的任意组合。在多个外部源104a、104c、104d的情况下，这些外部源可以在相同服务器或不同服务器上实现。每个外部源可由用户终端102经由一个或多个网络101访问。在多个外部源104a、104c、104d的情况下，这些外部源可以经由相同网络或不同网络被访问。例如，用户终端102可以被布置为：经由广域互联网络(如互联网)访问一个或多个外部源，但是经由局域网(如公司内联网)访问一个或多个其他外部源。
28.用户终端103安装有客户端应用103。客户端应用103被存储在用户终端102的一个或多个存储单元上，这些存储单元例如可以包括采用电子介质的存储单元，如ssd、闪存器
或eeprom；或者采用磁介质的存储单元，如磁性硬盘驱动器；或者两种或多种存储介质或单元的任意组合。其上安装有客户端103的存储装置可以是与任何内部本地目录104a(例如设备联系人的列表)相同或不同的物理存储单元或一些物理存储单元。客户端103被布置为在用户终端102的处理装置上运行，该处理装置包括一个或多个处理单元，例如中央处理单元(cpu)、图形处理单元(gpu)、数字信号处理器(dsp)、专用集成电路(asic)或现场可编程门阵列(fpga)等；或者两个或多个处理单元的任意组合。客户端应用103可以例如采取下列形式：voip客户端、即时消息传送(im)客户端、协作工作空间客户端、办公或商业应用套件的客户端、社交网络服务的客户端，或者专门的人物搜索应用，等等。或者，客户端应用103可以是通用客户端应用，如用于经由网络101之一访问在服务器外部托管的特定服务的网络浏览器，例如，网络托管的voip和/或im通信服务、协作工作空间、社交网络，或者托管在网络或其他在线位置上的办公或商业应用套件。
29.当在用户终端102的处理装置上运行时，客户端应用在用户终端102的显示屏幕106上显示用户界面107。用户界面107包括应用视图(“应用视图”)108，其包括应用103基于用户通过用户输入装置105输入的搜索查询找到的搜索结果的列表。当在用户终端102的处理装置上运行时，客户端应用103可以被布置为操作如下(通过客户端应用103本身的整体功能或通过访问托管在服务器上的服务，或者这些方式的组合)。它使用用户输入装置105执行以下操作以接收来自用户的搜索查询，并使用显示屏幕106上显示的用户界面107中的应用视图108来向用户显示相应的搜索结果。
30.用户希望通过用户终端102来提交查询，以便在存储在一个或多个数据源104之中的多方的记录中搜索诸如目标方的目标实体的记录。每个数据源104包括多个条目，每个条目包括相应实体(例如，某一方)的记录，该实体可以潜在是用户正在寻找的实体，这取决于用户输入什么搜索查询。用户通过用户输入装置105输入搜索查询。搜索查询包括表示用户正在寻找的目标实体的字符串。
31.在实施例中，应用103在用户开始输入搜索查询之前缓存来自至少一个数据源104的可能候选条目的子集，例如来自本地设备联系人104a或邮箱104b中的前n个最常访问实体的列表(例如，与用户通信最多的联系人)的前m个最常访问条目(例如，联系人)。一些其他源104(例如全局地址列表(gal)104d)可能不值得提前缓存，例如，因为它们太大并且缓存没有任何信息的目标结果的概率太小或者甚至可以忽略。或者，直至用户输入搜索查询的第一部分之前，应用103可以不从任何源104开始缓存。
32.无论哪种方式，一旦用户开始输入搜索查询的部分，应用103就在用户输入搜索查询的每个部分(例如，每个字符)时利用所述每个部分来动态地触发缓存填充操作。这在本文中可以被称为“动态回填”操作。对于每个这样的操作，每个操作都由用户输入搜索查询的各个字符而触发，应用103查询一个或多个数据源104的集合中的每个数据源，以寻找与迄今为止输入的搜索查询相匹配的任何条目，即，由直到过程中的当前点输入的搜索查询的一部分或一些部分组成。基于此，应用103检索并缓存在用户终端102上的缓存层中找到的条目中的至少一些条目。优选地，这导致应用视图108在用户进入下一部分之前用该系列中当前部分的检索到的条目来进行更新。
33.缓存层可以是用户终端102上板载的数据保存区域，其具有比搜索中涉及的任何数据源104更低的延时，即：i)访问缓存层和在应用视图108中显示缓存结果之间的时间低
于ii)访问相应数据源104、检索结果并直接在应用视图108中显示结果所花费的时间。除此之外，本文中使用的术语“缓存”不局限于任何特定的缓存层，也不一定局限于用户终端102上的处理装置的处理器的硬件中的架构(硬件)缓存层。例如，缓存层可以在通用ram中实现，或者在ram和处理装置的处理器的寄存器之间的架构缓存中实现，或者甚至可以在具有更低延时的高速非易失性存储单元中实现，例如，其上存储有设备联系人104a的非易失性存储单元。
34.注意，取决于实施方式，搜索查询或搜索查询的一部分的“匹配”可能需要硬匹配(相同字符串)或软匹配(例如，使用模糊匹配，例如以便适应用户的搜索查询中可能的拼写错误或打字错误)。用于搜索匹配的各种其他选项(例如区分大小写或不区分大小写、需要整个单词等)在本领域中是已知的，并且应当理解，本公开内容的范围不需要局限于任何具体匹配技术。此处的术语“条目”是指数据源104中的一个数据源中的特定记录，或其保存在缓存层或应用视图108中的缓存版本。给定条目包括给定实体的记录，例如某一方(例如用户的联系人)。条目的缓存版本可以包括存储在数据源104中的相同条目的一些或全部信息。与搜索查询相匹配、与选择标准相匹配或者被缓存的条目在本文中也可以被称为“结果”或“命中”。
35.在多个源104的情况下，然后对于每个缓存操作，应用将从每个被查询的源104检索到的任何结果缓存在相应的缓存组204中(例如，参见图2
‑
图16，稍后将更详细讨论)。例如，缓存组204可以包括：用于对来自设备联系人104a的结果进行缓存的设备联系人缓存组204a、用于对来自邮箱104b中的前n个列表的结果进行缓存的前n个缓存、用于对来自社交网站104c的结果进行缓存的社交网络缓存204c，和/或用于对来自全局地址列表(gal)104d的结果进行缓存的gal缓存204d。每个缓存组204是保存来自相应源的相应缓存结果的数据结构。它们可以在彼此相同的物理数据保存区域(例如，相同的ram或架构缓存)或不同的物理区域，或者其组合中实现。缓存组在实施方式中在结构上是不同的，以便能够实现涉及本文中的实施例描述的排序。
36.注意，本文所指的社交网络不排除商业网络。社交网站可以是休闲社交网站或商务社交网站。这里的术语“社交”用于指人和/或人群之间形成联系，而不是区分休闲与商务。
37.在多个源104的情况下，不同的源104a
‑
104可以具有不同的延时。在此，延时是指发起对源103的访问以利用搜索查询进行查询和在用户终端102处接收回相应结果之间的时间。
38.利用用户输入的搜索查询的每个部分以及每个相应的缓存填充操作，应用103从每个缓存组204中获取任何新缓存的结果的所选择的子集，并在应用视图108中向用户显示该子集。例如，在实施例中，根据一些标准或度量对每个子组中的结果进行排名，例如，用户过去与相应实体进行交互的频率(例如，用户过去与联系人通信的频率)。这可以与相应条目在从中检索到这些条目的数据源中具有的排名相同。从缓存组204获取到应用视图108的子集可以是达到预定最大数量的最高排名的结果。对于缓存组204中的不同缓存组，预定数量可以不同。
39.在实施例中，应用103被布置为：按照在用户终端102处从结果各自的数据源104接收结果的顺序在应用视图108中显示这些结果。因此，在多个数据源14的情况下，来自具有
较低延时的数据源的结果将自动倾向于显示在应用视图108中的列表的更高位置。
40.现在参考图2至图16描述示例用例。这些图显示了来自四个示例源104a
‑
d的结果如何存储在单独的相应缓存组204a
‑
d中。应当理解，类似的原理也可以应用于不同数量的其他类型的源104，以及对人物以外的实体的搜索。
41.考虑例如以上四个源：设备联系人104a、邮箱前n列表104b、社交网络联系人的列表或图表104c以及全局地址列表(gal)104d。前n列表104是根据某个度量与用户通信最多的n个联系人的列表，根据该度量进行排名(用于该操作的示例度量本身在本领域中是已知的)。社交网络服务104c例如可以是其品牌名称以字母l开头的商业网络服务。因此，从四个源104a
‑
d检索的结果(缓存条目)201在图2
‑
图16中分别由字母d、t、l和g表示。
42.如上所述，四个源104a
‑
d具有不同的特性。下表显示了一些可能不同的属性的示例，其中，该实例中的延时是从查询到第90个百分位数的结果的时间，平均相关性是在该特定源中找到用户正在寻找的人的机会(再次注意，一个人可能出现在多个源中)。
[0043][0044]
每个缓存组204负责取出它自己的数据。所公开方案的任何给定实例化的设计者可以设置从各个数据源104检索多少结果到每个组204中，以及在应用视图108中显示这些结果中的多少结果，以及它们的显示顺序。设计者还可以选择每个组的用户体验排名。或者，结果以它们被接收的顺序显示在应用视图108中，如果源104具有不同的延时，将倾向于按照按键然后按组(源)进行排序。在实施例中，设计者可以相互独立地选择这些参数中的任何一个或多个。这意味着设计师可以针对每种体验在不同源之间进行优化。在实施例中，上述参数中的一个或多个参数甚至可以由用户选择，仍然独立于每个组204。
[0045]
图2示出了该过程中的第一个可选步骤。这里，在用户输入搜索查询的任何部分之前，应用103从一个或多个数据源104中的每个数据源检索初始结果集合并将它们包括在相应的缓存组204中。例如，在所示出的示例中，相应的初始条目集合被缓存到设备联系人104a、邮箱前n 104b和社交网络联系人104c中的每一个的相应缓存组204a、204b、204c中。在这些源104中的每个源中，可以对相应目录中的条目进行排名。例如，在设备联系人104a和邮箱联系人104b中的每一个之内，可以按照用户与他们通信的频率来对联系人进行排名；而可以按照社交网络内的连接性来对社交网络联系人104c进行排名。
[0046]
在每个缓存组204的初始集合中缓存的条目的数量可以是预定数量，其可以针对
每个缓存组104独立设置(例如，由设计者或用户设置)。缓存结果的初始集合例如可以是来自每个源的排名前m个结果，其中通常可以由设计者或用户针对每个组204独立地设置m。或者，如果给定源中的条目中的条目没有根据估计的相关性、重要性、可能性等进行排名，则可以在不同的基础上选择要缓存的条目的集合，例如从源104的较大量条目之中随机选择。在说明的示例中，由于在三个源104a
‑
c中的每个源中找到用户正在寻找的联系人的可能性几乎相等是先验的，因此对于每个组204a
‑
c，预定数量m被设置为相同的。在说明的示例中，该数量为9，使得应用103从三个源104a
‑
c中的每个源取出并缓存9个联系人，并将它们存储在单独的相应缓存组204a
‑
c中。注意，在实践中，该数量可能要大得多，例如，～100或1000个或更多联系人。然而，为了说明的目的，作为示例，使用的最大缓存组大小为9个条目。在实施例中，应用103尚未从gal 104d取出任何条目，因为从大目录取出随机数据几乎没有意义。取出的联系人按照这些联系人被返回的顺序存储在他们各自的缓存组104a
‑
c中，在这种情况下是设备联系人104a，然后是邮箱前n 104b，然后是社交网络联系人104c(设备联系人104a在三者中具有最低延时，而社交网络服务104c在三者中具有最大延时)。或者，可以按照它们的排名顺序在相关缓存组204中对结果进行排序。
[0047]
图3至图4示出了移除重复项的可选步骤。在不同的源104中可能存在一些联系人的重复项，并且这些可能最终被缓存，使得来自不同源的重复联系人最终都在不同的相应缓存组204中的缓存中。在实施例中，应用过程以从缓存中移除这些重复项(即，移除每个重复条目的除一个实例之外的所有实例)。如图3所示，首先应用103检测重复项并在缓存中对其进行标记。出于说明目的，这些重复项在图3中以交叉阴影线显示。然后，应用103将从除一个缓存组之外的所有缓存组中移除每个重复项，以便在仅一个缓存组204中留下任何给定结果的仅一个实例，如图4所示。在所示示例中，应用103从邮箱缓存组204b和社交网络缓存组204c中移除重复项，将实例留在设备联系人缓存组204a中，但是应当理解，这只是一个示例。
[0048]
图5示出了在应用视图108中呈现的初始缓存结果的选择(在任何重复项移除之后)。在实施例中，按照结果进入的顺序(结果从它们各自的源104到达用户终端102的顺序)来呈现结果。因此，来自最低延时源104a(设备联系人)的结果将自然地以这样的顺序出现：首先是应用视图108，然后是邮箱联系人104b，然后是社交网络联系人104c。或者在其变体中，可以向缓存组204分配预定顺序，例如根据设计者估计的在相应源104中找到匹配的概率来排序。在这种情况下，结果首先在应用视图108中按缓存组排序，然后来自组内的各个结果根据它们的到达顺序来排序。在类似的变体中，缓存组204可以由用户手动排序，或由应用自适应地排序(例如，基于根据随着时间流逝用户选择与之进行交互的结果自适应地确定的相关性度量)。
[0049]
从每个缓存组204中选择以包括在应用视图108中的集合可以是相应缓存组204中的缓存条目的全部或其子集。这可以由多少空间可用或多少存储器可用，或这二者来确定。其可以在设计阶段预先确定，或者是自适应的，或者由用户设置。在实施例中，从每个缓存组204中选择的数量是根据预定方案以组204之间的预定比率确定的。
[0050]
例如，在不知道相关性模型的分布的情况下，假设它是线性的，使得目标方在子集中的几率等于平均相关性*样本大小/总体。称在子集p(x)中找到某个人的概率，例如，在设备联系人的子集d中找到目标的概率＝pd(d)。这然后给出pd(d)＝ard*d/popd，其中ard是
设备联系人的平均相关性，d是子集的大小，popd是设备联系人的总人数。为每一个选择样本大小4，然后给出：
[0051]
pd(4)＝0.8*4/420＝0.0076,或者0.76％。
[0052]
pt(4)＝0.24％
[0053]
pl(4)＝0.425％。
[0054]
这是一种简化，因为在实践中，联系人的相关性往往呈指数分布，但分布的细节对算法来说并不重要。设计者可以根据分布模型来调整每个组的缓存并查看子集。例如，查看上面的数字，可以决定将算法设置为从设备联系人缓存组204a取出4个结果以显示在应用视图108中，但是只从邮箱缓存组204b中取出1个结果，从社交网络缓存组204c中取出2个结果。
[0055]
如图5所示，从缓存组204中移除所选择的结果，并将其放入应用视图108(其本身是缓存组)。给定缓存组204中的结果可以被排序，例如按照它们到达用户终端102的顺序，或者按照重要性或相关性度量来排序。被选择从给定缓存组204传送到应用视图的子集可以是根据该顺序的最顶端的子集(例如，最早到达缓存组中)。因此在所示示例中，来自设备联系人缓存组204a的前4个结果被传输到应用视图108，来自邮箱缓存组204b的前1个结果以及来自社交网络缓存组204c的前2个结果。
[0056]
图6到图16现在示出了在任何初始、抢先的缓存之后的缓存匹配过程，如关于图2到图5所讨论的。
[0057]
当用户现在开始键入时，应用103会将结果过滤为与查询文本匹配的结果。如果用户正在寻找john，他/她将从键入“j”开始。在这种情况下，用户可能会命中缓存组204中一个或多个缓存组中缓存的一个或多个结果。图6中示出了一个示例，其中第一个字符“j”的一些示例命中(匹配)显示为阴影。
[0058]
应用103然后可以立即从应用视图108中过滤掉不匹配的结果。它还在缓存组204中寻找在图5的初始步骤中未被选择用于在应用108中显示的命中(匹配)。如果发现任何此类命中，现在将这些命中中的一个或多个传输到应用视图。可以使用与关于图5所讨论的相同的选择标准和排序方案。在说明的示例中，这留下了如图7所示的应用视图108。注意，结果仍按源的原始顺序排列，这意味着没有结果将会交换位置。
[0059]
在实施例中，应用103将非匹配项重新放回到它们各自的缓存组204中。原因是用户经常键入错误的字母。如果用户删除他/她的第一个字母并重新键入一个新字母，则将不匹配项放回缓存中使它们能够再次被快速调用。然而，这并不是严格必要的。应用103可以替代地刷新任何不匹配项的缓存组204。
[0060]
在实施例中，缓存分组使得设计者、用户和/或应用103能够管理不同的源104及其结果集合的排名，以及保留源的高级别排名。
[0061]
图7显示了在用户键入“j”后经过滤的结果的示例。下一步是执行动态回填操作以补充缓存组204，如通过图8中的示例方式所示。
[0062]
缓存分组策略使得应用103能够对每个源104的缓存组204进行动态回填。如果处于图8所示的状态，则在键入第一个字母“j”之后，每个缓存组204现在可以独立地调用其各自的源104来填充缓存。这包括将部分搜索查询“j”作为搜索请求提交给每个源104，以搜索和检索迄今为止与搜索查询相匹配的条目。这些条目从每个源104返回到用户终端102，并
缓存在相应的缓存组204中。它们在图8中显示为斜阴影线。如果在给定源104中找到的匹配项比相应缓存组204的最大大小多，则仅前m个匹配项可以被检索并缓存，例如，根据关于图2讨论的类似方案。
[0063]
因此，当对缓存进行填充时，每个组204仅利用迄今为止与查询相匹配的条目(在该示例中为
‘
j’)来进行回填。在实施例中，来自第四源gal104d的结果现在被检索到第四缓存组204d中。这是因为现在可能会产生一个更相关的结果集合，因为到目前为止其结果是基于部分搜索查询被过滤的。在其他实施方式中，应用103可以被布置为在开始填充该缓存组204d之前等待搜索查询的更多部分或字符(或者实际上是任何源104的缓存组204，其条目没有根据重要性、相关性或优先级等进行排名)。
[0064]
注意，在图8所示的阶段，所有新缓存的条目(斜阴影线)与迄今为止输入的部分搜索查询相匹配，当前包括在应用视图108中的所有条目也是如此。如果先前的不匹配被返回到缓存组204而不是被刷新，那么此时的大多数源缓存将不匹配查询“j”，但如所解释的，这些可以可选地被保留以避免在用户改变他/她的查询的情况下必须重新补充缓存。因此，在所示示例中，只有应用视图108中的条目以及编号为x10或更高的缓存组中的条目与查询
‘
j’相匹配。还应注意，来自gal 104a的所有结果都与查询相匹配，因为它没有被零查询“污染”。
[0065]
为了说明起见，在示例中假设新结果中不存在重复项。可选地，该阶段的过程可能涉及类似于关于图3
‑
图4所描述的另一个重复项移除步骤。可选地，可以在任何或每个动态回填步骤中执行该重复移除，并将在此后的讨论中被视为已读。
[0066]
图9示出了将与查询
‘
j’相匹配的结果的子集从缓存组204移动到应用视图108中的下一个步骤。这可以根据与关于图5所描述的相同的方案来完成，即，从每个缓存组204向应用视图108传送最多为预定最大数量的结果，其中该预定数量可以由设计者、用户或应用103为每个组204独立设置。
[0067]
可以假设结果以相应源104的平均延时的顺序返回，但这对于要工作的策略不是必需的。假设例如设备联系人204a首先进来(因为他们在设备上)，然后是社交媒体联系人204c，然后是邮箱联系人204b，最后是gal结果204d。在实施例中，这些以先到先被服务的方式被添加到应用视图108。或者，它们可以先按组排序，然后按到达顺序排序。例如，在实施例中，应用103可以被布置为基于目标将被包含在结果中的几率，例如基于不同源104的预定平均相关性，来显示全部结果或结果的子集。
[0068]
填充大小现在已减少了大约为26的因子(英文字母表中的字母的数量)，因为用户选择了名字的一个字符，并假设名字是每字母均等分布的(作为非常粗略的近似)。然后，对于设备联系人104a、邮箱联系人104b、gal104d和社交网络104c，找到目标的机会分别增加到大约5％、1.5％、0.3％和3％。
[0069]
在所示的示例中，在应用视图缓存108中剩余四个空闲位置。基于此，应用103将附加两个新的设备联系人建议、一个社交网络建议和一个邮箱建议。在实施例中，应用103可以被布置为在此时从应用视图108忽略gal，因为在那里找到合适的人的几率仍然太低。
[0070]
随着这些结果被添加，将有可能立即对缓存组204进行另一次回填，再次匹配查询
‘
j’。然而，实施例不这样做：这可能不值得付出努力，因为应用视图108缓存已满，并且鉴于概率的这种分布以及缓存大小，源缓存组204将非常接近。然而，在其他实施例中，特别是如
果存在较大的源缓存与应用视图比率或非常高的平均相关性，则可以在此阶段进行另一次回填。
[0071]
该过程现在已经尽可能地基于用户键入一个字符来实现。由于用户正在寻找
‘
john’，那么他/她现在将键入第二个字符
‘
o’。作为响应，应用103立即识别针对“jo”的任何缓存命中。这些命中在图10中以阴影显示，即d11、t11、l13、g2和g7(作为示例)。
[0072]
如图11所示，应用103然后从应用视图108中过滤掉所有未命中项，并改为附加来自源缓存组204的匹配。应用视图108的未命中项可以被回收回缓存组，或者被丢弃，这取决于实施方式和可用的缓存大小。在说明的示例中，它们被逐出，因为应用将立即对缓存组204进行回填。因此，只与字母
‘
j’匹配的缓存命中被移除，且只保留与
‘
jo’匹配的结果。在替代实施方式中，在用户敲击退格键并打算键入不同的第二个字母的情况下，可以将命中“j”但未命中“jo”的结果回收回它们各自的缓存组204，与图7中针对第一个字母的情况类似。然而，此时用户很有可能已经提交了他的/她的搜索项(用户最有可能重新键入的字母是第一字母)。因此，在实施例中，如图11所示，没有这样做。
[0073]
实施例可以忽略缓存组204在第一键入字符上的排序，但是现在可以在第二组中考虑它。例如，基于上述概率，以及该集合现在将减少大约为26的另一个因子的事实，设计者可以将顺序设置如下：首先是设备联系人组204a，然后是社交网络组204c，然后是邮箱组204b，最后是gal组204d。逐出所有未命中后，缓存现在显现为如图11所示。这显示了针对
‘
jo’的当前缓存命中现在如何全部在应用视图108中，而其余的缓存组204已被逐出。
[0074]
随着第二个字符被键入，应用103还立即向源104a
‑
d发送针对
‘
jo’的搜索查询，以回填相应的缓存组204a
‑
d。这些现在被重新填充(在实施例中移除任何重复项，如前所述)。
[0075]
图12示出了缓存组的新动态回填(新检索的条目再次以斜线阴影示出)。现在所有结果都与查询
‘
jo’相匹配。
[0076]
如图13所示，然后应用103将再次将对这些新结果的选择附加到应用视图101，例如，根据与之前相同的方案：2个设备联系人、1个邮箱结果和1个社交网络结果(假设它们在所示示例中排在第一位)。在说明的示例中，应用103在此阶段不允许来自gal组204d的更多新结果进入应用视图108，因为来自其他组204a
‑
c的结果足够将应用视图缓存108填充到其最大容量并且gal 104d仍然是结果的最不可能的源。在图13中，之前的应用视图结果108(回填之前)仍然保留，并且集合中的所有结果仍然与查询
‘
jo’相匹配。
[0077]
现在考虑第三字符。假设仍未找到目标，用户现在键入第三字符“h”。应用103立即匹配针对
‘
joh’的缓存，如图14所示(再次以阴影显示命中)。在说明的例子中，只有d17和g13是缓存命中。
[0078]
如图15所示，应用103现在刷新缓存204，在应用视图108中仅保留d17和g13。它还基于查询
‘
joh’立即从源104重新填充缓存组204。
[0079]
此时，在源104中完全找到任何匹配的几率显著降低，因为搜索查询现在是三个字母，并且如果姓名中的字母是随机分布的，则命中姓名的几率为1/20000。这只是一个非常粗略的近似值，但假设除了已经在应用视图108中的结果(其在实施例中被去重复)之外，现在只有0、1、2和3个条目的子集分别与设备联系人204a、邮箱前n 204b、社交媒体联系人204c和gal 204e中的
‘
joh’相匹配。这最终会得到如图15所示的缓存。
[0080]
应用103然后将新的回填结果再次添加到应用视图108，假设在所示示例中的结果
集合序列相同。图16示出了所有缓存的结果如何被传输到应用视图108。目标现在应该在应用视图108中，因为在缓存组204中没有更多的建议。
[0081]
应当理解，仅通过示例的方式对上文的实施例进行了描述。
[0082]
例如，所公开的技术不仅适用于多个数据源104的情况。动态回填的想法也可以应用于单个数据源，以提升更快地检索和显示多个更相关结果的机会。此外，所公开的技术不局限于人物搜索的应用。在其他应用中，搜索到的条目可以是其他类型的数据记录，例如产品信息、管理记录等。此外，本公开内容的范围不局限于所公开的特定源。例如，源不必包括用户终端内部的内部数据源，或者不必包括用户终端外部的外部数据源。所公开的技术可以与列表、数据库或图表等形式的任何形式的一个或多个内部和/或外部数据源104的任意组合相关地使用。
[0083]
此外，结果不限于按照它们被接收的顺序显示。例如，可以根据诸如字母顺序之类的规则对其进行排序，或者首先是来自优选的一个源的结果，等等。在一些实施例中，接收顺序是结果排序所基于的唯一事物。然而，在其他替代实施例中，对于不同的源具有不同的缓存组的优点在于：可以人为地按组/源对结果进行排序，将来自最可能组的那些结果置于最前面。这两种方式都是可能的。固定的结果顺序也是可能的，这有利于延时之前的稳定性。不同的选项各有利弊：“先到先被服务”的方式有利于低延时，但牺牲了稳定性。固定顺序则相反。
[0084]
在所公开技术的进一步变体中，输入搜索查询之前的初始缓存填充不是必需的。相反，可以响应于搜索查询的条目，完全动态地检索和缓存搜索结果(尽管这会在输出第一结果之前增加一些额外的延时)。此外，虽然已经根据输入的搜索查询的每字符的缓存的动态回填来描述了上文的实施例，但更一般地，可以由用户输入的搜索查询的每部分来触发动态回填，其中，每个部分可以是一个或多个字符。例如，可以每两个字符触发一次动态回填，等等。
[0085]
更一般地，根据本文中公开的一个方面，提供了一种由用户终端执行的方法，该方法包括：接收在一个或多个数据源的集合中的多个条目之间搜索目标条目的搜索查询的部分，所述部分是按序列一个接一个地接收的；通过接收所述部分中的每个相应的部分来触发执行相应的缓存操作，包括：查询集合中的一个或多个数据源中的每个数据源以检索与搜索查询相匹配的条目，所述搜索查询由迄今为止按序列接收的部分或一些部分组成，以及将检索到的条目缓存在每个被查询的数据源的相应缓存组中；呈现应用视图，应用视图显示检索到的条目中的至少一些条目的可视化表示；以及对于每个缓存操作，基于搜索查询像现在一样包括搜索查询的相应部分在检索之后在缓存中选择一个或多个任意新检索的条目，以及更新应用视图以包括从缓存中选择的一个或多个条目。
[0086]
在实施例中，应用视图可以按照所选择的条目在用户终端处被接收的顺序来显示所选择的条目，或者应用视图可以显示按缓存组排序的所选择的条目，或者应用视图可以显示按缓存组排序并且然后在每个缓存组内按照条目在用户终端处被接收的顺序排序的所选择的条目。
[0087]
在实施例中，被查询的数据源中的至少一个数据源可以在用户终端外部，在这种情况下，从外部数据源检索的条目可以是经由网络检索的。
[0088]
在实施例中，被查询的数据源中的至少一个数据源可以在用户终端内部。
[0089]
在实施例中，该方法可以包括：在按所述序列接收部分中的任何部分之前，执行初始缓存填充操作以从数据源中的一个或多个数据源中的每个数据源检索一些初始条目并用其初始填充相应的缓存组；以及响应于按所述序列接收到搜索查询的第一部分，最初呈现应用视图以包括应用视图中迄今为止基于第一部分与搜索查询相匹配的任何初始条目中的一个或多个条目。
[0090]
在实施例中，数据源的集合可以是多个数据源的集合，并且被查询的数据源可以是所述集合中的多个数据源。在这种情况下，从每个被查询的数据源检索的条目被缓存在不同的相应缓存组中。
[0091]
在实施例中，这多个数据源可以各自具有从数据源到用户终端检索条目的不同延时。
[0092]
在实施例中，不同的源可以具有找到目标的不同概率、不同的访问限制和/或不同数量的条目。
[0093]
在实施例中，从不同数据源检索的条目可以被缓存在相同缓存层中，在缓存层和应用视图中的呈现之间具有基本相同的延时。
[0094]
在实施例中，对于每个缓存组，在每次最初呈现或更新应用视图时，应用视图中可以最多只包括迄今为止与搜索查询相匹配的最大数量的所检索的条目。最大数量在至少一些缓存组之间可以是不同的。
[0095]
在实施例中，该方法可以包括：对于每个缓存操作，移除从这些数据源中的两个或更多个数据源中检索到的一个或多个重复条目。
[0096]
在实施例中，从其检索初始条目的一个或多个数据源可以仅包括一旦检索到搜索查询的第一部分随后被查询的被查询的数据源的初始子集，初始子集排除被查询的数据源中在数量条目方面最大的一个或多个被查询的数据源。
[0097]
在实施例中，更新还可以包括：移除应用视图中不再与搜索查询相匹配的任何条目中的一个、多个或所有条目。
[0098]
在实施例中，搜索查询的所述部分中的每个部分都可以是个体字符(例如，字母)。
[0099]
在实施例中，多个条目中的每个条目可以是某一方的记录，每一方是一个人或一组人；目标条目可以是目标方的条目。
[0100]
在实施例中，搜索查询可以包括目标方的名称。
[0101]
在实施例中，被查询的数据源可以包括以下中的一项或多项：在用户终端上维护的设备联系人的列表；在用户终端外部维护的用户邮箱中用户的前n个联系人的列表；来自用户终端外部的社交网络服务的用户的社交网络联系人的列表或图表；和/或全局地址列表，其是用户是成员的组织内的联系人的全局列表，在用户终端外部维护。
[0102]
在实施例中，可以在前n个基础上检索来自至少一个源的条目，例如，用户的前n个联系人。例如，在初始缓存填充中，可以对用户的前n个条目(例如，联系人)进行缓存。和/或，在随后的缓存操作中，可以从源中的前n个之中检索迄今为止与搜索查询相匹配的条目，或者可以通过前m个匹配查询来检索。可以例如基于用户的过去行为来确定前n个，例如，他/她过去最频繁地访问哪些联系人，或者更一般地，他/她过去最频繁地与哪些条目进行交互。n可以是任何预定整数。
[0103]
根据本文中公开的另一方面，提供了一种计算机程序，其体现在计算机可读存储
装置上并被配置为：当在用户终端的一个或多个处理单元上运行时执行本文中公开的任意实施例的方法。
[0104]
根据另一个方面，提供了一种用户终端，其包括包含一个或多个存储单元的存储装置以及包含一个或多个处理单元的处理装置，存储装置存储代码，代码被布置为在处理装置上运行并且被配置为当在处理装置上运行时执行本文中公开的任意实施例的方法。
[0105]
一旦给出了本文的公开内容，所公开的技术的其他变体或用例对本领域技术人员来说可以变得显而易见。本公开内容的范围不受所描述的实施例的限制，而仅受所附权利要求的限制。