具有用于个人搜索的方法的多用户搜索系统

摘要

一种具有用于个人搜索的方法的多用户搜索系统。在一种实施例中，例如，用于个人搜索的系统包括存储多个索引碎片的多个索引服务器。多个索引碎片中的每一个索引碎片对多个文档进行索引。多个文档中的每一个文档属于分配给索引碎片的多个文档命名空间中的一个。该系统还包括用于从认证用户接收搜索查询的前端服务器计算机；用于确定认证用户被授权访问的授权文档命名空间的访问控制服务器；以及用于应答搜索查询并且基于授权文档命名空间的标识符限制对搜索查询的应答，以仅识别满足搜索查询并且属于授权文档命名空间的文档的查询处理器。

说明书

技术领域

公开的实施例一般而言涉及信息检索计算机系统，并且更具体而言，涉及具有用于个人搜索的方法的多用户搜索系统。

背景技术

计算机是用于在大量信息之中搜索相关信息的非常强大的工具。索引是用于使用计算机在大型信息语料库中高效识别感兴趣的信息的常见机制。典型的索引是关键字到从中提取或导出关键字的信息的文档的有组织的映射。作为示例，世界可公开访问的网页的索引可以将网页中的单词映射到包含那个单词的网页的子集。

在实际物理索引本身(例如，如存储在一个或多个计算机上的索引数据)和系统的用户之间，搜索系统通常被提供为软件缓冲器(cushion)或层。实质上，搜索系统使用户免于知道或甚至关心底层索引细节。通常，来自用户的对索引中的信息的所有请求由搜索系统处理。例如，可以由搜索系统使用索引来识别与用户对信息的请求相关的文档，所有这些都无需用户对底层索引实现的了解。以这种方式，搜索系统在无需关心信息是如何被索引或访问的情况下向用户提供对相关信息的访问。用于在世界可公开访问的网页中识别相关信息的一个众所周知的搜索系统是由加州山景城(Mountain View，California)的Google公司提供的GOOGLE互联网搜索引擎。

搜索系统的一个功能是应答搜索查询(或简称“查询”)。查询可以被定义为包括一个或多个搜索项的集合的逻辑表达式，并且导致识别索引文档的子集。例如，考虑处理来自互联网搜索引擎的对于信息的请求。在操作中，这种请求通常由客户端系统发出，作为用于从服务器计算机上的索引检索特定搜索结果(例如，包含单词“大学”和“篮球”的所有互联网网页的列表)的一个或多个超文本传输协议或“HTTP”请求。响应于这种请求，搜索系统通常返回包含到被认为与搜索项“大学”和“篮球”最相关的那些互联网网页的超链接的网页。

互联网搜索引擎非常适于搜索在互联网上公开可用的所有世界的信息。但是，近来，用户开始积累大量的“个人”数字信息，这些信息不是在互联网上可公开访问的或者不是由互联网搜索引擎索引的。这样的信息可以包括例如个人数字照片、学校和工作文档以及其它个人和私有数字信息。在一些情况中，用户的个人数字信息与所定义的一组用户共享。例如，员工可以与其他同事共享工作文档或者用户可以与朋友和家人共享数字照片。

用户最近开始存储和管理所有他们的个人数字信息的一种方式是通过使用云数据存储服务。这样的服务允许用户从他们的各种终端用户计算设备将他们的个人数字信息上传和存储在互联网或其它网络上可访问的服务器计算机上。在一些情况中，服务可以在终端用户计算设备和服务服务器计算机之间同步信息，以便于用户在终端用户计算设备处本地访问信息。一个众所周知的云数据存储服务是由加州旧金山(San Francisco，California)的Dropbox公司提供的DROPBOX内容管理服务。

云数据存储服务的用户将感激搜索和定位由此类服务托管的他们的个人数字信息的方式。这样的个人数字信息通常不能在互联网上公开访问。由于这个和其它原因，互联网搜索引擎通常不足以满足这些用户的搜索需求。

在本部分中描述的方法是可以实行的方法，但不必须是先前已经构想或实行的方法。因此，除非另外指出，否则不应当假定在本部分中描述的任何方法仅仅由于它们被包括在本部分中就有资格作为现有技术。

附图说明

图1是根据本发明的一些实施例的基本计算设备的框图。

图2是根据本发明的一些实施例的用于控制计算设备的操作的基本软件系统的框图。

图3是根据本发明的一些实施例的包括多用户搜索系统的客户端/服务器系统的框图。

图4是根据本发明的一些实施例的多用户搜索系统的服务系统的框图。

图5是根据本发明的一些实施例的分片文档索引的索引碎片的框图。

图6是图示根据本发明的一些实施例的由多用户搜索系统的服务系统执行的个人搜索的过程的流程图。

图7是图示根据本发明的一些实施例的由路由服务器执行的用于确定存储对属于给定文档命名空间的文档进行索引的索引碎片的索引服务器的过程的流程图。

图8是图示根据本发明的一些实施例的由索引服务器处的查询处理器执行的、用于生成对非完成查询的个性化应答的过程的流程图。

图9是图示根据本发明的一些实施例的由索引服务器处的查询处理器执行的、用于生成对完成查询的个性化应答的过程的流程图。

具体实施方式

在下面的描述中，为了解释的目的，阐述了许多具体细节以提供对所公开的技术的透彻理解。但是，将显而易见的是，可以在没有这些具体细节的情况下实践所公开的技术。在其它情况中，以框图形式示出众所周知的结构和设备，以避免不必要地模糊所公开的技术。关于流程图，流程图内的方框可以表示方法步骤和用于执行方法步骤的装置元件。取决于当前特定实现的要求，可以在硬件、软件、固件或其组合中配置对应的装置元件。

还将理解的是，尽管在本文中可以使用术语“第一”、“第二”等来描述各种元件，但是这些元件不应当被这些术语限制。这些术语仅用于将一个元件与另一个元件进行区分。例如，在不脱离本发明的范围的情况下，第一设备可以被称为第二设备，并且类似地，第二设备可以被称为第一设备。第一设备和第二设备两者都是设备，但它们不是相同的设备。

本文所使用的术语只出于描述特定实现的目的，而不是旨在限制权利要求。如在本说明书和所附权利要求中所使用的，除非上下文其它方式明确指示，否则单数形式“一”、“一个”和“该”旨在也包括复数形式。还将理解的是，如本文所使用的术语“和/或”是指并且包括相关联的所列的项目中的一个或多个的任何和所有可能的组合。还将理解的是，当在本说明书中使用时，术语“包括”、“包含”、和/或“含有”指定所述的特征、整数、步骤、操作、元件和/或组件的存在，但不排除一个或多个其它特征、整数、步骤、操作、元件、组件和/或其组合的存在或添加。

取决于上下文，术语“如果”可以被解释为意指“当…时”或“在…时”或“响应于确定”或“响应于检测”。类似地，取决于上下文，短语“如果确定”或“如果检测到[条件或事件]”可以被解释为意指“在确定时”或“响应于确定”或“在检测到[所述条件或事件]时”或“响应于检测到[所述条件或事件]”。

概述

公开了一种具有用于搜索个人文档的方法的多用户计算机搜索系统。文档可以包括例如用户的个人文档，诸如例如，与用云数据存储服务持有的用户帐户相关联的文档。

在其它方面之外，本发明的各种实施例还有助于在多用户计算机搜索系统中对用户的个人文档进行全文本和文件名搜索。

在其它方面之外，本发明的各种实施例还实现了在使用计算机进行信息检索的技术领域的改进。

在其它方面之外，本发明的各种实施例还改进了由云数据存储服务提供商提供的多用户云数据存储服务。

在其它方面之外，本发明的各种实施例还改进了多用户计算机搜索系统的运行。

根据本发明的一种实施例，多用户计算机系统在多个索引服务器处存储多个索引碎片。多个索引碎片中的每一个索引碎片对多个文档进行索引。通过索引碎片进行索引的多个文档中的每一个文档属于分配给索引碎片的多个文档命名空间中的一个。该系统还实现用于个人搜索的方法，包括：从认证用户接收搜索查询；确定认证用户被允许访问的授权文档命名空间；以及基于授权文档命名空间的标识符限制对搜索查询的应答，以仅识别满足搜索查询并且属于授权文档命名空间的文档。

在本发明的另一种实施例中，该方法包括以下步骤：基于授权文档命名空间标识符识别多个索引服务器中存储授权文档命名空间所分配到的索引碎片的索引服务器；以及将搜索查询发送到识别出的索引服务器。

在本发明再另一种实施例中，该方法包括基于将确定性映射函数应用于授权文档命名空间标识符的结果，选择多个索引服务器中要向其发送搜索查询的索引服务器。

在本发明再另一种实施例中，多个索引碎片中的索引碎片包括索引令牌和多个对应的帖子列表(posting list)的字典。每一个帖子列表将对应的令牌映射到一个或多个文档标识符，并且帖子列表的每一个文档标识符与由该文档标识符识别的文档所属的文档命名空间的标识符相关联。

在本发明再另一种实施例中，该方法还包括以下步骤：将授权文档命名空间标识符与和多个索引碎片中的索引碎片的帖子列表中的文档标识符相关联的文档命名空间标识符进行比较，以确定由文档标识符识别的哪些文档属于该授权文档命名空间。

在其它方面，本发明包括被配置成执行前述步骤的计算机系统和计算机可读介质。

基本计算机系统硬件和软件

所公开的技术可以在一个或多个计算设备上实现。这样的计算设备可以以各种形式实现，包括但不限于，客户端、服务器计算机、网络设备、移动设备、蜂窝电话、智能电话、膝上型计算机、桌面计算机、工作站计算机、个人数字助理、刀片服务器计算机、大型计算机和其它类型的计算机。下面描述的计算设备及其组件，包括它们的连接、关系和功能，仅仅是示例性的，并不意味着限制本说明书中描述的所公开的技术的实现。适于实现所公开的技术的其它计算设备可以具有不同的组件，包括具有不同连接、关系和功能的组件。

基本计算设备

现在转到图1，它是根据本发明的一些实施例的适于实现所公开的技术的基本计算设备100的框图。计算设备100包括总线102或用于寻址主存储器106和用于在设备100的各种组件之间和当中传输数据的其它通信机制。计算设备100还包括与总线102耦合用于处理信息的硬件处理器104。硬件处理器104可以是通用微处理器、片上系统(SoC)、或者适于实现所描述的技术的其它处理器。

主存储器106(诸如，随机存取存储器(RAM)或其它动态存储设备)耦合到总线102，用于存储要由处理器104执行的信息和指令。主存储器106还可以用于在要由处理器104执行的指令的执行期间存储临时变量或其它中间信息。当存储在处理器104可访问的非瞬态存储介质中时，这些指令使计算设备100呈现为被定制以执行指令中指定的操作的专用计算设备。

计算设备100还包括耦合到总线102用于存储静态信息和用于处理器104的指令的只读存储器(ROM)108或其它静态存储设备。

大容量存储设备110耦合到总线102，用于在固定或可移动介质(诸如，磁、光、固态、磁光、闪存或任何其它可用的大容量存储技术)上持久地存储信息和指令。大容量存储设备可以在网络上共享，或者它可以是专用的大容量存储设备。通常，大容量存储设备110(例如，用于设备的主硬盘)存储用于指导计算设备的操作的程序主体和数据，包括操作系统、用户应用程序、驱动和其它支持文件，以及其它各种数据文件。

计算设备100可以经由总线102耦合到显示器112(诸如，液晶显示器(LCD)或其它电子视觉显示器)用于向计算机用户显示信息。显示器112还可以是用于向处理器104传送触摸手势(例如，手指或触控笔)输入的触敏显示器。

包括字母数字和其它键的输入设备114耦合到总线102，用于向处理器104传送信息和命令选择。

另一种类型的用户输入设备是光标控件116(诸如，鼠标、轨迹球或光标方向键)，用于向处理器104传送方向信息和命令选择以及用于控制显示器112上的光标移动。这种输入设备通常具有允许设备指定平面中的位置的两个轴(第一轴(例如，x)和第二轴(例如，y))中的两个自由度。

计算设备100可以使用与计算设备结合使得或者将计算设备100编程为专用机器的定制的硬连线逻辑、一个或多个专用集成电路(ASIC)、一个或多个现场可编程门阵列(FPGA)、固件或程序逻辑来实现本文所描述的方法。

还可以由计算设备100响应于处理器104执行包含在主存储器106中的一个或多个指令的一个或多个序列来执行本文所公开的方法。这些指令可以从另一个存储介质(诸如，存储设备110)读取到主存储器106中。包含在主存储器106中的指令序列的执行使得处理器104执行本文所描述的过程步骤。在替代实施例中，硬连线电路系统可以代替软件指令或与软件指令组合使用。

如本文所使用的术语“存储介质”是指存储使得计算设备以特定方式操作的数据和/或指令的任何非瞬态介质。这样的存储介质可以包括非易失性介质和/或易失性介质。非易失性介质包括例如光盘、磁盘或固态驱动器(诸如，存储设备110)。易失性介质包括动态存储器(诸如，主存储器106)。存储介质的常见形式包括例如软盘、柔性盘、硬盘、固态驱动器、磁带或任何其它磁性数据存储介质、CD-ROM、任何其它光学数据存储介质、具有孔图案的任何物理介质、RAM、PROM和EPROM、FLASH-EPROM、NVRAM、任何其它存储器芯片或盒(cartridge)。

存储介质与传输介质不同但是可以与其结合使用。传输介质参与在存储介质之间传输信息。例如，传输介质包括同轴电缆、铜线和光纤，包括包含总线102的导线。传输介质还可以采用声波或光波的形式，诸如在无线电波和红外数据通信期间生成的那些。

各种形式的介质可以涉及将一个或多个指令的一个或多个序列携带到处理器104用于执行。例如，最初可以在远程计算机的磁盘或固态驱动器上携带指令。远程计算机可以将指令加载到它的动态存储器中并且使用调制解调器在电话线上发送指令。计算设备100本地的调制解调器可以接收电话线上的数据并且使用红外发射器将数据转换成红外信号。红外检测器可以接收携带在红外信号中的数据，并且适当的电路系统可以将数据放置在总线102上。总线102将数据携带到主存储器106，处理器104从主存储器106检索并执行指令。由主存储器106接收到的指令可以可选地在由处理器104执行之前或之后存储在存储设备110上。

计算设备100还包括耦合到总线102的通信接口118。通信接口118提供耦合到有线或无线网络链路120的双向数据通信，其中有线或无线网络链路120连接到本地网络122(例如，以太网、无线局域网、蜂窝电话网络、蓝牙无线网络等)。通信接口118发送和接收携带表示各种类型的信息的数字数据流的电、电磁或光信号。例如，通信接口118可以是有线网络接口卡、具有集成无线电天线的无线网络接口卡、或者调制解调器(例如，ISDN、DSL或电缆调制解调器)。

网络链路120通常通过一个或多个网络向其它数据设备提供数据通信。例如，网络链路120可以通过本地网络122提供到主机计算机124或到由互联网服务提供商(ISP)126运营的数据装备的连接。ISP 126又通过现在通常称为“互联网”128的世界范围的分组数据通信网络提供数据通信服务。本地网络122和互联网128使用携带数字数据流的电、电磁或光信号。携带去往和来自计算设备100的数字数据的通过各种网络的信号和网络链路120上以及通过通信接口118的信号是传输介质的示例形式。

计算设备100可以通过本地网络122、互联网128、ISP 126、网络链路120和(一个或多个)通信接口118发送消息和接收数据，包括程序代码。在互联网的示例中，服务器计算机130可以通过互联网128、ISP 126、本地网络122和通信接口118发送对于应用程序的请求代码。

接收到的代码可以在其被接收到时由处理器104执行，和/或存储在存储设备110或其它非易失性存储器中用于以后执行。

基本软件系统

现在转到图2，它是根据本发明的一些实施例的用于控制计算设备100的操作的基本软件系统200的框图。如所示的，提供计算机软件系统200用于指导计算设备100的操作。存储在系统存储器(RAM)106中和固定存储设备(例如，硬盘)110上的软件系统200包括内核或操作系统(OS)210。OS 210管理计算机操作的低级方面，包括管理进程的执行、存储器分配、文件输入和输出(I/O)和设备I/O。一个或多个应用程序202(例如，202A、202B、202C...202N)可以被“加载”(例如，从固定存储设备110传输到存储器106中)用于由系统200执行。在一些情况中，打算在设备100上使用的应用程序202或其它软件也可以存储为一组可下载的计算机可执行指令，例如，用于从互联网位置(例如，从web服务器)下载和安装。

软件系统200可以包括图形用户界面(GUI)215，用于以图形(例如，“点击”或“触摸手势”)方式接收用户命令和数据。根据来自操作系统210和/或应用程序202的指令，系统200又可以按照这些输入行事。GUI 215还用于显示来自OS 210和应用程序202的操作的结果，由此用户可以提供附加输入或终止会话(例如，登出)。

OS 210可以直接在设备100的裸硬件(例如，处理器104)上执行。可替代地，可以在裸硬件和OS 210之间插入管理程序或虚拟机监视器(VMM)230。在这种配置中，VMM 230充当设备100的OS 210和裸硬件之间的软件“缓冲器”或虚拟化层。

VMM 230(如果存在)实例化并且运行虚拟机实例(“客户机”)。每一个客户机包括“客户”操作系统(诸如，OS 210)以及被设计成在客户操作系统上执行的一个或多个应用程序(诸如，应用程序202)。VMM 230向客户操作系统呈现虚拟操作平台并管理客户操作系统的执行。在一些情况中，VMM 230可以允许客户操作系统就像它正在设备100的裸硬件上直接运行那样运行。在这些情况中，也可以能够在无需修改或重新配置的情况下在VMM 230上执行被配置成直接在裸硬件上执行的相同版本的客户操作系统。换句话说，在一些情况中，VMM 230可以向客户操作系统提供完全的硬件和CPU虚拟化。在其它情况中，客户操作系统可以被专门设计或配置成为了效率在VMM 230上执行。在这些情况中，客户机操作系统“意识到”它在虚拟机监视器上执行。换句话说，在一些情况中，VMM 230可以向客户操作系统提供半虚拟化(para-virtualization)。

出于说明可以被采用用于实现所公开的技术的基本底层计算机组件的目的呈现了上述计算机硬件和软件。但是，所公开的技术不限于任何特定的计算环境或计算设备配置。相反，可以在能够支持下面详细呈现的所公开的技术的任何类型的系统体系架构或处理环境中实现所公开的技术。

客户端/服务器多用户搜索系统组件

现在转到图3，它是根据本发明的一些实施例的客户端/服务器系统300的框图。客户端/服务器系统300包括一个或多个服务器320(本文统称为“多用户搜索系统320”)。而且，客户端/服务器系统300包括经由网络330连接到一个或多个服务器325(本文统称为“服务系统325”)的一个或多个客户端310。具体而言，客户端310包括使用常规网络连接到一个或多个服务器326(本文统称为“搜索前端326”)的一个或多个终端用户计算设备311。在示例性实施例中，终端用户计算设备311本身可以包括多个终端用户个人计算设备，诸如，运行常规操作系统(诸如，MICROSOFT WINDOWS(例如XP、VISTA、WINDOWS 7、WINDOWS 8等)、MACOS X、LINUX(例如，UBUNTU、FEDORA等)、IOS、ANDROID、BLACKBERRY OS等)的上述设备100。

在示例性实施例中是以上提到的DROPBOX内容管理服务的一部分的服务系统325和一个或多个其它服务器321(本文统称为“构建系统321”)通常操作为在服务器操作系统(诸如，UNIX、LINUX等)下运行的一个或多个独立的进程(例如，独立于客户端)。构建系统321包括令牌存储器324、索引器服务器323(或者仅仅“索引器323”)和令牌化器(tokenizer)322(或者仅是“令牌化器322”)。除搜索前端326之外，服务系统325还包括查询处理器327和文档索引328。

取决于当前特定实现的要求，包括构建系统321的服务器和服务系统325的服务器的多用户搜索系统320的服务器可以实现为服务器计算机(例如，图1的设备100)或实现为虚拟机实例。在多用户搜索系统320的服务器实现为虚拟机实例时，仍然可以存在托管(执行)“虚拟”服务器的底层服务器计算机。但是，在虚拟服务器和服务器计算机之间不必须存在一一对应。例如，服务器计算机可以托管若干虚拟服务器。

如在本描述和所附权利要求中所使用的，除非上下文其它方式明确指示，否则单数形式“服务器”旨在也包括复数形式。例如，多用户搜索系统320的“服务器”实际上可以由若干服务器实现，这些服务器是彼此的镜像或副本，用于根据当前特定实现的要求进行负载平衡、故障转移、冗余、高可用性和/或其它目的。

在操作中，客户端310向搜索前端326发送搜索查询332并从搜索前端326接收对其的查询应答334。可以在搜索前端326处在网络请求中接收查询332并且可以从搜索前端326在对网络请求的网络响应中发送应答334。可以在网络330上在网络数据分组中接收/发送网络请求和网络响应。在本发明的一些实施例中，网络数据分组根据互联网协议(IP)被格式化。也可以根据应用层联网协议接收/发送网络请求和网络响应。在一些实施例中，应用层联网协议是超文本传输协议(HTTP)或安全超文本传输协议(HTTPS)。例如，可以在一个或多个HTTP或HTTPS请求中接收查询332，并且可以在对其的一个或多个HTTP或HTTPS响应中发送应答334。

网络330可以包括数种常规的有线或无线网络系统，包括例如，蜂窝电话网络、局域网(LAN)、广域网(WAN)、互联网等。服务系统325和构建系统321及其服务器也可以通过一个或多个IP网络和/或其它合适类型的数据通信网络互连并且也可以使用HTTP和/或HTTPS和/或其它适当的应用层协议彼此通信。

搜索查询332可以包括搜索表达式。搜索表达式的语法可以包括可能由一个或多个布尔运算符(例如，与(AND)、或(OR)、非(NOT)等)关联在一起的一个或多个查询令牌的序列。令牌可以被定义为一个或多个字符的序列。可以根据常规字符编码方案(例如，ASCII、UTF-8等)编码令牌中的字符。

查询令牌可以被定义为出现在搜索查询332中的令牌。例如，考虑简单的连接查询332：[baguette fromage](没有包围的括号)。满足这个查询332的文档340可以包含令牌“baguette”和令牌“fromage”两者，而在文档340中不必彼此相邻，并且令牌“baguette”在文档340中不必出现在令牌“fromage”之前。但是，包含或者与彼此接近的令牌“baguette”和“fromage”相关联并且与令牌“baguette”在令牌“fromage”之前相关联的文档340可以被认为比满足查询332的其它文档340更相关。

从搜索前端326返回到客户端(例如，终端用户计算设备311A)的对搜索查询332的查询应答334可以包括按照相关性排序的列表搜索应答总结。每一个这种总结可以对应于由查询处理器327在满足搜索查询332的文档索引328中识别的文档340。搜索应答总结可以包括例如对应文档的标识符(例如，名称、标题等)、对应文档的简短描述(例如，概要、摘要、摘录、片段等)、用于下载、查看对应文档或在对应文档上采取某些其它用户动作的交互式超链接(例如，统一资源定位符(URL))、以及关于对应文档340的可能的其它有用信息(例如，对应文档的缩略图图像)。可以例如在终端用户计算设备上执行的web浏览器应用中的网页上或者例如在终端用户计算设备上执行的应用(例如，移动应用)的另一个图形用户界面中将总结的列表呈现给终端用户计算设备的用户。

在搜索前端326处接收到的搜索查询332可以由查询处理器327处理。查询处理器327可以咨询文档索引328以识别满足搜索查询332的文档。可以在应答334中返回对由查询处理器327识别的满足搜索查询332的文档的引用(例如，超链接)。在本发明的一些实施例中由查询处理器327执行的用于处理查询332的技术可以如下面更详细描述的那样。

在一些情况中，搜索查询332是“完成”搜索查询332。完成搜索查询332可以被定义为包括一个或多个查询令牌的序列的搜索查询332，其中一个查询令牌不是完整的。例如，当终端用户计算设备的用户处于输入(例如，通过键入)完成搜索查询332的查询令牌之一的中间(例如，过程中)时，完成搜索查询332可能从终端用户计算设备(例如，311A)提交到搜索前端326。在这种情况中，对完成查询332的应答334可以包括查询处理器327基于完成查询332在文档索引328中识别的对完成搜索查询332的可能的完成的列表。

在完成查询332中的完整的查询令牌在本文中被称为“完整令牌(completetoken)”。在完成查询332中的不完整的查询令牌在本文中被称为“完成令牌(completiontoken)”。因此，完成查询也可以被定义为包括完成令牌的查询332。

完成查询332可以仅包括单个字符或多于一个字符。例如，在完成查询332[p](没有包围的括号)中，可以没有完整的令牌并且令牌“p”可以是完成令牌。完成查询332可以替代地包括一个或多个完整令牌。例如，在完成查询332[private se](没有包围的括号)中，令牌“private”可以是完整令牌并且令牌“se”可以是完成令牌。

通常，完成查询332的令牌序列中的最后一个令牌(或者如果在序列中只有一个令牌时的该唯一令牌)是完成令牌。通常，这是因为用户以完成查询332的令牌在序列中出现的相同顺序输入它们。但是，完成查询332的最后一个令牌之外的令牌可以是完成令牌。例如，用户可以在他或她的终端用户计算设备(例如，311A)处移动输入光标以编辑先前输入的令牌。例如，用户可以在第一时间输入查询332[solved two problems](没有包围的括号)。后来，用户可以移动输入光标以用“th”替换令牌“two”以生成完成查询[solved thproblems]。在这个示例完成查询332中，第一令牌“solved”和最后一个令牌“problems”可以是完整令牌并且第二令牌“th”可以是完成令牌。

在本发明的一些实施例中，查询332被指定为包括查询332的网络请求中的完成查询332。例如，网络请求可以指示查询332的查询令牌是完成令牌。可以由在用户的终端用户计算设备(例如，311A)处执行的软件来进行完成令牌的识别。例如，当用户正在(例如，使用物理键盘或软键盘)将查询332的令牌的字符输入到在用户的终端用户计算设备处呈现的搜索用户界面中时，软件可以将包括查询332的网络请求发送到搜索前端326。在这样做时，软件可以在(例如，具有元数据的)网络请求中标记、作记号、识别或以其它方式指示用户正在输入的令牌是完成令牌。在本发明的一些实施例中，在用户的终端用户计算设备处执行的软件是JAVASCRIPT软件或其它web浏览器客户端脚本语言软件，并且搜索用户界面呈现在用户的web浏览器的窗口中显示的网页上。在本发明的一些实施例中，在用户的终端用户计算设备处执行的软件是在用户的终端用户计算设备处驱动搜索用户界面的移动应用或其它专用软件应用。

完成搜索查询332的可能的完成可以被定义为由通过文档索引328索引的至少一个文档340满足的并且完成完成查询332的搜索查询332。例如，由通过文档索引328索引的至少一个文档340满足的搜索查询332[solved two problems](没有包围的括号)可以是完成搜索查询332[solved two prob](没有包围的括号)的可能的完成。在满足完成查询332的文档340的搜索应答总结的列表之外或作为替代，可以在应答334中提供完成查询332的可能的完成的列表。在本发明的一些实施例中由查询处理器327采用的、用于处理完成查询332的技术可以如下面更详细描述的那样。

不是完成查询332的查询332在本文中有时可以被称为“非完成”查询332，以将查询332与完成查询332区分。非完成查询332也可以被定义为仅包含完整令牌并且不包含任何完成令牌的查询332。当一般地引用查询332时，本文可以引用前面没有“完成”或“非完成”限定符的“查询332”或“搜索查询332”。除非在上下文中另外清楚地出现，否则本文关于查询332的描述通常关于完成查询332和非完成查询332两者。

文档340可以被定义为包含文本内容(例如，字符数据)和/或与文本内容(例如，文本元数据)相关联的数字信息的集合。仅作为一些示例，文字处理文档340通常包含文本上下文(例如，文档的创作词和句子)，电子表格文档340可以包含单词和数字形式的文本上下文，以及数字图像文档340(例如，数字照片)可以在它的首部(例如，可交换图像文件格式(Exif))中包含文本内容。附加地或可替代地，数字图像文档340可以以文本元数据标签或图像内容的其它文本描述的形式与文本内容相关联。这些仅仅是可能类型的文档的一些示例并且其它类型的文档也在本发明的范围内。

在一些情况中，文档340对应于具有文件类型的文件。可以是文档的一些类型的文件包括但不限于图像文件(例如，.jpg、.GIFf、.gif)、音乐文件(例如，.mp3、.aiff、.m4a、.wav)、电影文件(例如，.mov、.mp4、.m4v)、字处理文件(例如，.doc、.docx、.pages)、演示文件(例如，.ppt、.pptx、.key)、电子表格文件(例如，.xlsx、.xlsx、.numbers)、网页文件(例如，.htm、.html)、文本文件(例如，.txt)、以及包含和/或与文本相关联的任何其它类型的文件。

文档340可以与描述文档内容的文本上下文相关联。这种相关联的文本内容有时被称为文档的“文本元数据”。例如，文档340的文件名可以是文档340的文本元数据。作为另一个示例，可以通过图像的计算机分析(例如，光学字符识别(OCR)、面部识别算法等)产生数字图像文档的文本元数据。文档340的文本元数据的其它形式可以包括例如从引用文档340(例如，通过超链接)、提及文档340(例如，在社交网络帖子中)、或讨论文档340(例如，在博客和/或用户评论帖子中)的网页获得的关于文档340的文本内容。出于本描述的目的，文档340的文本元数据可以被认为是文档340的文本内容的一部分并且包含(出现)在文档340的文本内容中。

文档340还可以具有若干版本，其中之一被认为是当前版本。例如，用户可以使用文字处理程序创建并保存文字处理文档340的第一版本。一些时间以后，用户可以修改文档340的第一版本并保存包含修改的文档340的第二版本。可替代地，文档340可以在某一时间只具有一个被认为是当前版本的版本。

文档索引328可以包括一个或多个字典和帖子对。字典对可以存储索引令牌，并且还可以包括到用于每一个索引令牌的帖子对中的帖子列表的指针。例如，指针可以是其中存储帖子列表的易失性或非易失性存储器中的位置的地址。

索引令牌可以被定义为文档340通过其在文档索引328中被索引的令牌。除了索引令牌之外，字典还可以存储索引令牌的令牌属性，诸如例如，令牌的文档频率。索引令牌的令牌属性可以由查询处理器327使用以提高查询处理效率和搜索结果排名。

索引令牌的帖子列表可以存储其中令牌出现的一个或多个文档340的一个或多个文档标识符的列表，并且还可以存储在帖子列表中识别出的文档340的文档-令牌属性，诸如例如，文档340中令牌的频率、或者文档340内令牌的(一个或多个)位置。帖子列表中文档340的文档-令牌属性也可以由查询处理器327使用以提高查询处理效率和搜索结果排名。

当处理查询332时，查询处理器327可以基于查询332中的查询令牌在文档索引328的字典中定位索引令牌。例如，对于诸如[solved two problems](没有包围的括号)的查询332，查询处理器327可以在字典中定位索引令牌“solved”、“two”和“problems”。查询处理器327可以使用与字典中所定位的索引令牌相关联的指针来检索所定位的索引令牌的帖子列表。例如，查询处理器327可以从与索引令牌“solved”、“two”和“problems”的字典帖子列表相关联的文档索引328的帖子中检索(例如，加载到RAM中)。

查询处理器327可以使用合并算法来合并检索到的帖子列表以识别满足查询332的文档340。例如，假设为索引令牌“solved”检索到的帖子列表识别文档D2和D3、为索引令牌“two”检索到的帖子列表识别文档D2、并且为索引令牌“problems”检索到的帖子列表识别文档D2和D3。查询处理器327然后可以根据合并算法合并这三个帖子列表以将文档D2识别为包含所有定位的索引令牌。可以使用各种不同的合并算法用于合并帖子列表并且本发明不限于任何特定的合并算法。例如，合并算法可以通过指针交错前进经过若干帖子列表中的每一个来组合若干帖子列表。

查询处理器327不限于仅处理简单的连接查询332并且查询处理器327可以处理更复杂的查询332。例如，查询处理器327可以处理以下示例类型的查询332：查询A：[(two orthree)NOT problems]，查询B：[two three problems]，查询C：[(two three)problem]和查询D：[(two OR three)(problems OR solutions)]。在包围的括号[]内的上述示例查询332的每一个中，包围的括号[]不是查询的一部分。查询A等效于查询332[(two or three)AND NOT problems]，查询B等效于布尔查询332[two AND three AND problems]，查询C等效于布尔查询332[(two AND three)AND problems]，以及查询D等效于布尔查询332[(twoOR three)AND(problems OR solutions)。在前述示例查询332中，AND OR NOT()是布尔运算符。

在本发明的一些实施例中，跨服务系统325的多个索引服务器水平分区(例如，分片)文档索引328，其中每一个索引服务器存储文档索引328的一部分(例如，碎片)。可以使用各种不同的技术跨索引服务器水平分区(例如，分片)索引328。在本发明的一些实施例中，由“文档命名空间”分片文档索引328。

文档命名空间可以被定义为在公共访问控制下的一个或多个文档340的集合。公共访问控制可以基于明确和/或隐含的许可，其指定和/或指示哪(一个或多个)用户和/或用户的(一个或多个)组可以访问文档命名空间中的文档340，以及(一个或多个)用户和/或用户的(一个或多个)组对属于文档命名空间的文档340具有什么访问(例如，读取访问、写访问、共享访问、预览访问、下载访问等中的一个或多个)。明确许可可以来自例如一个或多个访问控制列表(ACL)和/或与文档命名空间(或其标识符)相关联的其它数据的形式，该明确许可指定和/或指示哪(一个或多个)用户和/或用户的(一个或多个)组可以访问文档命名空间中的文档340，以及(一个或多个)用户和/或(一个或多个)组对文档命名空间中的文档340具有什么访问。隐含许可的一个示例可以是：用户可以访问与用户的帐户(或其标识符)相关联的文档命名空间中的所有文档340。

在示例性实施例中，文档命名空间包括与用云数据存储服务(诸如例如，前面提到的DROPBOX内容管理服务)保持的用户帐户相关联的文档340。通过对帐户成功地认证(例如，使用有效的用户名/密码)，用户隐含地访问与用户帐户相关联的文档命名空间中的文档340。

在示例性实施例中，文档命名空间包括属于一个或多个文档340的集合的文档340，该集合在用云数据存储服务(例如，前面提到的DROPBOX内容管理服务)保持的若干用户帐户之间共享。在一些情况中，文档的集合可以被称为“共享文件夹”。通过对文档集合与其共享的帐户成功地认证，用户可以访问共享文档命名空间中的文档。

根据其中由文档命名空间分片文档索引328的本发明的一些实施例，服务系统325的多个索引服务器中的每一个对属于一个或多个文档命名空间的文档340进行索引。在本发明的一些实施例中，文档命名空间的标识符用作碎片关键字以确定对文档命名空间中的文档340进行索引的索引服务器。在非限制性的示例性实施例中，文档索引328对超过四亿(400,000,000)个文档命名空间中的文档进行索引。

文档340可以包括被提供或使得可用于由构建系统321处理或在文档索引328中被索引的任何文档340。构建系统321从文档340构建文档索引328的索引数据库文件351。构建系统321还从文档340生成对文档索引328的索引变化352。

索引数据库文件351可以包括一起对一个或多个文档340进行索引的字典和帖子对。非常一般地，索引数据库文件351内的数据可以被构造为键-值对的集合(例如，关联数组)，其中键对应于字典的索引令牌并且值对应于帖子的帖子列表。在本发明的一些实施例中，索引数据库文件351对一个文档命名空间中的文档340进行索引。在本发明的一些实施例中，为了减少文档索引328的索引数据库文件351的数量，索引数据库文件351对若干文档命名空间中的文档340进行索引。由索引数据库文件351索引的若干文档命名空间在本文中有时被称为文档命名空间的“文档命名空间组”。

由构建系统321构造文档索引328的索引数据库文件351可以涉及令牌化器322，其通过令牌化文档340生成令牌集合并将生成的令牌集合存储在令牌存储器324中。索引器323然后可以基于生成的令牌集合生成索引数据库文件351。索引器323将生成的索引数据库文件351提供给服务系统325，用于存储在服务系统325的索引服务器上作为文档索引328的一部分。

由构建系统321从文档340生成对索引文档328的索引变化352可以涉及令牌化器322在从最近创建或最近修改的文档340生成令牌集合之后通知索引器323。例如，终端用户计算设备311的用户可以已经最近创建或最近修改文档340。当被通知最近创建的文档340时或者当被通知修改的文档340时，索引器323基于在令牌存储器324中为文档存储的一个或多个令牌集合生成文档的索引变化352。在一些情况中(诸如例如，当文档已被修改时)，生成的索引变化352反映为修改的文档生成的令牌集合与为文档的先前版本生成的令牌集合之间的差异。生成的索引变化352可以提供给服务系统325，服务系统325然后对其应用文档索引328。

令牌化器322通过对文档340的文本内容进行令牌化来产生令牌集合。令牌化文档的文本内容可以包括获得文档的字符序列。取决于文档数据的格式，令牌化器322可以使用各种技术来获得文档的字符序列。例如，使用的一种或多种技术可以包括取决于文档的字符编码方案(例如，ASCII、Unicode UTF-8、MICROSOFT WORD、ADOBE PDF等)解码文档和/或取决于文档是否被压缩(例如，通过ZIP压缩)解压文档。

一旦获得文档的字符序列，令牌化器322就将字符序列划分成称为令牌的片段，可能同时对令牌执行语言处理。语言处理可以包括例如忽略某些字符(例如，标点符号)、丢弃常用单词(例如，停止词)和/或进行词干提取(stemming)和词形还原(lemmatization)。语言处理还可以包括令牌标准化，包括去除变音符号和重音和/或大写化/大小写转换等。

在令牌化器322已经为文档生成令牌集合之后，令牌化器322将令牌集合存储在令牌存储器324中。在一些情况中，诸如例如，当令牌化器322向索引器323通知最近创建的文档340时，或者向索引器323通知最近修改的文档340时，令牌化器322也可以将令牌集合提供给索引器323。

令牌存储器324存储由令牌化器322为文档340生成的令牌集合。例如，对于给定版本的文档340，令牌存储器324可以存储由令牌化器322为那个文档版本生成的令牌集合。

在本发明的一些实施例中，令牌存储器324包括面向列的、分布式数据库系统，诸如例如，APACHE HBASE数据库系统。但是，在其它实施例中，根据当前实现的特定要求可以使用其它类型的数据库系统。例如，可以使用专有的、关系型或独立的数据库系统，而不是开源的、面向列的或分布式数据库系统。

考虑到上述示例性客户端-服务器多用户搜索系统320，现在将更详细地描述用于处理查询332并向其返回个性化应答334的服务系统325及其组件。

服务系统组件

现在转到图4，它是更详细地图示根据本发明的一些实施例的服务系统325的组件的框图。服务系统325包括一个或多个服务器326(本文统称为“前端服务器326”)、一个或多个服务器410(本文统称为“访问控制服务器410”)和查询处理器327。

查询处理器327分布在两级服务器上：(1)一个或多个服务器430(统称为“索引服务器430”)，其负责存储文档索引328并且负责处理针对文档索引328的索引碎片(例如，328A、328B、328C...328N)的查询332，以及(2)一个或多个服务器430(统称为“路由服务器420”)，其负责基于与查询332相关联的文档命名空间标识符将查询332从前端服务器326路由到适当的索引服务器430并且负责将从索引服务器430返回的应答418组合成然后将返回到前端服务器326并最终返回到终端用户计算设备311的应答334。

文档索引328的每一个索引碎片(例如，328A、328B、328C...328N)可以存储在对应的索引服务器(例如430A、430B、430C...430N)处。索引服务器(430B)处的索引碎片(例如，328B)可以对分配给该索引碎片的一个或多个文档命名空间中的文档340进行索引。

在操作中，前端服务器326A从终端用户计算设备(例如，311A)接收搜索查询332A并将对其的个性化应答334A返回给终端用户计算设备。在某种意义上，应答334A可以被个性化为在应答334中识别出的与查询332A相关的文档340仅限于属于用户被授权访问的文档命名空间的文档340。如果查询332A是完成查询，那么在某种意义上，应答334A也可以被个性化为包括在应答334中的对于完成查询的可能的完成可以仅由属于用户被授权访问的文档命名空间的索引文档340的文档索引328中的索引令牌组成。用户可以被认证以便于对应答334A的个性化。

因此，可以在为认证用户建立的认证会话的上下文中在前端搜索326A处接收查询332A。例如，认证用户可以是向前端服务器326A发送查询332A的终端用户计算设备的用户。可以在前端服务器326A接收查询332A之前已经认证了认证用户。例如，可以响应于从终端用户计算设备接收到包含认证凭证(例如，用户名/口令对)的认证网络请求而已经认证了认证用户。响应于接收到认证网络请求，网络请求中的密码可以与给定用户名的已知密码进行比较。如果密码匹配，那么建立认证会话。否则，如果密码不匹配，那么不建立认证会话。

可以使用除了用户名/密码对之外的认证凭证来认证用户。例如，在一些情况中，可以根据多因素认证技术来认证用户。例如，在用户知道的事情(例如，用户名/口令对)之外，可以基于用户他或她拥有物(例如，FOB或移动电话)中的一些东西和/或基于用户具有的一些东西(例如，生物测量)来认证用户。在一些情况中，可以根据不要求用户提供密码的认证协议来认证用户。适于这种目的的一些示例认证协议包括开放授权(OpenAuthorization，OAuth)、OpenId和安全性断言标记语言(Security Assertion MarkupLanguage，SAML)认证协议。

虽然在一些情况中，在前端服务器326A接收到查询332A之前认证用户，但是在其它实施例中，响应于接收到查询332A认证用户。例如，包含查询332A的网络请求也可以包含用于认证用户的认证凭证，或者可以以其它方式响应于接收到包含查询332A的网络请求认证用户。

在用户被认证之后，可以以会话标识符令牌的形式为用户建立认证会话。特别地，可以响应于成功认证用户创建会话标识符令牌。在创建之后，会话标识符令牌可以在网络请求和网络响应中(包括在包含查询332A的网络请求中和在包含应答334A的网络响应中)在用户的终端用户计算设备和前端服务器326A之间发送(例如，在“cookie”中)。会话标识符令牌直接或间接地(例如，通过关联数组)识别用户对其成功认证的用户帐户(例如，通过用户名唯一识别的帐户)。为了额外的安全性，会话标识符令牌可以被密码学地加密。

有时(例如，响应于接收查询332A)或在一段时间上(例如，从用户被认证时直到应答334A返回到用户的终端用户计算设备)，认证会话数据411可以存储在前端服务器326A的易失性或非易失性存储器中。认证会话数据411可以包括关于认证用户的信息，诸如，认证用户的用户名、用户标识符或其它用户帐户标识符以及相关联的特权、许可和/或授权。

服务系统325能够将对查询332A的应答334A限制为仅识别满足查询332A并且属于授权用户被授权访问的文档命名空间的在文档索引328中被索引的文档340。服务系统325能够进行这种限制，即使文档索引328可以对满足查询332A但是属于授权用户未被授权访问的文档命名空间的文档340进行索引。

为了限制对查询332A的应答334A，前端服务器326A可以向访问控制服务器410A发送网络请求412，请求认证用户被允许访问的(一个或多个)文档命名空间的(一个或多个)标识符。为了便于由访问控制服务器410A进行这种确定，网络请求412可以包含认证用户的指示或标识符。例如，指示或标识符可以是用户名、会话标识符令牌、用户帐户标识符、或唯一地识别用户和/或用户对其成功认证的用户帐户的其它信息。

响应于接收网络请求412，访问控制服务器410A可以将在请求412中提供的认证用户的指示或标识符用作查找操作中的关键字在用户帐户数据库(图4中未示出)中查找认证用户被允许访问的(一个或多个)文档命名空间的(一个或多个)标识符。

前端服务器326A可以在各种不同时间向访问控制服务器410A发送网络请求412。例如，前端服务器426A可以响应于接收查询332A发送网络请求412。作为另一个示例，前端服务器426A可以在成功认证用户之后发送网络请求412。

响应于接收网络请求412，访问控制服务器410A返回包括认证用户被允许访问的(一个或多个)授权文档命名空间的(一个或多个)标识符的网络响应413。每一个授权文档命名空间标识符唯一地识别根据对文档命名空间的明确和/或隐含访问控制授权用户在一些访问级别被允许访问的文档命名空间。例如，授权文档命名空间标识符可以识别认证用户对属于该文档命名空间的文档340至少具有读取访问的文档命名空间。为了处理后续网络请求中的效率，前端服务器326A可以将(一个或多个)授权文档命名空间标识符存储(高速缓存)成为认证用户维护的认证会话数据411的一部分。在这种情况中，前端服务器326A可以不需要响应于接收查询332A而向访问控制服务器410A发送网络请求412。

包括来自用户的终端用户计算设备的查询332A的网络请求还可以指定用户希望搜索的(一个或多个)文档命名空间的(一个或多个)标识符。在这种情况中，可以计算用户希望搜索的(一个或多个)文档命名空间的(一个或多个)标识符集合与用户被允许访问的(一个或多个)授权文档命名空间的(一个或多个)标识符集合的交集，以确定要搜索的(一个或多个)授权文档命名空间的(一个或多个)标识符。这种交集可以由前端服务器326A执行。可替代地，这种交集可以由访问控制服务器410A执行。在这种情况中，前端服务器326A可以在网络请求412中包括用户希望搜索的(一个或多个)文档命名空间的(一个或多个)标识符，并且对网络请求412的网络响应413可以包括如由访问控制服务器410A计算的交集的结果。

如果包括查询332A的网络请求没有指定要搜索的任何请求的文档命名空间，那么可以选择要搜索的(一个或多个)授权文档命名空间的(一个或多个)标识符的默认集合。可以由前端服务器326A视具体情况从在响应413中返回的或者作为认证会话数据411的一部分被高速缓存的(一个或多个)授权文档命名空间的(一个或多个)标识符来执行默认集合的选择。可替代地，访问控制服务器410A可以从用户被允许访问的所有文档命名空间集合中选择默认集合。在任一情况下，默认集合可以识别a)用户被允许访问的所有文档命名空间(例如，与认证用户的帐户相关联的所有文档命名空间)，或者b)其子集。

在已经确定要搜索的(一个或多个)授权文档命名空间的(一个或多个)标识符之后，包括查询332A和要搜索的(一个或多个)授权文档命名空间的(一个或多个)标识符的网络请求可以从前端服务器326A发送到路由服务器420A，用于由查询处理器327进一步处理查询332A。

响应于从前端服务器326A接收包括查询332A和要搜索的(一个或多个)授权文档命名空间的(一个或多个)标识符的网络请求，路由服务器420A处的查询处理器327确定将查询332A路由到其的一个或多个索引服务器430。可以基于路由服务器420A向要搜索的(一个或多个)授权文档命名空间的(一个或多个)标识符中的每一个应用确定性映射函数416的结果做出这种确定。给定文档命名空间的标识符，路由服务器(例如，420A)可以使用确定性映射函数416和索引服务器映射417以确定存储对给定文档命名空间中的文档进行索引的索引碎片(例如，328B)的索引服务器(例如，430B)。

根据本发明的一些实施例，确定性映射函数416向文档命名空间标识符应用单向散列函数、简单散列函数、一致性散列函数等进行搜索，以便确定文档命名空间被分配到的索引碎片(例如，328B)。为了做出这种确定，路由服务器420A处的查询处理器327可以具有对索引服务器映射417的访问。确定性映射函数416和索引服务器映射417一起为路由服务器420A处的查询处理器327提供确定在其存储包含给定文档命名空间的索引的索引碎片(例如，328B)的索引服务器(例如，430B)的主机名或网络地址的方法。

在本发明的一些实施例中，确定性映射函数416可以包括散列机制和模运算机制。散列机制可以接受文档命名空间标识符作为输入(例如，表示文档命名空间标识符的字符串数据)，并且可以产生散列值hv作为输出。例如，散列机制可以包括MD4、MD5、SHA-1或SHA2消息摘要算法，当其应用到作为输入提供的文档命名空间标识符时，产生散列值(例如，32位散列值)作为输出。模运算机制可以计算散列值hv除以模数k的余数r，从而将输入文档命名空间标识符映射到0至k-1范围内的k个值中的一个。可以基于各种不同的因素(包括，例如，实际、预计或期望的索引服务器430的数量、由文档索引328进行索引的实际、预计或期望的文档命名空间的数量、和/或实际、预计或期望的文档命名空间组的数量)选择模数k的值。在一种示例性实施例中，值k是2的幂并且至少等于1024。

在本发明的一些实施例中，索引服务器映射417包括用于每一个索引服务器430的条目。每一个这种条目由在范围0至k-1中的一个或多个不重叠的子范围作为关键字。例如，映射417中的第一条目E1可以具有包括限定0至k-1范围中的连续值的第一范围的值K1和K2的关键字，并且映射417中的第二条目E2可以具有包括限定范围0至k-1中的连续值的第二范围的值K3和K4，其中第一范围K1至K2与第二范围K3至K4不重叠。

当路由服务器420A处的查询处理器327将确定性映射函数416应用到给定文档命名空间标识符时，可以产生在0至k-1范围中的值r。路由服务器420A处的查询处理器327然后可以使用值r咨询索引服务器映射417，以识别r在其条目关键字的范围内的条目。这个条目的主机名或网络地址可以识别在其存储将属于给定文档命名空间的索引文档340进行索引的索引碎片(例如，328B)的索引服务器(例如，430B)。

在本发明的一些实施例中，分配给索引碎片(例如，328B)的文档命名空间被分组成较少数量的索引碎片的文档命名空间组，以便减少存储在在其存储索引碎片的索引服务器(例如，430B)处的索引文件的数量。换句话说，在索引碎片(例如，328B)内，分配给该索引碎片的文档命名空间可以被分区到文档命名空间组中。每一个这样的文档命名空间组可以包括若干文档命名空间。

例如，分配给索引碎片(例如，328B)的两百万(2,000,000)个文档命名空间中的每一个可以被分区到索引碎片的八十(80)个文档命名空间组中的一个中。为了效率，在其存储索引碎片(例如，328B)的索引服务器(例如，430B)可以为八十(80)个文档命名空间组中的每一个存储一个或多个索引文件，而不是为两百万(2,000,000)个文档命名空间中的每一个存储一个或多个索引文件。在这种情况中，当应用到给定文档命名空间标识符时由散列机制输出的散列值hv可以用作给定文档命名空间所属的文档命名空间组的标识符。

在一些实施例中，文档命名空间组不用于进一步对索引碎片(例如，328B)分区。在这些实施例中，散列值hv除以模数k的余数r可以用作给定文档命名空间所分配到的索引碎片的标识符。同样，在这些实施例中，在其存储索引碎片的索引服务器可以为分配到索引碎片的所有文档命名空间存储一个或多个索引文件。例如，索引服务器可以为分配给索引碎片的所有文档命名空间存储单个索引文件。

虽然在图4中索引服务器映射417被示为与路由服务器420A处的确定性映射函数416和查询处理器327分开，但是索引服务器映射417可以是在路由服务器420A处的确定性映射函数416的组件或查询处理器327的组件。此外，每一个路由服务器420可以访问索引服务器映射417。在这种情况中，索引服务器映射417的拷贝可以存储(高速缓存)在每一个路由服务器420处用于高效访问。附加地或可替代地，可以作为网络服务使索引服务器映射417对路由服务器420可用。服务系统325可以包括以水平方式扩展的若干路由服务器420，用于负载平衡、增加容量、增加吞吐量、减少延迟、故障转移和/或冗余的目的。

在示例性实施例中，文档索引328对超过四亿(400,000,000)个文档命名空间中的文档340进行索引，并且确定性映射函数416和索引服务器映射417将超过4亿个文档命名空间中的每一个分配(映射)到大约两百(200)个索引碎片(例如，328A、328B、328C...328N)中的一个。在这种示例性实施例中，每一个索引碎片(例如，328A)对大约两百万(2,000,000)个文档命名空间中的文档340进行索引。

在一些情况中，索引服务器(例如，430C)实际上包括以水平方式分布的多个服务器，以为索引碎片(例如，328C)提供负载平衡、故障转移或冗余。在这种情况中，若干索引服务器中的每一个可以存储索引碎片(例如，328C)的副本或拷贝。

在一些情况中，索引服务器(例如，430A)包括若干服务器，其中若干服务器中的每一个存储索引碎片(例如，328A)的一部分。在这种情况中，可能有若干级别的路由服务器。第一路由级别由路由服务器420A作为示例，其将从前端服务器326A接收到的查询332A路由到索引服务器430中的一个或多个。可以存在第二级别的路由服务器以进一步在索引服务器(例如，430C)内将查询路由到索引服务器的若干服务器中的一个或多个。在这种情况中，第二级路由服务器还可以具有确定性映射函数和类似确定性映射函数416以及索引服务器映射417的映射，用于基于文档命名空间的标识符进一步路由查询。

在图4的示例中，查询332A由路由服务器420A根据确定性映射函数416和索引服务器映射417路由到索引服务器430B和430C。但是，取决于用查询332A要搜索的授权文档命名空间的数量，查询332A可以仅仅被简单地路由到仅单个索引服务器430或路由到多于两个的索引服务器430。例如，如果仅有一个授权文档命名空间要搜索，或者如果要搜索的所有授权文档命名空间都被分配到同一索引碎片(例如，328B)，那么查询332A可以由路由服务器420A路由到仅仅一个索引服务器(例如430B)。

当将查询332A路由到索引服务器(例如，430B)时，路由服务器420A可以向索引服务器发送包括查询332A的网络请求。此外，网络请求可以包括分配到存储在那个索引服务器处的索引碎片(例如，328B)的要搜索的(一个或多个)授权文档命名空间的(一个或多个)标识符。此外，每一个这种授权文档命名空间标识符可以在网络请求中与该文档命名空间所属的文档命名空间组的标识符相关联。

在本发明的一些实施例中，当确定对查询332A的应答(例如，418A)时，索引服务器(例如，430B)处的查询处理器327使用从路由服务器420A接收到的网络请求中的文档命名空间组的标识符限制被访问的索引碎片(例如，328B)的部分。例如，基于网络请求中的文档命名空间组标识符，索引服务器处的查询处理器327可以只访问在索引服务器处的非易失性存储器中存储的某(一个或多个)索引数据库文件351，或者只访问在索引服务器的易失性存储器中存储的某些数据结构。

作为示例，假设从前端服务器326A发送到路由服务器420A的包括查询332A的网络请求指定两个授权文档命名空间要使用对应的文档命名空间标识符“abcd”和“defg”进行搜索。进一步假设根据确定性映射函数416和索引服务器映射417，授权文档命名空间“abcd”属于文档命名空间组“1234”并被分配给索引碎片328B，并且授权文档命名空间“defg”属于文档命名空间组“5678”并被分配给索引碎片328C。在这种情况中，从路由服务器420A到索引服务器430B的网络请求可以指定文档命名空间组“1234”中的文档命名空间“abcd”是要被搜索的，并且从路由服务器420A到索引服务器430C的网络请求可以指定文档命名空间组“5678”中的文档命名空间“defg”是要被搜索的。当制定对查询332A的应答418A时，索引服务器430B可以使用发送到索引服务器430B的网络请求中的文档命名空间组标识符“1234”限制被索引服务器430B处的查询处理器327访问的索引碎片328B的部分。类似地，当制定对查询332A的应答418B时，索引服务器430C可以使用发送到索引服务器430C的网络请求中的文档命名空间组标识符“5678”限制被索引服务器430C处的查询处理器327访问的索引碎片328C的部分。这种限制可以包括例如只访问存储在索引服务器的非易失性存储器中的一个或多个索引数据库文件351和/或与指定的文档命名空间组标识符相关联的索引服务器的易失性存储器中的数据。

路由服务器420A可以将查询332A路由到若干索引服务器(例如，430B、430C)，使得每一个索引服务器430处的查询处理器327可以并行地处理查询。例如，在与路由服务器420A向索引服务器430C发送包括查询332A的网络请求相同或大致相同的时间，路由服务器420A可以向索引服务器430B发送包括查询332A网络请求。在这种情况中，在与索引服务器430C处的查询处理器327针对索引碎片328C处理查询332A相同或大致相同的时间，索引服务器430B处的查询处理器327可以针对索引碎片328B处理查询332A。

当在索引服务器(例如，430B)处接收到查询332A时，索引服务器处的查询处理器327可以咨询(访问)存储在索引服务器处的索引碎片(例如，328B)，以确定满足查询的文档340。在这样做时，索引服务器处的查询处理器327可以将可能在对查询的应答(例如，418A)中识别出的文档340限制成仅属于要搜索的授权文档命名空间的文档340。为了做这个限制，索引服务器处的查询处理器327可以使用伴随来自路由服务器420A的网络请求中的查询332A的(一个或多个)授权文档命名空间标识符。此外，在索引碎片中进行索引的文档340的文档标识符可以与索引文档340所属的文档命名空间的文档命名空间标识符相关联。这些关联有助于查询处理器327将可以在对查询的应答中识别出的文档340限制成1)满足查询332A和2)与作为要被搜索的授权文档命名空间标识符之一的文档命名空间标识符相关联的那些文档。即使索引文档340可以以其它方式满足查询，但是如果文档340不属于要搜索的授权文档命名空间之一，那么索引服务器处的查询处理器327也不可以在对查询332的应答418A中识别文档340。

来自索引服务器(例如，430B)的返回到路由服务器(例如，420A)的应答(例如，418A)可以识别满足查询332A的一个或多个授权文档命名空间中的一个或多个文档340。文档可以根据由索引服务器处的查询处理器327采用的排名函数进行排名。排名函数可以基于为索引的文档计算出的查询相关的度量和/或查询无关的度量。

来自索引服务器(例如，430B)的对查询332A的应答(例如，418A)可以包括由排名函数生成的每一个识别出的文档的排名分数。查询处理器327可以在所有索引服务器(例如，430A、430B、430C...430N)处采用相同的排名函数，使得在不同索引服务器处为相同查询生成的排名分数是可比较的。在所有索引服务器处使用相同的排名函数还允许路由服务器420A处的查询处理器327将从索引服务器430B和430C返回的对查询332A的若干应答418A和418B中标识出的文档340组合成返回到前端服务器326A并且最终返回到由前端服务器326A从其接收查询332A的终端用户计算设备311A的单个应答334A。

根据本发明的一些实施例，前端服务器326A可以向获得的搜索查询332A应用常规的拼写校正算法和/或常规的语音校正算法(例如，soundex算法)。拼写校正算法可以应用不同形式的拼写校正。例如，拼写校正算法可以应用常规的孤立项校正算法(isolated-term correction algorithm)(例如，编辑距离和/或k-gram重叠)和/或常规的上下文敏感校正算法。因此，转发到路由服务器420A并路由到索引服务器430的查询332A可以反映由前端服务器326A对查询332A的令牌执行的拼写校正和/或语音校正的结果。

索引碎片

现在转到图5，它是根据本发明的一些实施例的文档索引328的索引碎片(例如，328B)的框图。根据本发明的一些实施例，索引碎片可以被构造为包括字典510和对应的帖子520的反向索引。

字典510可以包括索引令牌(例如，TOKEN 1、TOKEN 2、TOKEN 3...TOKEN N)，在帖子520中标识出的文档340通过其进行索引。字典510还包括用于每一个索引令牌(例如，TOKEN 1)的指向一个或多个文档标识符(例如，DOC ID 1)的帖子列表(例如，POSTINGSLIST 2)的指针，所述标识符识别该索引令牌通过其进行索引(例如，在其中出现)的文档340。

字典510还可以包括除索引令牌之外的信息，诸如例如，令牌属性信息，诸如例如，令牌频率信息或可以由查询处理器327的排名函数使用以用查询相关和/或查询无关的方式排名或者其它方式确定文档与查询的相关性的其它信息。

帖子520的帖子列表(例如，POSTINGS LIST 2)可以包括除文档标识符之外的信息，诸如例如，文档-令牌属性信息，诸如例如，在特定文档340内令牌的令牌频率、在特定文档340内令牌的一个或多个位置、或者可以由查询处理器327的排名函数使用以用查询相关和/或查询无关的方式排名或者其它方式确定文档340与查询的相关性的其它信息。

帖子520中的文档标识符(例如，DOC ID 1、DOC ID 2、DOC ID 3...DOC ID N)可以与文档命名空间标识符相关联，以指示标识出的文档340所属的文档命名空间。这种关联还允许索引服务器(例如，430B)处的查询处理器327将对查询(例如，332)的应答(例如，417A)限制为仅识别属于要搜索的授权文档命名空间的文档340。

例如，帖子列表(例如，POSTINGS LIST 2)中的元素可以用识别文档340所属的文档命名空间的文档命名空间标识符作为前缀。例如，帖子列表(例如POSTINGS LIST 2)中的元素可以是<document namespace identifier>:<document identifier>格式中的字符串数据，其中<document namespace identifier>是识别文档命名空间的字符串数据字段并且<document identifier>是识别属于文档命名空间的文档340的字符串数据字段。冒号“:”字符可用作分隔符以分隔帖子列表元素内的字符串数据字段。其它分隔符也是可能的。例如，在字符串数据字段具有固定长度的情况下，也可能不使用分隔符。用于文档标识符的其它格式是可能的并且本发明不限于任何特定前缀格式。

代替使用文档命名空间标识符作为帖子列表中的文档标识符前缀以将文档340与其所属的文档命名空间相关联，索引碎片可以包括将给定文档标识符映射到文档340所属的文档命名空间的标识符的多对一(many-to-one)映射。该映射是多对一的，因为文档命名空间可以包含若干文档340。

在本发明的一些实施例中，为了空间效率和减少帖子520的尺寸，帖子列表(例如，POSTINGS LIST 2)中的文档命名空间标识符或文档标识符包括对于索引碎片(例如，索引碎片328B)是本地的并且代替尺寸较大(例如，就字节数而言)的全局文档命名空间标识符或全局文档标识符的本地标识符。本地标识符可以在尺寸上(例如，就字节数而言)小于本地标识符所代替的全局文档命名空间标识符或全局文档标识符。

索引碎片(例如，328B)可以包括将给定本地标识符映射到全局文档标识符的一对一(one-to-one)映射。可替代地，可以存在两个一对一映射，其中一个用于将本地文档命名空间标识符转换成全局文档命名空间标识符，并且另一个映射用于将本地文档标识符转换成全局文档标识符。作为再另一替代，可以存在用于将给定本地文档命名空间标识符转换成文档340所属的文档命名空间的全局文档标识符和全局文档命名空间标识符的一对一映射。

在这描述中，除非在上下文中其它方式清楚地出现，否则文档340的“文档标识符”是指直接或间接(例如，通过关联数组)唯一地识别文档340的文档标识符的所有可能形式，包括文档340的本地文档标识符和文档340的全局文档标识符。

类似地，在这种描述中，除非在上下文中其它方式清楚地出现，否则文档命名空间的“文档命名空间标识符”是指直接或间接地(例如，通过关联数组)唯一地识别文档命名空间的文档命名空间标识符的所有可能形式，包括文档命名空间的本地文档命名空间标识符和文档命名空间的全局文档命名空间标识符。

根据本发明的一些实施例，当在索引服务器(例如，430B)处接收到查询(例如，332)时，索引服务器处的查询处理器327使用查询中的查询令牌作为到字典510中的关键字来识别对应帖子520中的帖子列表。如果在查询中存在若干查询令牌，那么可以取决于这些查询令牌一起如何作为布尔表达式相关在一起而适当地合并对应的帖子列表。

在本发明的一些实施例中，索引服务器处的查询处理器327将可以包括在对查询的应答(例如，417A)中的、在对应帖子列表中识别出的文档340限制到仅属于要搜索的授权文档命名空间的那些文档340。索引服务器处的查询处理器327在本发明的一些实施例中通过将与对应帖子列表中的文档标识符相关联的文档命名空间标识符与和查询相关联的授权文档命名空间标识符(例如，包括在包括来自路由服务器(例如，420A)的查询的网络请求中)进行比较来这样做。如果与以其它方式满足查询的文档340的文档标识符相关联的文档命名空间标识符匹配与查询相关联的授权文档命名空间标识符，那么文档340可以被包括在对查询的应答中。但是，如果与文档标识符相关联的文档命名空间标识符不匹配与查询相关联的授权文档命名空间标识符，那么即使该文档以其它方式满足查询，文档340也不被包括在对查询的应答中。以这种方式，索引服务器430处的查询处理器327可以将对查询的应答限制到仅属于与要搜索的查询相关联的授权文档命名空间的文档340。

在本发明的一些实施例中，索引碎片存储若干字典510/帖子520对。例如，索引碎片可以为分配给索引碎片的若干文档命名空间中的每一个或为分配给索引碎片的若干文档命名空间组中的每一个存储字典510和对应的帖子520。

在本发明的一些实施例中，索引碎片(例如，328B)可以根据分配给该索引碎片的文档命名空间组的标识符被组织成索引数据库文件351和易失性存储器数据结构的单独可识别的集合。在这种情况中，对于分配给索引碎片的每一个文档命名空间组，可以存在单独的字典510或单独的字典510和对应的帖子520。当在索引服务器(例如，430B)处接收到查询(例如，332)时，索引服务器处的查询处理器327可以使用与来自路由服务器的网络请求中的授权文档命名空间标识符相关联的文档命名空间组标识符来确定要访问哪个字典510或哪些字典510和对应的帖子520。

在本发明的一些实施例中，索引碎片(例如，328B)可以根据分配给索引碎片的文档命名空间的标识符被组织成索引数据库文件和易失性存储器数据结构的单独可识别的集合。在这种情况中，对于分配给索引碎片的每一个文档命名空间，可以存在单独的字典510或单独的字典510和对应的帖子520。当在索引服务器(例如，430B)处接收到查询(例如，332)时，索引服务器处的查询处理器327可以使用来自路由服务器的网络请求中的文档命名空间标识符来确定要访问哪个字典510或哪些字典510和帖子520。

在本发明的一些实施例中，索引碎片存储用于处理不同类型的查询的单独的字典510/帖子520对。例如，对于关联到索引碎片的给定文档命名空间或给定文档命名空间组，索引碎片可以存储用于处理非完成查询的第一字典510/帖子520对，以及用于处理完成查询的第二字典510/帖子520对。存储单独的字典510/帖子520对允许字典510和对应的帖子520的结构和内容定制用于处理某种类型的查询。例如，用于处理完成查询的字典510可以仅包括用于文档的文件名的索引令牌，而不是用于文档的全文的索引令牌，以在当存储在非易失性存储器(例如，闪存)上或易失性存储器(例如，RAM)中时消耗的字节的方面减少字典的尺寸，从而允许查询处理器327更快地处理完成查询。

为了更高效的访问，在索引服务器(例如，430C)处的查询处理器327可以将字典510(或其一部分)从非易失性存储设备(例如，闪存)加载到易失性存储器(例如，RAM)中。为了更高效的访问，可以将帖子列表(例如，POSTINGS LIST 2)存储在索引服务器(例如，430C)的非易失性存储器(例如，闪存)中和/或高速缓存在索引服务器的易失性存储器中。可以根据高速缓存逐出策略(诸如例如，最近最少访问策略)从索引服务器的易失性存储器中逐出高速缓存的帖子列表。索引服务器(例如，430B)处的查询处理器327还可以在易失性存储器中高速缓存作为对从帖子520检索到的若干帖子列表执行的合并算法的结果而生成的帖子列表。通过这样做，索引服务器处的查询处理器327可以避免必须在以后的时间对若干帖子列表执行合并算法。

继续参考图5，根据本发明的一些实施例，为了便于完成查询的处理，字典510中的索引令牌可以由文档命名空间标识符作为前缀，并且可以以前缀索引令牌(prefixedindex token)的词典编纂顺序在字典内排序前缀索引令牌。以这种方式构造的字典510在本文被称为“完成”字典。

在本发明的一些实施例中，与前缀索引令牌相关联的帖子列表可以包括属于在前缀索引令牌中识别出的文档命名空间的文档340的文档标识符。因此，索引令牌可以在完成字典中出现多于一次，如果完成字典包括用于多于一个文档命名空间的前缀索引令牌，那么对于若干文档命名空间中的每一个，索引令牌在完成字典中出现一次。

例如，完成字典中的前缀索引令牌可以具有以下形式：<document namespaceidentifier>:<index token>，其中<document namespace identifier>是识别文档命名空间的字符串数据字段，并且<index token>是包括索引令牌的字符的字符串数据字段。冒号“:”字符或其它字符可以用作分隔符以分隔前缀索引令牌内的字符串数据字段。前缀索引令牌的示例是[abcd:private](没有包围的括号)，其中“abcd”是文档命名空间的标识符并且“private”是索引令牌。

通过根据前缀索引令牌的词典编纂排序在完成字典内排序前缀索引令牌，索引服务器(例如430B)处的查询处理器327可以更高效地识别对完成查询的完成令牌的可能的完成。特别地，作为前缀索引令牌的词典编纂排序的结果，当完成字典存储在非易失性存储器或易失性存储器中时，属于同一文档命名空间并且共享与完成令牌匹配的前缀的完成字典中的索引令牌可以彼此靠近地存储(聚集)(例如，在连续或邻近的存储器位置中)。当查询处理器访问完成字典以确定对完成令牌的可能的完成时，这种聚类有助于顺序的存储器访问，并且还在访问完成字典时减少或消除了随机存储器访问。

例如，用于文档命名空间“abcd”的索引令牌“concession”、“conclude”、“conclusion”、“concrete”和“concurrent”可以在存储器中彼此靠近地分别存储为前缀索引令牌“abcd:concession”、“abcd:conclude”、“abcd:conclusion”、“abcd:concrete”和“abcd:concurrent”。当处理具有例如完成令牌“con”的完成查询并且具有例如“abcd”的标识符的特定文档命名空间是要搜索的授权文档命名空间时，查询处理器可以生成用于访问完成字典的索引关键字“abcd:con”。由于作为词典编纂排序的结果，前缀索引令牌在存储器中彼此靠近地存储，因此，查询处理器可以比如果前缀索引令牌在存储器中没有彼此靠近地存储更高效地识别索引令牌“concession”，“conclude”，“conclusion”，“concrete”和“concurrent”作为文档命名空间“abcd”中的完成令牌“con”的可能的完成。

在作为前缀索引令牌的词典编纂排序的结果在存储器中彼此靠近地存储的完成字典的前缀索引令牌之外，指向对应帖子列表的存储位置的与排序的前缀索引令牌相关联的完成字典的指针(例如，地址)也可以作为前缀索引令牌的词典编纂排序的结果彼此靠近地存储在存储器中。特别地，指向前缀索引令牌的帖子列表的存储位置的指针可以存储在存储器中靠近前缀索引令牌。例如，指针和前缀索引令牌可以存储在相同存储器块或连续或相邻存储器块的相同集合中。因此，查询处理器不仅可以例如更高效地将索引令牌“concession”，“conclude”，“conclusion”，“concrete”和“concurrent”识别为文档命名空间“abcd”中完成令牌“con”的可能的完成，而且查询处理器还可以更高效地识别作为词典编纂排序的结果与那些索引令牌对应的帖子列表的存储位置。

在本发明的一些实施例中，以前缀索引令牌的词典编纂顺序对完成字典的前缀索引令牌进行排序包括对完成字典的多个记录(数据结构)进行排序，其中每一个这种记录包括前缀索引令牌和相关联的指向在其存储前缀索引令牌的帖子列表的易失性或非易失性存储器位置的指针(例如，地址)。可以根据其前缀索引令牌的词典编纂次序排序多个记录。然后，排序的记录可以存储在计算机存储器(例如，易失性存储器或非易失性存储器)的连续或相邻块中。

下面的描述给出了可以使用计算机可执行指令实现的、用于在处理器控制下引导一个或多个计算设备的操作的方法步骤。计算机可执行的指令可以存储在计算机可读介质(诸如，CD、DVD、闪存等)上。计算机可执行的指令还可以存储为一组可下载的计算机可执行指令，例如，用于从互联网位置(例如，Web服务器)下载和安装。

虽然图和下面的描述可能暗示了方法步骤的特定顺序，但是应当理解的是，除非上下文其他方式清楚地指示，否则方法步骤可以以与所示和/或所描述的顺序不同的顺序来执行。此外，除非上下文其他方式清楚地指示，否则方法步骤可以彼此并行(并发地)执行。

个人搜索的过程

图6是图示根据本发明的一些实施例的用于由多用户搜索系统320的服务系统325执行的个人搜索的过程600的流程图。

在步骤602，如本文所述，前端服务器326A从认证用户的终端用户计算设备311A获得搜索查询332A。搜索查询332A可以是完成查询或非完成查询。

在步骤604，如本文所述，前端服务器326A确定要搜索的一个或多个授权文档命名空间的一个或多个标识符。如本文所述，前端服务器326A然后将查询332A和要搜索的一个或多个授权文档命名空间的一个或多个标识符转发到路由服务器420A。

在步骤606，如本文所述，路由服务器420A确定查询332A应当被路由到的一个或多个索引服务器430。在本发明的一些实施例中由路由服务器420A执行的用于确定把查询323A路由到哪个(哪些)索引服务器430的过程可以如本文以及下面参考图7所述的那样。

在步骤608，如本文所述，路由服务器420A将查询332A路由到在步骤606确定的一个或多个索引服务器430中的每一个，以路由查询332A。

在步骤610，如本文所述，由在步骤608查询332A路由到的每一个索引服务器430处的查询处理器327处理查询332A。如所提到的，查询332A可以是完成查询或非完成查询。当查询332A是非完成查询时，在本发明的一些实施例中由索引服务器(例如，430B)处的查询处理器327执行的、用于生成对查询332A的个性化应答(例如，418A)的过程可以如本文以及下面参考图8所述的那样。当查询332A是完成查询时，在本发明的一些实施例中由索引服务器(例如，430B)处的查询处理器327执行的、用于生成对查询332A的个性化应答(例如，418A)的过程可以如本文以及下面参考图9所述的那样。

在步骤612，如本文所述，路由服务器420A从在步骤608查询332A路由到的每一个索引服务器430接收对查询332A的个性化应答(例如，418A)。如果查询332A在步骤608路由到若干索引服务器430，那么在步骤612，路由服务器420A可以接收到若干对应的个性化应答418。

如本文所述，如果路由服务器420A在步骤612接收到若干个性化应答418，那么在步骤614路由服务器420A可以将若干个性化应答组合成然后返回到前端服务器326A的单个个性化应答334A。

在步骤616，如本文所述，前端服务器326A将对查询332的个性化应答334A返回到从其接收到查询332A的终端用户计算设备311A。

确定性查询路由

图7是图示根据本发明的一些实施例的由路由服务器420A执行的用于确定存储对属于给定文档命名空间的文档340进行索引的索引碎片(例如，328B)的索引服务器(例如，430B)的过程700的流程图。

在步骤702，如本文所述，路由服务器420A获得要搜索的每一个授权文档命名空间的标识符。例如，路由服务器420A可以获得从前端服务器326A接收到的还包括查询332A的网络请求中的(一个或多个)标识符。

在步骤704，如本文所述，路由服务器420A的确定性映射函数416将散列算法(例如，消息摘要算法)应用到每一个授权文档命名空间标识符，以为每一个授权文档命名空间标识符生成散列值hv。可以使用任何数量的不同散列算法。但是，所使用的散列算法应当是确定性的，在某种意义上，对于给定的授权文档命名空间标识符，散列算法始终输出相同的散列值。可以在步骤704使用的一些合适的散列算法的非限制性示例包括MD4、MD5、SHA-1和SHA2消息摘要算法。

在步骤706，如本文所述，对于要搜索的每一个授权文档命名空间，路由服务器420A的确定性映射函数416计算在步骤704为授权文档命名空间计算出的散列值hv除以模数k的余数r。

在步骤708，如本文所述，对于要搜索的每一个授权文档命名空间，路由服务器420A的确定性映射函数416在映射417中识别其中在步骤706为授权文档命名空间计算出的余数r在条目关键字的范围之内的映射条目。如所提到的，映射417中的条目可以包括关键字和值。条目的关键字可以定义范围0至k-1中的连续值的子范围。条目的值可以包括索引服务器(例如，430B)的主机名和/或网络地址。例如，条目的值可以包括索引服务器的主机名或网络地址，路由服务器420A通过其可以向索引服务器生成和发送包括查询332A以及其它各种其它信息的网络请求。

在步骤710，对于在步骤708识别出的每一个索引服务器，路由服务器420A将查询332A路由到索引服务器，如本文所述。

处理非完成查询

图8是图示根据本发明的一些实施例的由索引服务器(例如，430B)处的查询处理器327执行的用于在查询332A是非完成查询时生成对查询332A的个性化应答(例如，418A)的过程800的流程图。可以在网络请求中从路由服务器(例如，420A)接收查询332A。网络请求还可以包括要搜索的一个或多个授权文档命名空间的一个或多个标识符。此外，每一个这种授权文档命名空间标识符可以在网络请求中与该文档命名空间所属的文档命名空间组的标识符相关联。

在步骤802，索引服务器处的查询处理器327确定要访问的索引服务器处的索引碎片(例如，320B)的一个或多个索引。每一个这种索引可以包括存储在索引服务器的非易失性存储器(例如，闪存)中的索引数据库文件351中的字典(例如510)和对应的帖子(例如，520)。每一个这种索引还可以具有易失性存储器组件。例如，索引的字典可以存储在索引服务器的易失性存储器中。此外，来自索引的帖子的各种帖子列表可以有时高速缓存在索引服务器的易失性存储器中。查询处理器327可以根据高速缓存逐出策略(例如，LRU)从易失性存储器中逐出高速缓存的帖子列表。

根据一些实施例，索引的索引数据库文件351被视为不可变的，并且对索引的更新存储在索引服务器的易失性存储器中。更新可以包括在索引中将由其索引文档340的新索引令牌，以及在索引中将不再由其索引文档340的索引令牌。更具体而言，在索引服务器处的易失性存储器中存储的索引中的索引令牌的“增量”帖子列表可以反映对存储在索引的索引数据库文件351中的索引令牌的“基本”帖子列表的更新。

例如，假设索引服务器(例如，430A)处的索引的索引数据库文件351通过令牌“solved”、“two”和“problems”索引文档D2。在这种情况中，索引数据库文件351可以包括三个基本帖子列表，每一个索引令牌“solved”、“two”和“problems”一个基本帖子列表。接下来，假设文档D2被编辑以将“solved two problems”替换为“solved three problems”。接下来，假设索引服务器接收到一个或多个索引变化352，其指定文档D2不再通过索引令牌“two”进行索引而是现在将通过索引令牌“three”进行索引。为了表示这些变化352，用于索引令牌“two”的增量帖子列表可以存储在索引服务器的易失性存储器中以表示(例如，使用删除位向量)文档D2不再通过索引令牌“two”进行索引并且用于索引令牌“three”的另一增量帖子列表可以存储在索引服务器的易失性存储器中以表示(例如，通过在帖子列表中包括文档D2的标识符)文档D2通过索引令牌“three”进行索引。为了表示这些变化352，不必修改索引数据库文件351。当处理查询(例如，332A)时，索引服务器处的查询处理器327既可以咨询索引数据库文件351(其可以高速缓存在RAM中)中用于给定查询令牌的基本帖子列表又可以咨询存储在易失性存储器中用于给定查询令牌的增量帖子列表。查询处理器327可以合并(例如，相交)增量帖子列表和基本帖子列表，以确定满足给定查询令牌的文档。

根据一些实施例，索引服务器处的查询处理器327在步骤802基于来自路由服务器420A的网络请求中的(一个或多个)文档命名空间组标识符来确定要访问的(一个或多个)索引。例如，查询处理器327可以基于来自路由服务器420A的网络请求中的文档命名空间组标识符来确定访问易失性存储器中的某(一个或多个)索引数据库文件351和/或某些数据结构(例如，字典，帖子列表等)。

在步骤804，对于在步骤802确定的要访问的每一个索引，从索引中加载用于查询332A中的(一个或多个)查询令牌的帖子列表。这种加载可以包括检索存储在索引服务器处的非易失性存储器中的帖子列表并且将帖子列表存储在索引服务器处的易失性存储器中。在一些情况中，帖子列表可能已经被存储(高速缓存)在索引服务器处的易失性存储器中。在这种情况中，可以不需要从索引服务器处的非易失性存储器中检索帖子列表。

在步骤806，如果在步骤804加载了若干帖子列表，那么相应地合并若干帖子列表以产生可以包括满足(匹配)查询332A的一个或多个文档的一个或多个标识符的单个“结果”帖子列表。为了确定满足(匹配)给定查询的文档，可以使用各种不同的算法来合并帖子列表。本发明的实施例不限于任何特定的合并算法。如果，例如因为在查询332A中只有一个查询令牌，因此在步骤804仅加载了一个帖子列表，那么那个加载的帖子列表可以是结果帖子列表。

在步骤808，索引服务器处的查询处理器327根据排名算法对与查询332A匹配的结果帖子列表中的文档进行排序。排名算法可以涉及相关于查询332A的为每一个匹配文档计算排名分数。可以使用各种不同的排名算法并且本发明的实施例不限于任何特定的排名算法。例如，排名算法可以基于查询相关的度量和/或查询无关的度量为查询令牌和匹配文档计算排名分数。

在步骤810，索引服务器处的查询处理器327生成对查询332A的个性化应答(例如，418A)并且在网络响应中将该应答发送到路由服务器420A。个性化应答可以仅识别属于要搜索的授权文档命名空间的匹配文档。为了便于这一点，在结果帖子列表中识别出的每一个匹配文档可以与匹配文档所属的文档命名空间的标识符相关联。索引服务器处的查询处理器327可以将匹配文档的文档命名空间标识符与包括在来自路由服务器420A的网络请求中的(一个或多个)授权文档命名空间标识符集合进行比较，以确定是否应该在个性化应答中识别该文档。如果基于这个比较，匹配文档属于授权文档命名空间，那么可以在个性化应答中识别匹配文档。否则，不能在个性化应答中识别匹配文档。

处理完成查询

图9是图示根据本发明的一些实施例的由索引服务器(例如，430B)处的查询处理器327执行的用于当查询332A是完成查询时生成对查询332A的个性化应答(例如，418A)的过程900的流程图。

可以在网络请求中从路由服务器(例如，420A)接收完成查询332A。网络请求还可以包括要搜索的一个或多个授权文档命名空间的一个或多个标识符。此外，每一个这种授权文档命名空间标识符可以在网络请求中与该文档命名空间所属的文档命名空间组的标识符相关联。此外，网络请求可以指示或指定完成查询332A的哪个查询令牌是完成令牌。完成查询332A中的任何其它查询令牌被认为是完整令牌。

根据本发明的一些实施例，索引服务器(例如430B)处的索引碎片(例如，328B)可以包括用于分配给索引碎片的一个或多个文档命名空间组中的每一个的“完成”索引。每一个这种完成索引可以包括完成字典和对应的帖子，其一起对属于该完成索引的文档命名空间组的一个或多个文档命名空间中的文档进行索引。

根据本发明的一些实施例，当处理属于该完成索引的文档命名空间组的要搜索的授权文档命名空间的完成查询332A时，索引服务器(例如，430A)处的查询处理器327访问用于文档命名空间组的完成索引。

根据本发明的一些实施例，完成索引仅对文档的文件名进行索引。即，完成字典中的索引令牌限于从属于完成索引的文档命名空间组的一个或多个文档命名空间中的文档的文件名中提取的令牌。通过这样做，完成索引的尺寸可以相对于文档命名空间组的全文索引或其它索引更小，从而有助于由索引服务器处的查询处理器327更高效地处理完成查询332，同时仍然提供与完成查询332相关的应答418。

如所提到的，完成字典包括以词典编纂排序顺序排序的前缀索引令牌。每一个这种前缀索引令牌包括具有文档命名空间标识符的索引令牌前缀。排序的前缀索引令牌可以在易失性和/或非易失性存储器中以排序顺序彼此靠近地存储(聚集)。通过这样做，以排序顺序迭代前缀索引令牌可以有助于迭代期间的顺序存储器访问，并且减少迭代期间的随机存储器访问，从而使索引服务器处的查询处理器327更高效地迭代在完成字典中共享公共前缀的前缀索引令牌集合。

现在转到图9，在步骤902，索引服务器处的查询处理器327为完成查询332A的查询令牌生成用于在访问一个或多个完成字典时使用的索引关键字。通常，通过以与完成字典中的前缀索引令牌的形式匹配的形式用授权文档命名空间标识符为查询令牌加上前缀来生成索引关键字。例如，如果完成字典中的前缀索引令牌的形式是<document namespaceidentifier>:<index token>，那么生成的索引关键字的形式可以是<authorizeddocument namespace identifier>:<query token>。

在步骤902，索引服务器处的查询处理器327可以为每一个查询令牌生成若干索引关键字，要搜索的多个授权文档命名空间中的每一个一个索引关键字，其中每一个这种要搜索的授权文档命名空间被分配给索引服务器的索引碎片。

可以由索引服务器处的查询处理器327为在来自路由服务器420A的网络请求中指定的要搜索的每一个授权文档命名空间执行步骤904-916。

在步骤904，对于要搜索的给定授权文档命名空间，在步骤902为完成查询332A的任何(一个或多个)完整令牌生成的任何(一个或多个)索引关键字被用来访问用于给定授权文档命名空间所属的文档命名空间组的完成字典。特别地，与(一个或多个)索引关键字相关联的(一个或多个)帖子列表被加载用于完成查询332A中的(一个或多个)完整令牌。

在步骤906，对于要搜索的给定授权文档命名空间，在步骤904为(一个或多个)完整令牌加载的任何(一个或多个)帖子列表被合并以产生用于完成查询332A中的(一个或多个)完整令牌的“结果”帖子列表。

除了为在来自路由服务器420A的网络请求中指定的要搜索的每一个授权文档命名空间执行步骤908-916之外，可以为在完成字典中识别出的作为对完成查询332A中的完成令牌的可能的完成的多个可能的完成令牌中的每一个执行步骤908-916。

为授权文档命名空间执行的步骤908-916通常涉及使用为完成令牌生成的索引关键字来访问完成字典，并且以多个前缀索引令牌的词典编纂顺序在多个前缀索引令牌上迭代，直到达到停止条件。为授权文档命名空间迭代的多个前缀索引令牌中的每一个可以包括授权文档命名空间的标识符作为前缀、索引令牌作为后缀，并且完成令牌是索引令牌的前缀或与索引令牌匹配。同样在迭代期间，对于多个前缀索引令牌中的每一个前缀索引令牌，做出在与前缀索引令牌相关联的帖子列表中识别出的任何文档是否满足完成查询的确定。可以在对完成查询的应答中返回确实满足完成查询的帖子列表中的文档的信息。在一些实施例中，前缀索引令牌来自文档的文件名并且在对文档的完成查询的应答中返回的信息是文档的文件名。

在本发明的一些实施例中，不是以前缀索引令牌的词典编纂顺序迭代多个前缀令牌，而是以对应帖子列表尺寸的递减顺序迭代前缀索引令牌，其中，帖子列表的尺寸由在帖子列表中识别出的文档的数量来确定。通过以这种顺序对前缀索引令牌进行迭代，在对完成查询的应答中考虑首先包括由其索引大多数文档的完成令牌的可能的完成。

为了便于这种迭代，可以在索引服务器处维护辅助的每命名空间令牌-频率映射。映射中的每一个条目包括关键字和对应的值。每一个这种关键字包括索引令牌并且每一个这种值包括用于索引令牌和文档命名空间的完成字典中的帖子列表的尺寸。辅助映射的条目可以在映射中以条目关键字的索引令牌的词典编纂顺序排序，并且条目可以以其排序的顺序存储(聚集)在连续的易失性和/或非易失性存储器位置中。这允许索引服务器处的查询处理器327更高效地识别共享匹配完成查询332A中的完成令牌的公共前缀的辅助映射中的所有索引令牌。一旦识别所有这种索引令牌，它们就以如由辅助映射中的条目值所指定的它们的帖子列表尺寸的降序来排序。作为结果的索引令牌的排序顺序是当访问完成字典和考虑对完成令牌的可能的完成时索引令牌的迭代顺序。因为辅助映射不存储用于索引令牌的实际帖子列表，因此辅助映射在就字节而言的尺寸上比完成索引的尺寸小得多。因此，用于索引令牌的迭代顺序可以根据辅助映射来确定，其比如果迭代顺序根据完成索引本身来确定具有较少的存储器I/O操作。

在步骤908，查询处理器327确定是完成令牌的可能的完成的迭代顺序中的下一个索引令牌。如刚刚讨论的，迭代顺序可以基于共享匹配完成令牌的公共前缀的索引令牌的词典编纂次序或基于索引令牌的帖子列表尺寸的降序。

在步骤910，查询处理器327为在步骤908的迭代中确定的对查询332A中的完成令牌的当前可能的完成令牌加载帖子列表。在一些情况中，用于当前可能的完成令牌的帖子列表可能已经存储在索引服务器处的易失性存储器中。在这种情况中，可以不必从非易失性存储器中检索帖子列表。

在步骤912，如果完成查询332A中存在任何(一个或多个)完整令牌，那么在步骤906确定的(一个或多个)完整令牌的结果帖子列表与在步骤910的迭代中确定的对完成令牌的当前可能的完成令牌的帖子列表合并。由这个合并产生的完成查询332A的这种当前“结果”帖子列表可以包括满足完成查询332A的授权文档名称空间中的一个或多个文档的标识符，其中完成令牌用当前可能的完成令牌替换。如果完成查询332A中没有任何完整令牌，那么完成查询332A的当前结果帖子列表可以是在步骤910的迭代中为当前可能的完成令牌加载的帖子列表。

在步骤914，如果完成查询332A的当前结果帖子列表是非空的(即，它在授权文档命名空间中识别至少一个文档)，那么可以在对完成查询332A的应答(例如，418A)中发送在用于完成查询332A的当前结果帖子列表中识别出的每一个文档的信息。在一些实施例中，这种信息包括文档的文件名。

虽然在一些实施例中，在对完成查询332A的应答(例如，418A)中返回文档的文件名，但是如果用于完成查询332A的当前结果帖子列表是非空的，那么在对完成查询332A的应答(例如，例如418A)中返回用当前可能的完成令牌替换完成令牌的完成查询332A。在任一情况中，在对完成查询332A的应答(例如，418A)中返回的信息可以最终呈现在终端用户的计算设备处，用于由用户选择和用于另一查询332A提交给服务系统325。

在步骤916，索引服务器处的查询处理器327确定是否继续迭代对完成查询332A中的完成令牌的可能的完成令牌。根据一些实施例，如果已经达到停止条件，那么查询处理器327停止迭代。根据一些实施例，当以下条件中的任一个变为真时达到停止条件：

·已识别满足完成查询332A的阈值数量的文档，其中完成查询332A中的完成令牌用可能的完成令牌替代

·已考虑阈值数量的可能的完成令牌，或者

·查询执行计时器已过去。

如果在步骤916确定已经达到停止条件，那么对完成查询332A中的完成令牌的可能的完成令牌的迭代结束。否则，在步骤908处对下一个可能的完成令牌再次继续迭代。

用于处理完成查询的以上过程向终端用户提供多个益处。例如，该过程可以减少用户接收识别感兴趣的文档的应答所花费的时间。对于另一个益处，该过程可以减少用户需要输入到搜索字段中以找到感兴趣的文档的击键的数量。对于再另一原因，该过程可以减轻用户记住令牌的正确拼写的负担。

虽然在一些实施例中，以上过程提供文档文件名的个性化搜索查询自动完成，但是在其它实施例中，上述过程提供文档内容的个性化搜索查询自动完成。

扩展和替代方案

虽然本发明具体参考了单个优选实施例和某些替代方案进行了详细描述，但是并不旨在将本发明限制到该特定实施例或那些具体替代方案。因此，本领域技术人员将理解的是，在不脱离本发明的教导的情况下，可以对优选实施例进行修改。