对列入访问控制表的文档进行的高效索引和搜索的制作方法
对列入访问控制表的文档进行的高效索引和搜索的制作方法
【专利摘要】一种方法、系统和设备，其包括在计算机存储介质上编码的计算机程序，该计算机存储介质用于将多个文档存储在计算机可读存储器中，多个文档中的每个文档具有对应的访问控制表（ACL），每个ACL限定被授权访问相应的文档的多个用户，基于多个用户而生成索引，索引包括多个分区，每个分区对应于多个用户中的用户，并且针对多个文档中的每个文档：对多个用户中的用户进行排序，基于排序而将用户选择为索引用户，以及将文档存储在索引的分区中，该分区对应于索引用户。
【专利说明】对列入访问控制表的文档进行的高效索引和搜索
[0001]相关联_请的交叉引用
[0002]本专利申请要求于2011年3月11日提交的美国临时专利申请N0.61/452，013的优先权，上述临时专利申请的公开内容明确地通过引用被全文并入于此。
【背景技术】
[0003]本说明书一般涉及对文档的索引和捜索，通过相应的访问控制表(ACL)来调节对上述文档的访问。
[0004]伴随着协作文档和社交网络的发展，越来越多的内容与ACL —起被存储，所述ACL指定可以访问文档的ー组人。在这样的一系列文档上进行捜索呈现了某些挑战。例如，一个用户看到的文档可能与另ー用户看到的文档不同。通过向文档增加ACL令牌，此问题可被解決，每个ACL令牌代表ー个拥有访问对应文档的许可的用户。但是，这种方法的问题是捜索系统必须执行较大命中列表的交集，这在基于磁盘的索引方案中是特别有问题的。一种基于磁盘的索引系统的方法是为对文档拥有许可的每个人写该文档的单独副本。这称为写扇出。虽然这提高了捜索的效率，但是也极大地増加了索引的大小和文档写速率。ー个可替换的解决方案包括将具有ACL令牌的每个文档的单独副本写入对应于每个文档所有者的子索引(分区)，并对来自于处于搜索时间的用户的每个协作者的结果进行合井。这称为读扇入。虽然这提高了文档写的效率，但是当用户有许多协作者时，捜索可能以合并数目很大的结果集的方式而告終。
【发明内容】
[0005]本公开的实施方式涉及方法和系统，其用于对被列入访问控制表的(ACL’d)文档进行索引和捜索。本公开的实施方式提供捜索索引，其可以被用于有效地捜索被列入访问控制表的文档，每个索引被分区成特设组，其中，在ー个或多个特设组中，对每个文档进行索引。索引将文档放入ー组用户和组分区中，而搜索对来自于ー组用户和组分区的结果进行合井。为了更有效的搜索行为，可以在分区之间移动或复制文档。
[0006]一般来说，在本说明书中描述的主题内容的创新的方面可以体现为ー种方法，其包括如下动作:将多个文档存储在计算机可读存储器中，所述多个文档中的每个文档具有对应的访问控制表(ACL)，每个ACL限定被授权访问相应的文档的多个用户，基于所述多个用户而生成索引，所述索引包括多个分区，每个分区对应于所述多个用户中的用户，以及，针对所述多个文档中的每个文档:对所述多个用户中的用户进行排序，基于所述排序而将用户选择为索引用户，以及将所述文档存储在所述索引的分区中，该分区对应于所述索引用户。
[0007]这些和其它实施方式可能每个都优选地包括一个或多个下列特征。例如，所述动作进ー步包括基于所述多个用户而生成索引映射，所述索引映射包括多个映射分区，每个映射分区对应于所述多个用户中的用户，并且包括对所述索引的相应的ー个或多个分区的ー个或多个引用；其中，排序包括:确定多个用户标识符，每个用户标识符对应于所述多个用户中的用户，以及基于所述多个用户标识符而对所述用户进行排序；其中，基于所述多个用户标识符而对所述用户进行排序包括:针对每个用户标识符生成对应的哈希值，以提供多个哈希值，对所述多个哈希值进行排序，以提供排序，以及基于所述排序而选择所述索引用户；其中，所述索引用户对应于所述排序内的最小哈希值；其中，所述索引用户对应于所述排序内的最大哈希值；所述动作进ー步包括:基于所述索引而生成复制索引，所述复制索引包括至少ー个分区，其包括ー个或多个复制文档，所述ー个或多个复制文档中的每一个复制文件是对多个文档中的文档的复制，并且基于所述多个用户而生成索引映射，所述索引映射包括多个映射分区，每个映射分区对应于所述多个用户中的用户，并且包括对所述索引和所述复制索引的相应的ー个或多个分区的ー个或多个引用；所述动作进ー步包括:监控所述多个文档中的文档被更新的频率，并且基于所述频率而确定是否复制所述文档；所述动作进ー步包括:监控对应于特定用户的ー个或多个文档被提供为搜索结果的频率，在对ー个或多个搜索查询的响应中提供所述搜索結果，并且基于所述频率而确定是否复制所述文档；所述动作进ー步包括:确定与所述多个文档中的文档相关联的重索引代价，基于ー个或多个文档大小、更新定时和搜索频率来确定所述重索引代价，将所述重索引代价与代价阈值相比较，当所述重索引代价小于所述阈值吋，复制所述文档；所述动作进ー步包括:接收输入，所述输入对应于所希望的重索引比率，基于所述输入而调整将一个或多个文档复制为所述复制索引的发生比率；所述动作进ー步包括:接收搜索查询，所述搜索查询包括一个或多个关键字和用户身份，基于用户身份而选择所述多个分区中的分区，基于所述一个或多个关键字而搜索与所述分区相关联的一个或多个文档，基于所述搜索而生成搜索結果。
[0008]在下面的附图和说明书中，给出了在本说明书中描述的主题内容的ー个或多个实施方式的详细信息。根据说明书、附图和权利要求书，该主题内容的其他潜在特征、方面和优点会变得明显。
【专利附图】
【附图说明】
[0009]图1描述ー个示例系统，其用于基于访问控制表(ACL)对文档进行高效索引和搜索。
[0010]图2描述ー个示例二分图，其说明用户和文档之间的示例访问关系。
[0011]图3是ー个表,其基于图2描绘出的关系而概述ー个不例ACL。
[0012]图4A是根据本公开的实施方式的示例索引。
[0013]图4B是根据本公开的实施方式的示例分区映射。
[0014]图5是基于文档协作者的包括分区的示例索引。
[0015]图6是基于文档所有者的包括分区的示例索引。
[0016]图7A基于图4A的示例索引描述ー个示例复制索引。
[0017]图7B基于图4A的示例索引和图7A的示例复制索引描述ー个示例分区映射。
[0018]图8是ー个示例进程的流程图，其用于对列入访问控制表的文档进行高效索引和搜索。
[0019]遍及全文，类似的附图标号代表对应的组件。【具体实施方式】
[0020]本公开一般地涉及基于访问控制表(ACL)限制用户对ー个或多个文档的访问。如在此所用的，术语“文档”可涉及任何协作介质，诸如可被多个用户用电子方式查看和/或编辑的电子介质等。示例文档可包括用电子方式创建并存储的协作文档，诸如文字处理文档、电子表格文档、演示文档、以及与ー个或多个社交网络服务相关联的文档等(例如共享的帖子、图片等)。
[0021]正如在此进ー步详细讨论的，本公开的实施方式提供对协作文档的高效索引和搜索。例如，可生成并存储多个文档。所述多个文档的每个文档均可被列入访问控制表(列入ACL的)，以便对每个文档的访问仅仅提供给指定的用户。提供了用于实现捜索索引的技木，所述搜索索引可以被用于有效地捜索被列入访问控制表的文档。该索引被分区成每个用户文档集和特设组(ad-hoc groups)。索引将文档放入ー组用户和组分区,而搜索对来自于ー组用户和组分区的结果进行合井。为了更有效的搜索行为，文档可在分区之间移动或复制。
[0022]图1描述ー个示例系统100，其用于对被列入访问控制表的(列入ACL的)文档进行高效索引和搜索。系统100包括计算设备102A-102F，其每个都可以与在网络106上的一个或多个服务器系统104通信。计算设备102A-102F中的每个计算设备分别包括相关联的用户108A-108F。网络106可包括大型计算机网络，诸如连接任意多的移动计算机、固定计算设备和服务器系统的局域网(LAN)、广域网(WAN)、因特网、蜂窝网络或其组合。服务器系统104包括计算设备110和机器可读仓储库或数据库112。可以理解的是，虽然描述了单个服务器系统104，但是所述单个服务器系统可代表一个或多个服务器系统。
[0023]在示例系统100中，计算设备102A-102C示为台式计算设备，计算设备102D、102F示为膝上型计算设备，并且计算设备102E示为移动计算设备。但是，可以理解的是，计算设备102A-102F可每个都包括任何类型的计算设备，诸如台式计算机、膝上电脑、掌上电脑、个人数字助理(PDA)、蜂窝电话、网络家电、摄影机、智能电话、增强型通用分组无线电业务(EGPRS)移动电话、媒体播放器、导航设备、电子邮件设备、游戏控制台或任何两个或更多个上述数据处理设备或其他数据处理设备的组合。
[0024]计算设备102A-102F使各用户108A-108F能创建、访问、查看和/或编辑诸如协作文档等的文档。文档可用电子方式存储在存储器中。在一些实施方式中，文档可存储在ー个或多个计算设备102A-102F和/或服务器系统104上。在网络106上，计算设备102A-102F和/或服务器系统104可以互相之间进行通信，以使得能访问来自于其它计算设备102A-102F和/或服务器系统104的任何一台的文档。在一些实施方式中，使用计算机应用的用户108A-108F可生成、访问、查看和/或编辑文档，相应的计算设备102A-102F执行所述计算机应用。在一些实施方式中，使用计算机应用的用户108A-108F生成、访问、查看和/或编辑文档，服务器系统104执行所述计算机应用。在一个这样的实施方式中，该计算机应用可作为基于网络的应用程序(网络应用)而被提供；该基于网络的应用使用服务器系统104执行，并且从在网络106上的ー个或多个计算设备102A-102F接收输入并向其提供输出。
[0025]图2描述ー个示例二分图200，其说明用户202和文档204之间的示例访问关系。用户202包括用户A-F。出于说明目的，用户A-F可对应于图1的用户108A-108F。文档204包括文档文档1-文档7。二分图200可基于ー个示例ACL，其限定用户A-F和文档文档1-文档7之间的关系。例如，二分图200规定:用户A可以访问文档文档1、文档2和文档6，用户B和C中的每个用户都可以访问文档文档1-文档3、文档5和文档6，用户D和E可以访问文档文档4和文档7，并且用户F可以访问文档文档7。
[0026]用文档文档I为例，用户A (例如，图1的用户108A)可以通过使用计算设备(例如，图1的计算设备102A)来生成文档文档I。文档文档I可存储在计算设备和/或服务器系统(例如，图1的计算设备102A和/或服务器系统104)中。用户A可以被指定为文档文档I的所有者。在一些实施方式中，文档的所有者是文档的创建者。用户A可以指定对文档文档I进行访问和访问/编辑的权利。例如，用户A可以指定用户B和用户C具有对文档文档I进行访问/编辑的权利。在ACL中可提供此指定信息，该ACL记录了哪些用户202具有对哪些文档204的进行访问/编辑的权利。
[0027]图3是一个表300,其基于图2描绘出的关系而概述一个不例ACL。表300包括文档列302、协作者列304和所有者列306。文档列302和协作者列304提供在如图2所示出的用户202和文档204之间的关系。所有者列306描述每个文档的相应的所有者。按照实例表300，用户A是文档文档I的所有者，用户B是文档文档1-文档3和文档5的所有者，用户C是文档文档6的所有者，用户D是文档文档4的所有者，并且用户E是文档文档7的所有者。用户F未被指定为文档文档1-文档7中的任何ー个的所有者。
[0028]如上所述，文档文档1-文档7中的每个可存储在计算机可读存储器中。可生成索弓丨，以使得对存储的文档进行高效搜索，从而基于搜索查询而识别相关联文档。例如，用户(例如，一个或多个用户108A-108F)可生成搜索查询，而基于该搜索查询可以访问该索引，从而识别可能和该搜索查询相关联的ー个或多个文档。捜索结果可被提供给查询的用户，捜索结果可包括对ー个或多个文档的识别。如果该用户被指定为可以访问所述ー个或多个文档的ー个或多个，该用户可以选择并访问文档。
[0029]本公开的实施方式使得生成索引和/或为现有的索引生成重索引，从而为取决于ACL的文档提供高效索引和捜索。一般来说，诸如图2的二分图200之类的二分图通常不是随机的。与彼此相隔很远的用户相比，已经共享文档和/或以其他方式在二分图中彼此接近的用户更可能分享文档。多个文档经常被同样的或类似的用户组共享。鉴于此，可基于协作者将文档聚类，以便每个用户可以在数目相对较小的聚类中发现所有文档，在该较小的聚类中他们是协作者。根据本公开的实施方式，在用户之中的总排序可以被确定，每个共享文档的用户可以被选择为用于特定文档的索引器。在一些实施方式中，如在此进一歩详细讨论的，基于ー个用户在特定共享文档的其他用户中的排序，该用户被识别为索引器。使用此方法论，数目更小的索引器覆盖ー个用户可以访问的所有文档。多数用户会仅仅需要捜索相对很少的索引器。但是数目较少的用户可能需要捜索数目更大的索引器，如在此进ー步详细讨论的，其由文档的所选定的复制解決。因此，基于在用户之中的总排序来选择用于每个文档的索引用户，这使得数目更小的索引用户可覆盖特定用户可以访问的所有文档。
[0030]根据本公开的实施方式，基于与每个用户相关联的哈希值，对用于特定文档的协作用户进行排序。基干与特定文档的用户相关联的相应的用户标识(用户ID)，可以确定所述哈希值。例如，每个用户标识可作为哈希函数的输入。哈希函数可以作为明确定义的程序或数学函数，其将每个用户标识转换成哈希值。例如，哈希值可作为整数，也可作为数组的索引。在一些实施方式中，最小哈希值可用作用于特定文档的索引。在一些实施方式中，最大哈希值可用作用于特定文档的索引。
[0031]通过非限制性的第一示例，并且出于说明目的，将考虑所述用户A、B、C和文档文档1、文档2、文档6。用户A、B、C中的每个都可以具有相关联的用户ID (例如，IDa、IDb,ID。)。使用哈希函数，可处理每个用户标识，以提供相应的哈希值(例如，HVa、HVb、HV。)。例如，可以处理所述哈希值，以确定最小哈希值和最大哈希值中的ー个。仅仅出于说明目的，HVa可以小于HVb和HV。。因此，HVa可以视为最小哈希值，并且，在用户A是与用户B和C 一起的协作者的情况下，如參考图4A和图4B在下面进ー步详细讨论的，HVa还可以被选择为用于所有文档的索引。例如，即使用户B是文档2的所有者、用户C是文档3的所有者，用户A也可以被选择为用于文档文档1、文档2、文档6的索引。
[0032]通过非限制性的第二示例，并且出于说明目的，HVb可以小于HVC。因此，HVb可以视为在用户B和C之间的最小哈希值，并且，在用户B是与用户C 一起的协作者的情况下，如參考图4A和图4B在下面进ー步详细讨论的，HVb还可以被选择为用于所有文档的索引。例如，用户B可被选择为用于文档文档3、文档5的索引。
[0033]根据本公开的实施方式，图4A是示例索引400。索引400基于图3的表300，并包括分区402-412。分区402-412中的每ー个都作为索引，(分別)对应于(用户A-F中的)一个用户。使用上述第一示例，基于哈希值HVa、HVb, HV。，用户A可以被选择为用于文档文档
1、文档2、文档6的索引。因此，文档文档1、文档2、文档6被存入分区402，所述分区402被用户A索引。使用上述第二示例，基于哈希值HVB、HV。，用户B可被选择为用于文档文档
3、文档5的索引。因此，文档文档3、文档5被存入分区404，所述分区404被用户B索引。因为根据上述第一示例和第二示例，用户C未被选择为用于任何文档的索引，其中用户C是协作者，分区406是空的。
[0034]在图4A中，被用户D索引的分区408包括文档文档4、文档7。在图4A的示例中，用户E、F未被选择为用于任何文档的索引，其中，用户E、F是协作者。因此，所述分区410、412是空的。这表示:对应于用户D的哈希值(HVd)小于分别对应于用户E、F的两个哈希值(HVe^HVf)0
[0035]图4B是根据本公开的实施方式的示例分区映射420。分区映射跟踪共享文档被索引到哪里，还跟踪去哪里搜索每个用户。在一些实施方式中，提供连续的清洁扫描(cleanerscanlet)。清洁扫描删除废弃的搜索扇入边缘和重索引文档，以减少搜索扇入。清洁扫描修整共享边缘，所述共享边缘具有不频繁更新的小文档和频繁的搜索。在一些实施方式中，通过复制文档，清洁扫描完成这种修整。例如，如果当前特定文档仅仅与创建者用户一起保存，并且用户A仅仅不得不搜索创建者用户的索引，该索引是用于那ー个文档的，那么该清洁扫描可从创建者用户的索引复制该文档至用户A的索引，因此减少了ー个(文档)所需要的扇入。一般来说，分区映射使捜索时间操作最小化，并通过避免事务来简化写时间操作。清洁扫描可脱机地操作，以将读者映射同步到文档共享状态。共享映射跟踪哪些用户可以阅读特定文档，还跟踪该文档目前被索引到哪些共享索引位置。读者映射针对每个读者跟踪，他们在哪些共享索引位置处可以发现那名读者共享的所有文档。
[0036]继续參考图4B，分区映射420包括分区422-432，其对应于图4A的分区402-412。分区映射420映射的是，哪些分区是要扇入的。換言之，分区映射420映射的是，索引400的哪些分区402-412会构成对应于每个用户的文档列表。例如，分区422对应于用户A，并且包括对应的扇入指定A。这表示在分区402中保存的文档将被扇入该分区422。作为另一示例，分区424对应于用户B，并且包括对应的扇入指定A、B。这指示在分区402、404中保存的文档将被扇入该分区422。因此，文档文档1、文档2、文档3、文档5、文档6被扇入该分区422，该分区422对应于用户B是在其上的协作者的文档(參看图2和图3)。作为另ー示例，分区426对应于用户C，并且包括对应的扇入指定A、B。这表示在分区402、404中保存的文档将被扇入该分区426。因此，文档文档1、文档2、文档3、文档5、文档6被扇入该分区426，该分区426对应于用户C是在其上的协作者的文档(參看图2和图3)。
[0037]根据图4A和图4B，相对于传统的索引技术，在下面进ー步详细讨论了索引的效率。
[0038]图5是基于文档协作者的包括分区502-512的示例索引500。根据这种可以称作写扇出方法的技术，存储每个文档的单独副本，这是为了那些可以访问该文档的每个用户。使用图2和图3的示例，分区502包括文档文档1、文档2、文档6，用户A是这些文档上的协作者。分区504、506每个都包括文档文档1、文档2、文档3、文档5、文档6，用户B、C是这些文档上的协作者。分区508、510每个都包括文档文档4、文档7，用户D、E是这些文档上的协作者。而分区512包括文档文档7，用户F是这文档上的协作者。
[0039]虽然用图5说明的基于协作者的索引技术提供了高效搜索，但是索引和文档写比率的大小也显著地增大了。例如，图4A的索引400包括7个文档，而图5的索引500包括18个文档。当协作者数目和文档数目增加时，这就更复杂了。
[0040]图6是基于文档所有者的包括分区602-612的示例索引600。根据这种可以称作读扇出方法的技木，将每个文档的单独副本写入对应于每个文档所有者的分区，并且将来自于处于搜索时间的用户的每个协作者的搜索结果合并在一起。虽然此技术对于写是高效的(例如，图6的索引600包括7个文档，而图5的索引500包括18个文档)，但是，当用户有许多协作者时，捜索可能以合并数目很大的结果集的方式而告終。
[0041]在此讨论的基于用户排序的索引的实施方式为大多数用户提供了良好的文档分发。但是，可以理解的是，数目较少的用户可能仍然有大的搜索扇入。为了应对这样的情況，可在多个索引位置处复制文档的小集合，以便限制用于所有用户的检索扇入。換言之，通过将文档的小子集有选择地复制到多个索引，可以改进捜索扇入。在一些实施方式中，使用后台进程，异步地进行复制。在一些实施方式中，基于用户排序的选择，可以进一歩改进搜索扇入。
[0042]在一些实施方式中，捜索扇入可被限制在阈值(例如，10)。在捜索扇入超过该阈值的情况下，可以选择具有最小总文档大小的索引位置，将来自于那些位置的所有文档复制到捜索者自己的索引位置。这样的实施方式可称为简单扇入限制。
[0043]在一些实施方式中，作为上述简单扇入限制的替代方案，可提供动态文档复制。特别地，可采集文档的更新定时，还可估计每个文档的下ー个更新时间。在这种方式下，在复制一个文档是否值得方面可做出更好的决策。例如，如果估计一个文档(例如，在阈值时间内)会被频繁地和/或相对很快地更新，那么可以放弃对那个文档的复制。进ー步，可以采集用户的搜索定时，还可以估计搜索频率。在这种方式下，可以识别频繁的捜索者，并且，与不频繁捜索者相比，可以更积极地減少对应于频繁搜索者的捜索扇入。[0044]在一些实施方式中，提供了重索引代价，其代表关于是否删除通过复制进行的扇入的成本ー效益比率。可基于文档大小、更新定时和搜索频率来确定重索引代价。可以提供动态代价阈值。可以将重索引代价与对应的代价阈值相比较，以确定是否复制文档。例如，如果重索引代价大于代价阈值，就不复制这些文档了。
[0045]在一些实施方式中，提供了控制项，以便调节总的重索引比率。总的重索引比率可对应于被花费在复制上的总带宽。控制项可用于调节上述代价阈值，以满足带宽限制。在这种方式下，可以控制复制流量的冲击，并且，当文档越来越不频繁更新时(例如，夜晚和周末)的非高峰时间可以用于更积极的复制。可以提供捜索扇入阈值，以便约束最坏情况扇入。阈值覆盖了用于大读者的代价阈值，虽然代价还用于对读者的扇入边缘进行排序，以及用于选择要删除的边缘。在一些实施方式中，大读者是扇入很大(例如，大于某个阈值的)的用户。用户的扇入边缘被规定是:为了查看被该用户共享的所有文档而需要被访问的其他用户索引的数目。
[0046]代价阈值代表对文档进行复制的成本ー效益分析。根据文档大小、更新定时和读者的搜索频率来计算该代价。例如，如果ー个文档被频繁地更新，复制它的成本是很高的，这是因为一旦它被再次更新，就将失去该效益。被频繁地捜索的很少更新的小文档可以被低成本、高效益地复制。
[0047]图7A基于图4A的示例索引400描述ー个示例复制索引700。复制索引700包括分区702-712，其对应于示例索引400的分区402-412。示例复制索引700包括对在分区706中的文档1、文档2、文档3、文档5、文档6的复制；在每个图4B的分区映射420中，示例复制索引700对应于对在示例索引400的分区402、404中的文档进行的写扇入。图7B基于图4A的示例索引400和图7A的示例复制索引700而描述一个示例分区映射740。分区映射740包括分区742-752，其对应于索引400的分区402-412。
[0048]可以实现索引400、700，以便基于被用户输入的捜索查询而提供捜索结果。示例搜索查询可包括一个或多个关键字和用户身份。在这种方式下，对应的搜索引擎可处理该搜索查询，以识别所标识的用户可以访问的文档，该文档包括一个或多个搜索查询。分区映射(例如，图7A的分区映射740)可以被用于确定索引的哪些分区对应于所标识的用户(例如，索引400的分区402-412和/或图7A的复制索引700的分区702-712)。可基于ー个或多个关键字捜索在ー个分区内的文档，并且，可以生成捜索结果，该搜索结果包括与所标识的用户相关联的文档，并且该文档包括所述ー个或多个关键字中的一个或多个关键字。
[0049]通过ー个非限制性的示例，搜索查询可包括“用户B”和“关键字”。搜索引擎可以接收该搜索查询作为输入，并且，可以基于用户B而访问图7B的分区映射740。在这种情况下，用户B对应于分区744，其识别在图4A和7B的索引400中的、与用户A和B相关联的、要被扇入的文档。因此，可以基于关键字而搜索包括文档1、文档2、文档3、文档5和文档6的文档集，以便在该文档集内识别包括该关键字的任何文档。可以在搜索结果中提供在该文档集内的包括该关键字的任何文档。
[0050]图8是ー个示例进程800的流程图，其用于对列入访问控制表的文档进行高效索弓I。将多个文档存储在计算机可读存储器中(802)。例如，图1的服务器系统104可以存储多个文档。多个文档中的每个文档都具有对应的ACL，并且每个ACL限定被授权访问相应的文档的多个用户。基于多个用户生成索引(804)。例如，基于多个用户，图1的服务器系统104可以生成索引。索引包括多个分区，每个分区对应于多个用户中的用户(例如，图4A的索引400)。对于多个文档中的每个文档，对多个用户的用户进行排序(806)，基于该排序将ー用户选择为索引用户(808)，并且将文档存储在索引的分区中(810)，该分区对应于该索引用户。例如，图1的服务器系统104可以针对多个文档中的每个文档，对多个用户中的用户进行排序，基于该排序而将用户选择为索引用户，并且将该文档存储在该索引的分区中。基于多个用户而生成索引映射(812)。例如，图1的服务器系统104可以生成索引映射。索引映射包括多个映射分区，每个映射分区对应于多个用户中的用户，并且包括对索引的相应的ー个或多个分区的ー个或多个引用。
[0051]基于索引而生成复制索引(814)。例如，图1的服务器系统104可以基于索引而生成复制索引。复制索引包括至少ー个分区，其包括ー个或多个复制文档，一个或多个复制文档中的每个复制文档都是对多个文档中的文档的复制。基于索引和复制索引生成经修订的索引映射(816)。例如，图4A的服务器系统104可以生成经修订的索引映射(例如，图7B的索引映射740)。
[0052]本公开的实施方式和在此提供的所有功能性操作均可以实现在数字电子电路中，或者实现在包括在本说明书和它们的结构等同物中公开的结构的计算机软件、固件、或硬件中，或者实现在其一个或多个的组合中。本公开的实施方式可被实现为一个或多个计算机程序产品，即在计算机可读介质上编码的计算机程序指令的一个或多个模块，该计算机可读介质或者被数据处理设备执行，或者控制该数据处理设备的操作。计算机可读介质可以是机器可读存储设备、机器可读存储基板、存储设备、实施机器可读传播信号的物质组合物、或其一个或多个的组合。术语“数据处理设备”涵盖用于处理数据的所有设备、装置和机器，举例来说，其包括可编程处理器、计算机、或多台处理器或计算机。除硬件之外，设备可包括创建了用于正在讨论的计算机程序的执行环境的代码，例如，构成了处理器固件、协议栈、数据库管理系统、操作系统、或其一个或多个的组合的代码。
[0053]计算机程序(也称为程序、软件、软件应用、脚本、或代码)可以以包括编译或解释语言的编程语言的任何形式编写，它也可以以包括作为独立程序或作为适合于在计算环境中使用的模块、组件、子程序、或其他単元的任何形式部署。计算机程序不一定对应于在文档系统中的文档。程序可以存储在保存其他程序或数据(例如，存储在标记语言文档中的一个或多个脚本)的文档的一部分中，或者存储在专用于正在讨论的程序的单个文档中，或者存储在多个协作文档(例如，存储ー个或多个模块、子程序、或代码的部分的文档)中。可以在一台计算机上或在多台计算机上部署要被执行的计算机程序，所述计算机位于ー个站点处、或横跨多个站点分布并通过通信网络互连。
[0054]通过执行一个或多个计算机程序的一个或多个可编程处理器，可以执行本公开描述的所述进程和逻辑流程，以便通过操作输入数据和生成输出来执行功能。所述进程和逻辑流程也能被专用逻辑电路，例如FPGA (现场可编程门阵列)或ASIC (专用集成电路)执行，并且设备也能被实现为专用逻辑电路，例如FPGA (现场可编程门阵列)或ASIC (专用集成电路)。
[0055]适合于执行计算机程序的处理器，举例来说包括一般微处理器和专用微处理器，以及任何ー种数字计算机的一个或多个处理器。通常，处理器将从只读存储器或随机访问存储器或两者来接收指令和数据。计算机的元件可包括用于执行指令的处理器和用于存储指令和数据的一个或多个存储器设备。通常，计算机将还包括用于存储数据的例如磁盘、磁光盘、或光盘的ー个或多个大容量存储器，或者可操作地耦合至用于存储数据的例如磁盘、磁光盘、或光盘的ー个或多个大容量存储器，以便从其接收数据或向其转移数据，或者两者兼有。但是，计算机不必具有这样的设备。此外，计算机可以嵌入在另ー个设备中，例如，移动电话、个人数字助理(PDA)、移动音频播放器、全球定位系统接收机中,仅举几例。适合于存储计算机程序指令和数据的计算机可读介质包括各种形式的非易失性存储器、介质和存储设备，举例来说例如包括EPROM、EEPROM和闪存设备的半导体存储设备；例如内置硬盘或可装卸磁盘的磁盘；磁光盘；以及⑶ROM和DVD-ROM盘。可以用专用逻辑电路来补充该处理器和存储器，或者可以在专用逻辑电路内合并该处理器和存储器。
[0056]为了提供与用户进行的交互，本公开的实施方式可在计算机上实现，该计算机具有例如CRT (阴极射线管)或LCD (液晶显示器)监视器的、用于向用户显示信息的显示设备，还具有用户可以由其向计算机提供输入的键盘和指示设备，例如鼠标或轨迹球。其他类型的设备也可用于提供与用户的交互；例如，提供给用户的反馈可以是任何形式的感知反馈，例如可视的反馈、可听的反馈、或触觉反馈；并且可以包括声学、语音或触觉输入的任何形式接收来自于用户的输入。
[0057]虽然本公开包括一些细节，但是这些(细节)不应当被解释为限制本公开或可以要求保护的范围，而是可解释为对本公开的示例实施方式的特征的描述。本公开在单独实施方式的上下文中描述的某些特征也可以在单个实施方式中以组合的形式提供。反过来说，在单个实施方式的上下文中描述的各种特征也可在多个实施方式中单独地或以任何合适的子组合形式提供。此外，虽然特征可以被上文描述为以某些组合的形式作用，并且甚至是这样最初要求保护的，但是，来自于所要求保护的组合的一个或多个特征在某些情况下可以从该组合中剔除，并且所要求保护的组合可以涉及子组合或子组合的变型。
[0058]类似地，虽然在附图中以特定次序描述了操作，但是这不应当被理解成要实现所希望的结果就需要以所示出的特定次序或以顺序次序执行这样的操作，或需要执行所示出的所有操作。在某些情况下，多任务和并行处理可以是有利的。此外，对在上述实施方式中的各种系统组件的分离不应当被理解成:需要在所有实施方式中进行这样的分离，并且应该理解的是:所述描述的程序组件和系统一般可能以单个软件产品的形式或以封装成多个软件产品的形式集成在一起。
[0059]因而，已经描述了本公开的特定实施方式。其他实施方式落在下面的权利要求书范围内。例如，可能以不同的次序执行按权利要求书中详述的动作，并且还能实现所希望的結果。已经描述了很多实施方式。然而，将理解的是，可以无需不脱离本公开的精神和范围而做出各种修改。例如，上面所示出的各种形式的流程，可能以具有重新排序的、増加的、或删除的步骤的方式使用。因此，其他实施方式落在下面的权利要求书的范围内。
【权利要求】
1.一种系统，其包括: 一个或多个处理器；以及 计算机可读存储介质，所述计算机可读存储介质被耦合到所述ー个或多个处理器，在所述计算机可读存储介质上存储有指令，当由所述ー个或多个处理器执行所述指令吋，所述指令使得所述ー个或多个处理器执行操作，所述操作包括: 将多个文档存储在计算机可读存储器中，所述多个文档中的每个文档具有对应的访问控制表(ACL)，每个ACL限定被授权访问相应的文档的多个用户； 基于所述多个用户来生成索引，所述索引包括多个分区，每个分区对应于所述多个用户中的用户；以及 针对所述多个文档中的每个文档: 对所述多个用户中的所述用户排序； 基于所述排序来将用户选择为索引用户；以及 将所述文档存储在所述索引的分区中，所述分区对应于所述索引用户。
2.如权利要求1所述的系统，所述操作还包括基于所述多个用户来生成索引映射，所述索引映射包括多个映射分区，每个映射分区对应于所述多个用户中的用户并且包括对所述索引中的相应的ー个或多个分区的ー个或多个引用。
3.如权利要求1所述的 系统，其中，排序包括: 确定多个用户标识符，每个用户标识符对应于所述多个用户中的用户；以及 基于所述多个用户标识符来对所述用户排序。
4.如权利要求3所述的系统，其中，基于所述多个用户标识符来对所述用户排序包括: 针对每个用户标识符，生成对应的哈希值以提供多个哈希值； 对所述多个哈希值排序以便提供排序；以及 基于所述排序来选择所述索引用户。
5.如权利要求4所述的系统，其中，所述索引用户对应于所述排序内的最小哈希值。
6.如权利要求4所述的系统，其中，所述索引用户对应于所述排序内的最大哈希值。
7.如权利要求1所述的系统，所述操作还包括: 基于所述索引来生成复制索引，所述复制索引包括至少ー个分区，所述至少ー个分区包括ー个或多个复制文档，ー个或多个复制文档中的每个复制文档是对所述多个文档中的文档的复制；以及 基于所述多个用户来生成索引映射，所述索引映射包括多个映射分区，每个映射分区对应于所述多个用户中的用户并且包括对所述索引和所述复制索引的相应的ー个或多个分区的ー个或多个引用。
8.如权利要求7所述的系统，所述操作还包括: 监控所述多个文档中的文档被更新的频率；以及 基于所述频率来确定是否复制所述文档。
9.如权利要求7所述的系统，所述操作还包括: 监控对应于特定用户的ー个或多个文档被作为搜索结果提供的频率，响应于一个或多个搜索查询而提供所述搜索结果；以及 基于所述频率来确定是否复制所述文档。
10.如权利要求7所述的系统，所述操作还包括: 确定与所述多个文档中的文档相关联的重索引代价，基于ー个或多个文档大小、更新定时和搜索频率来确定所述重索引代价； 将所述重索引代价与代价阈值相比较；以及 当所述重索引代价小于所述阈值时，复制所述文档。
11.如权利要求7所述的系统，所述操作还包括: 接收输入，所述输入对应于所希望的重索引比率； 基于所述输入来调整将一个或多个文档复制到所述复制索引的发生比率。
12.如权利要求1所述的系统，所述操作还包括: 接收搜索查询，所述搜索查询包括一个或多个关键字和用户身份； 基于所述用户身份来选择所述多个分区中的分区； 基于所述一个或多个关键字来捜索与所述分区相关联的一个或多个文档；以及 基于所述捜索来生成捜索結果。
13.一种计算机可读存储介质，所述计算机可读存储介质被耦合到一个或多个处理器，在所述计算机可读存储介质上存储有指令，当由所述ー个或多个处理器执行所述指令吋，所述指令使得所述ー个或多个处理器执行操作，所述操作包括: 将多个文档存储在计算机可读存储器中，所述多个文档中的每个文档具有对应的访问控制表(ACL)，每个ACL限定被授权访问相应的文档的多个用户； 基于所述多个用户来生成索引，所述索引包括多个分区，每个分区对应于所述多个用户中的用户；以及 针对所述多个文档中的每个文档: 对所述多个用户中的所述用户排序； 基于所述排序来将用户选择为索引用户；以及 将所述文档存储在所述索引的分区中，所述分区对应于所述索引用户。
14.一种计算机实施的方法，所述方法包括: 将多个文档存储在计算机可读存储器中，所述多个文档中的每个文档具有对应的访问控制表(ACL)，每个ACL限定被授权访问相应的文档的多个用户； 基于所述多个用户来生成索引，所述索引包括多个分区，每个分区对应于所述多个用户中的用户；以及 针对所述多个文档中的每个文档: 对所述多个用户中的所述用户进行排序； 基于所述排序来将用户选择为索引用户；以及 将所述文档存储在所述索引的分区中，所述分区对应于所述索引用户。
【文档编号】G06F21/62GK103597474SQ201280021929
【公开日】2014年2月19日 申请日期:2012年3月9日 优先权日:2011年3月11日
【发明者】J·科恩, 庞若鸣, D·赫尔德, D·H·达玛尼亚 申请人:谷歌公司
【专利摘要】一种方法、系统和设备，其包括在计算机存储介质上编码的计算机程序，该计算机存储介质用于将多个文档存储在计算机可读存储器中，多个文档中的每个文档具有对应的访问控制表（ACL），每个ACL限定被授权访问相应的文档的多个用户，基于多个用户而生成索引，索引包括多个分区，每个分区对应于多个用户中的用户，并且针对多个文档中的每个文档：对多个用户中的用户进行排序，基于排序而将用户选择为索引用户，以及将文档存储在索引的分区中，该分区对应于索引用户。
【专利说明】对列入访问控制表的文档进行的高效索引和搜索
[0001]相关联_请的交叉引用
[0002]本专利申请要求于2011年3月11日提交的美国临时专利申请N0.61/452，013的优先权，上述临时专利申请的公开内容明确地通过引用被全文并入于此。
【背景技术】
[0003]本说明书一般涉及对文档的索引和捜索，通过相应的访问控制表(ACL)来调节对上述文档的访问。
[0004]伴随着协作文档和社交网络的发展，越来越多的内容与ACL —起被存储，所述ACL指定可以访问文档的ー组人。在这样的一系列文档上进行捜索呈现了某些挑战。例如，一个用户看到的文档可能与另ー用户看到的文档不同。通过向文档增加ACL令牌，此问题可被解決，每个ACL令牌代表ー个拥有访问对应文档的许可的用户。但是，这种方法的问题是捜索系统必须执行较大命中列表的交集，这在基于磁盘的索引方案中是特别有问题的。一种基于磁盘的索引系统的方法是为对文档拥有许可的每个人写该文档的单独副本。这称为写扇出。虽然这提高了捜索的效率，但是也极大地増加了索引的大小和文档写速率。ー个可替换的解决方案包括将具有ACL令牌的每个文档的单独副本写入对应于每个文档所有者的子索引(分区)，并对来自于处于搜索时间的用户的每个协作者的结果进行合井。这称为读扇入。虽然这提高了文档写的效率，但是当用户有许多协作者时，捜索可能以合并数目很大的结果集的方式而告終。
【发明内容】
[0005]本公开的实施方式涉及方法和系统，其用于对被列入访问控制表的(ACL’d)文档进行索引和捜索。本公开的实施方式提供捜索索引，其可以被用于有效地捜索被列入访问控制表的文档，每个索引被分区成特设组，其中，在ー个或多个特设组中，对每个文档进行索引。索引将文档放入ー组用户和组分区中，而搜索对来自于ー组用户和组分区的结果进行合井。为了更有效的搜索行为，可以在分区之间移动或复制文档。
[0006]一般来说，在本说明书中描述的主题内容的创新的方面可以体现为ー种方法，其包括如下动作:将多个文档存储在计算机可读存储器中，所述多个文档中的每个文档具有对应的访问控制表(ACL)，每个ACL限定被授权访问相应的文档的多个用户，基于所述多个用户而生成索引，所述索引包括多个分区，每个分区对应于所述多个用户中的用户，以及，针对所述多个文档中的每个文档:对所述多个用户中的用户进行排序，基于所述排序而将用户选择为索引用户，以及将所述文档存储在所述索引的分区中，该分区对应于所述索引用户。
[0007]这些和其它实施方式可能每个都优选地包括一个或多个下列特征。例如，所述动作进ー步包括基于所述多个用户而生成索引映射，所述索引映射包括多个映射分区，每个映射分区对应于所述多个用户中的用户，并且包括对所述索引的相应的ー个或多个分区的ー个或多个引用；其中，排序包括:确定多个用户标识符，每个用户标识符对应于所述多个用户中的用户，以及基于所述多个用户标识符而对所述用户进行排序；其中，基于所述多个用户标识符而对所述用户进行排序包括:针对每个用户标识符生成对应的哈希值，以提供多个哈希值，对所述多个哈希值进行排序，以提供排序，以及基于所述排序而选择所述索引用户；其中，所述索引用户对应于所述排序内的最小哈希值；其中，所述索引用户对应于所述排序内的最大哈希值；所述动作进ー步包括:基于所述索引而生成复制索引，所述复制索引包括至少ー个分区，其包括ー个或多个复制文档，所述ー个或多个复制文档中的每一个复制文件是对多个文档中的文档的复制，并且基于所述多个用户而生成索引映射，所述索引映射包括多个映射分区，每个映射分区对应于所述多个用户中的用户，并且包括对所述索引和所述复制索引的相应的ー个或多个分区的ー个或多个引用；所述动作进ー步包括:监控所述多个文档中的文档被更新的频率，并且基于所述频率而确定是否复制所述文档；所述动作进ー步包括:监控对应于特定用户的ー个或多个文档被提供为搜索结果的频率，在对ー个或多个搜索查询的响应中提供所述搜索結果，并且基于所述频率而确定是否复制所述文档；所述动作进ー步包括:确定与所述多个文档中的文档相关联的重索引代价，基于ー个或多个文档大小、更新定时和搜索频率来确定所述重索引代价，将所述重索引代价与代价阈值相比较，当所述重索引代价小于所述阈值吋，复制所述文档；所述动作进ー步包括:接收输入，所述输入对应于所希望的重索引比率，基于所述输入而调整将一个或多个文档复制为所述复制索引的发生比率；所述动作进ー步包括:接收搜索查询，所述搜索查询包括一个或多个关键字和用户身份，基于用户身份而选择所述多个分区中的分区，基于所述一个或多个关键字而搜索与所述分区相关联的一个或多个文档，基于所述搜索而生成搜索結果。
[0008]在下面的附图和说明书中，给出了在本说明书中描述的主题内容的ー个或多个实施方式的详细信息。根据说明书、附图和权利要求书，该主题内容的其他潜在特征、方面和优点会变得明显。
【专利附图】
【附图说明】
[0009]图1描述ー个示例系统，其用于基于访问控制表(ACL)对文档进行高效索引和搜索。
[0010]图2描述ー个示例二分图，其说明用户和文档之间的示例访问关系。
[0011]图3是ー个表,其基于图2描绘出的关系而概述ー个不例ACL。
[0012]图4A是根据本公开的实施方式的示例索引。
[0013]图4B是根据本公开的实施方式的示例分区映射。
[0014]图5是基于文档协作者的包括分区的示例索引。
[0015]图6是基于文档所有者的包括分区的示例索引。
[0016]图7A基于图4A的示例索引描述ー个示例复制索引。
[0017]图7B基于图4A的示例索引和图7A的示例复制索引描述ー个示例分区映射。
[0018]图8是ー个示例进程的流程图，其用于对列入访问控制表的文档进行高效索引和搜索。
[0019]遍及全文，类似的附图标号代表对应的组件。【具体实施方式】
[0020]本公开一般地涉及基于访问控制表(ACL)限制用户对ー个或多个文档的访问。如在此所用的，术语“文档”可涉及任何协作介质，诸如可被多个用户用电子方式查看和/或编辑的电子介质等。示例文档可包括用电子方式创建并存储的协作文档，诸如文字处理文档、电子表格文档、演示文档、以及与ー个或多个社交网络服务相关联的文档等(例如共享的帖子、图片等)。
[0021]正如在此进ー步详细讨论的，本公开的实施方式提供对协作文档的高效索引和搜索。例如，可生成并存储多个文档。所述多个文档的每个文档均可被列入访问控制表(列入ACL的)，以便对每个文档的访问仅仅提供给指定的用户。提供了用于实现捜索索引的技木，所述搜索索引可以被用于有效地捜索被列入访问控制表的文档。该索引被分区成每个用户文档集和特设组(ad-hoc groups)。索引将文档放入ー组用户和组分区,而搜索对来自于ー组用户和组分区的结果进行合井。为了更有效的搜索行为，文档可在分区之间移动或复制。
[0022]图1描述ー个示例系统100，其用于对被列入访问控制表的(列入ACL的)文档进行高效索引和搜索。系统100包括计算设备102A-102F，其每个都可以与在网络106上的一个或多个服务器系统104通信。计算设备102A-102F中的每个计算设备分别包括相关联的用户108A-108F。网络106可包括大型计算机网络，诸如连接任意多的移动计算机、固定计算设备和服务器系统的局域网(LAN)、广域网(WAN)、因特网、蜂窝网络或其组合。服务器系统104包括计算设备110和机器可读仓储库或数据库112。可以理解的是，虽然描述了单个服务器系统104，但是所述单个服务器系统可代表一个或多个服务器系统。
[0023]在示例系统100中，计算设备102A-102C示为台式计算设备，计算设备102D、102F示为膝上型计算设备，并且计算设备102E示为移动计算设备。但是，可以理解的是，计算设备102A-102F可每个都包括任何类型的计算设备，诸如台式计算机、膝上电脑、掌上电脑、个人数字助理(PDA)、蜂窝电话、网络家电、摄影机、智能电话、增强型通用分组无线电业务(EGPRS)移动电话、媒体播放器、导航设备、电子邮件设备、游戏控制台或任何两个或更多个上述数据处理设备或其他数据处理设备的组合。
[0024]计算设备102A-102F使各用户108A-108F能创建、访问、查看和/或编辑诸如协作文档等的文档。文档可用电子方式存储在存储器中。在一些实施方式中，文档可存储在ー个或多个计算设备102A-102F和/或服务器系统104上。在网络106上，计算设备102A-102F和/或服务器系统104可以互相之间进行通信，以使得能访问来自于其它计算设备102A-102F和/或服务器系统104的任何一台的文档。在一些实施方式中，使用计算机应用的用户108A-108F可生成、访问、查看和/或编辑文档，相应的计算设备102A-102F执行所述计算机应用。在一些实施方式中，使用计算机应用的用户108A-108F生成、访问、查看和/或编辑文档，服务器系统104执行所述计算机应用。在一个这样的实施方式中，该计算机应用可作为基于网络的应用程序(网络应用)而被提供；该基于网络的应用使用服务器系统104执行，并且从在网络106上的ー个或多个计算设备102A-102F接收输入并向其提供输出。
[0025]图2描述ー个示例二分图200，其说明用户202和文档204之间的示例访问关系。用户202包括用户A-F。出于说明目的，用户A-F可对应于图1的用户108A-108F。文档204包括文档文档1-文档7。二分图200可基于ー个示例ACL，其限定用户A-F和文档文档1-文档7之间的关系。例如，二分图200规定:用户A可以访问文档文档1、文档2和文档6，用户B和C中的每个用户都可以访问文档文档1-文档3、文档5和文档6，用户D和E可以访问文档文档4和文档7，并且用户F可以访问文档文档7。
[0026]用文档文档I为例，用户A (例如，图1的用户108A)可以通过使用计算设备(例如，图1的计算设备102A)来生成文档文档I。文档文档I可存储在计算设备和/或服务器系统(例如，图1的计算设备102A和/或服务器系统104)中。用户A可以被指定为文档文档I的所有者。在一些实施方式中，文档的所有者是文档的创建者。用户A可以指定对文档文档I进行访问和访问/编辑的权利。例如，用户A可以指定用户B和用户C具有对文档文档I进行访问/编辑的权利。在ACL中可提供此指定信息，该ACL记录了哪些用户202具有对哪些文档204的进行访问/编辑的权利。
[0027]图3是一个表300,其基于图2描绘出的关系而概述一个不例ACL。表300包括文档列302、协作者列304和所有者列306。文档列302和协作者列304提供在如图2所示出的用户202和文档204之间的关系。所有者列306描述每个文档的相应的所有者。按照实例表300，用户A是文档文档I的所有者，用户B是文档文档1-文档3和文档5的所有者，用户C是文档文档6的所有者，用户D是文档文档4的所有者，并且用户E是文档文档7的所有者。用户F未被指定为文档文档1-文档7中的任何ー个的所有者。
[0028]如上所述，文档文档1-文档7中的每个可存储在计算机可读存储器中。可生成索弓丨，以使得对存储的文档进行高效搜索，从而基于搜索查询而识别相关联文档。例如，用户(例如，一个或多个用户108A-108F)可生成搜索查询，而基于该搜索查询可以访问该索引，从而识别可能和该搜索查询相关联的ー个或多个文档。捜索结果可被提供给查询的用户，捜索结果可包括对ー个或多个文档的识别。如果该用户被指定为可以访问所述ー个或多个文档的ー个或多个，该用户可以选择并访问文档。
[0029]本公开的实施方式使得生成索引和/或为现有的索引生成重索引，从而为取决于ACL的文档提供高效索引和捜索。一般来说，诸如图2的二分图200之类的二分图通常不是随机的。与彼此相隔很远的用户相比，已经共享文档和/或以其他方式在二分图中彼此接近的用户更可能分享文档。多个文档经常被同样的或类似的用户组共享。鉴于此，可基于协作者将文档聚类，以便每个用户可以在数目相对较小的聚类中发现所有文档，在该较小的聚类中他们是协作者。根据本公开的实施方式，在用户之中的总排序可以被确定，每个共享文档的用户可以被选择为用于特定文档的索引器。在一些实施方式中，如在此进一歩详细讨论的，基于ー个用户在特定共享文档的其他用户中的排序，该用户被识别为索引器。使用此方法论，数目更小的索引器覆盖ー个用户可以访问的所有文档。多数用户会仅仅需要捜索相对很少的索引器。但是数目较少的用户可能需要捜索数目更大的索引器，如在此进ー步详细讨论的，其由文档的所选定的复制解決。因此，基于在用户之中的总排序来选择用于每个文档的索引用户，这使得数目更小的索引用户可覆盖特定用户可以访问的所有文档。
[0030]根据本公开的实施方式，基于与每个用户相关联的哈希值，对用于特定文档的协作用户进行排序。基干与特定文档的用户相关联的相应的用户标识(用户ID)，可以确定所述哈希值。例如，每个用户标识可作为哈希函数的输入。哈希函数可以作为明确定义的程序或数学函数，其将每个用户标识转换成哈希值。例如，哈希值可作为整数，也可作为数组的索引。在一些实施方式中，最小哈希值可用作用于特定文档的索引。在一些实施方式中，最大哈希值可用作用于特定文档的索引。
[0031]通过非限制性的第一示例，并且出于说明目的，将考虑所述用户A、B、C和文档文档1、文档2、文档6。用户A、B、C中的每个都可以具有相关联的用户ID (例如，IDa、IDb,ID。)。使用哈希函数，可处理每个用户标识，以提供相应的哈希值(例如，HVa、HVb、HV。)。例如，可以处理所述哈希值，以确定最小哈希值和最大哈希值中的ー个。仅仅出于说明目的，HVa可以小于HVb和HV。。因此，HVa可以视为最小哈希值，并且，在用户A是与用户B和C 一起的协作者的情况下，如參考图4A和图4B在下面进ー步详细讨论的，HVa还可以被选择为用于所有文档的索引。例如，即使用户B是文档2的所有者、用户C是文档3的所有者，用户A也可以被选择为用于文档文档1、文档2、文档6的索引。
[0032]通过非限制性的第二示例，并且出于说明目的，HVb可以小于HVC。因此，HVb可以视为在用户B和C之间的最小哈希值，并且，在用户B是与用户C 一起的协作者的情况下，如參考图4A和图4B在下面进ー步详细讨论的，HVb还可以被选择为用于所有文档的索引。例如，用户B可被选择为用于文档文档3、文档5的索引。
[0033]根据本公开的实施方式，图4A是示例索引400。索引400基于图3的表300，并包括分区402-412。分区402-412中的每ー个都作为索引，(分別)对应于(用户A-F中的)一个用户。使用上述第一示例，基于哈希值HVa、HVb, HV。，用户A可以被选择为用于文档文档
1、文档2、文档6的索引。因此，文档文档1、文档2、文档6被存入分区402，所述分区402被用户A索引。使用上述第二示例，基于哈希值HVB、HV。，用户B可被选择为用于文档文档
3、文档5的索引。因此，文档文档3、文档5被存入分区404，所述分区404被用户B索引。因为根据上述第一示例和第二示例，用户C未被选择为用于任何文档的索引，其中用户C是协作者，分区406是空的。
[0034]在图4A中，被用户D索引的分区408包括文档文档4、文档7。在图4A的示例中，用户E、F未被选择为用于任何文档的索引，其中，用户E、F是协作者。因此，所述分区410、412是空的。这表示:对应于用户D的哈希值(HVd)小于分别对应于用户E、F的两个哈希值(HVe^HVf)0
[0035]图4B是根据本公开的实施方式的示例分区映射420。分区映射跟踪共享文档被索引到哪里，还跟踪去哪里搜索每个用户。在一些实施方式中，提供连续的清洁扫描(cleanerscanlet)。清洁扫描删除废弃的搜索扇入边缘和重索引文档，以减少搜索扇入。清洁扫描修整共享边缘，所述共享边缘具有不频繁更新的小文档和频繁的搜索。在一些实施方式中，通过复制文档，清洁扫描完成这种修整。例如，如果当前特定文档仅仅与创建者用户一起保存，并且用户A仅仅不得不搜索创建者用户的索引，该索引是用于那ー个文档的，那么该清洁扫描可从创建者用户的索引复制该文档至用户A的索引，因此减少了ー个(文档)所需要的扇入。一般来说，分区映射使捜索时间操作最小化，并通过避免事务来简化写时间操作。清洁扫描可脱机地操作，以将读者映射同步到文档共享状态。共享映射跟踪哪些用户可以阅读特定文档，还跟踪该文档目前被索引到哪些共享索引位置。读者映射针对每个读者跟踪，他们在哪些共享索引位置处可以发现那名读者共享的所有文档。
[0036]继续參考图4B，分区映射420包括分区422-432，其对应于图4A的分区402-412。分区映射420映射的是，哪些分区是要扇入的。換言之，分区映射420映射的是，索引400的哪些分区402-412会构成对应于每个用户的文档列表。例如，分区422对应于用户A，并且包括对应的扇入指定A。这表示在分区402中保存的文档将被扇入该分区422。作为另一示例，分区424对应于用户B，并且包括对应的扇入指定A、B。这指示在分区402、404中保存的文档将被扇入该分区422。因此，文档文档1、文档2、文档3、文档5、文档6被扇入该分区422，该分区422对应于用户B是在其上的协作者的文档(參看图2和图3)。作为另ー示例，分区426对应于用户C，并且包括对应的扇入指定A、B。这表示在分区402、404中保存的文档将被扇入该分区426。因此，文档文档1、文档2、文档3、文档5、文档6被扇入该分区426，该分区426对应于用户C是在其上的协作者的文档(參看图2和图3)。
[0037]根据图4A和图4B，相对于传统的索引技术，在下面进ー步详细讨论了索引的效率。
[0038]图5是基于文档协作者的包括分区502-512的示例索引500。根据这种可以称作写扇出方法的技术，存储每个文档的单独副本，这是为了那些可以访问该文档的每个用户。使用图2和图3的示例，分区502包括文档文档1、文档2、文档6，用户A是这些文档上的协作者。分区504、506每个都包括文档文档1、文档2、文档3、文档5、文档6，用户B、C是这些文档上的协作者。分区508、510每个都包括文档文档4、文档7，用户D、E是这些文档上的协作者。而分区512包括文档文档7，用户F是这文档上的协作者。
[0039]虽然用图5说明的基于协作者的索引技术提供了高效搜索，但是索引和文档写比率的大小也显著地增大了。例如，图4A的索引400包括7个文档，而图5的索引500包括18个文档。当协作者数目和文档数目增加时，这就更复杂了。
[0040]图6是基于文档所有者的包括分区602-612的示例索引600。根据这种可以称作读扇出方法的技木，将每个文档的单独副本写入对应于每个文档所有者的分区，并且将来自于处于搜索时间的用户的每个协作者的搜索结果合并在一起。虽然此技术对于写是高效的(例如，图6的索引600包括7个文档，而图5的索引500包括18个文档)，但是，当用户有许多协作者时，捜索可能以合并数目很大的结果集的方式而告終。
[0041]在此讨论的基于用户排序的索引的实施方式为大多数用户提供了良好的文档分发。但是，可以理解的是，数目较少的用户可能仍然有大的搜索扇入。为了应对这样的情況，可在多个索引位置处复制文档的小集合，以便限制用于所有用户的检索扇入。換言之，通过将文档的小子集有选择地复制到多个索引，可以改进捜索扇入。在一些实施方式中，使用后台进程，异步地进行复制。在一些实施方式中，基于用户排序的选择，可以进一歩改进搜索扇入。
[0042]在一些实施方式中，捜索扇入可被限制在阈值(例如，10)。在捜索扇入超过该阈值的情况下，可以选择具有最小总文档大小的索引位置，将来自于那些位置的所有文档复制到捜索者自己的索引位置。这样的实施方式可称为简单扇入限制。
[0043]在一些实施方式中，作为上述简单扇入限制的替代方案，可提供动态文档复制。特别地，可采集文档的更新定时，还可估计每个文档的下ー个更新时间。在这种方式下，在复制一个文档是否值得方面可做出更好的决策。例如，如果估计一个文档(例如，在阈值时间内)会被频繁地和/或相对很快地更新，那么可以放弃对那个文档的复制。进ー步，可以采集用户的搜索定时，还可以估计搜索频率。在这种方式下，可以识别频繁的捜索者，并且，与不频繁捜索者相比，可以更积极地減少对应于频繁搜索者的捜索扇入。[0044]在一些实施方式中，提供了重索引代价，其代表关于是否删除通过复制进行的扇入的成本ー效益比率。可基于文档大小、更新定时和搜索频率来确定重索引代价。可以提供动态代价阈值。可以将重索引代价与对应的代价阈值相比较，以确定是否复制文档。例如，如果重索引代价大于代价阈值，就不复制这些文档了。
[0045]在一些实施方式中，提供了控制项，以便调节总的重索引比率。总的重索引比率可对应于被花费在复制上的总带宽。控制项可用于调节上述代价阈值，以满足带宽限制。在这种方式下，可以控制复制流量的冲击，并且，当文档越来越不频繁更新时(例如，夜晚和周末)的非高峰时间可以用于更积极的复制。可以提供捜索扇入阈值，以便约束最坏情况扇入。阈值覆盖了用于大读者的代价阈值，虽然代价还用于对读者的扇入边缘进行排序，以及用于选择要删除的边缘。在一些实施方式中，大读者是扇入很大(例如，大于某个阈值的)的用户。用户的扇入边缘被规定是:为了查看被该用户共享的所有文档而需要被访问的其他用户索引的数目。
[0046]代价阈值代表对文档进行复制的成本ー效益分析。根据文档大小、更新定时和读者的搜索频率来计算该代价。例如，如果ー个文档被频繁地更新，复制它的成本是很高的，这是因为一旦它被再次更新，就将失去该效益。被频繁地捜索的很少更新的小文档可以被低成本、高效益地复制。
[0047]图7A基于图4A的示例索引400描述ー个示例复制索引700。复制索引700包括分区702-712，其对应于示例索引400的分区402-412。示例复制索引700包括对在分区706中的文档1、文档2、文档3、文档5、文档6的复制；在每个图4B的分区映射420中，示例复制索引700对应于对在示例索引400的分区402、404中的文档进行的写扇入。图7B基于图4A的示例索引400和图7A的示例复制索引700而描述一个示例分区映射740。分区映射740包括分区742-752，其对应于索引400的分区402-412。
[0048]可以实现索引400、700，以便基于被用户输入的捜索查询而提供捜索结果。示例搜索查询可包括一个或多个关键字和用户身份。在这种方式下，对应的搜索引擎可处理该搜索查询，以识别所标识的用户可以访问的文档，该文档包括一个或多个搜索查询。分区映射(例如，图7A的分区映射740)可以被用于确定索引的哪些分区对应于所标识的用户(例如，索引400的分区402-412和/或图7A的复制索引700的分区702-712)。可基于ー个或多个关键字捜索在ー个分区内的文档，并且，可以生成捜索结果，该搜索结果包括与所标识的用户相关联的文档，并且该文档包括所述ー个或多个关键字中的一个或多个关键字。
[0049]通过ー个非限制性的示例，搜索查询可包括“用户B”和“关键字”。搜索引擎可以接收该搜索查询作为输入，并且，可以基于用户B而访问图7B的分区映射740。在这种情况下，用户B对应于分区744，其识别在图4A和7B的索引400中的、与用户A和B相关联的、要被扇入的文档。因此，可以基于关键字而搜索包括文档1、文档2、文档3、文档5和文档6的文档集，以便在该文档集内识别包括该关键字的任何文档。可以在搜索结果中提供在该文档集内的包括该关键字的任何文档。
[0050]图8是ー个示例进程800的流程图，其用于对列入访问控制表的文档进行高效索弓I。将多个文档存储在计算机可读存储器中(802)。例如，图1的服务器系统104可以存储多个文档。多个文档中的每个文档都具有对应的ACL，并且每个ACL限定被授权访问相应的文档的多个用户。基于多个用户生成索引(804)。例如，基于多个用户，图1的服务器系统104可以生成索引。索引包括多个分区，每个分区对应于多个用户中的用户(例如，图4A的索引400)。对于多个文档中的每个文档，对多个用户的用户进行排序(806)，基于该排序将ー用户选择为索引用户(808)，并且将文档存储在索引的分区中(810)，该分区对应于该索引用户。例如，图1的服务器系统104可以针对多个文档中的每个文档，对多个用户中的用户进行排序，基于该排序而将用户选择为索引用户，并且将该文档存储在该索引的分区中。基于多个用户而生成索引映射(812)。例如，图1的服务器系统104可以生成索引映射。索引映射包括多个映射分区，每个映射分区对应于多个用户中的用户，并且包括对索引的相应的ー个或多个分区的ー个或多个引用。
[0051]基于索引而生成复制索引(814)。例如，图1的服务器系统104可以基于索引而生成复制索引。复制索引包括至少ー个分区，其包括ー个或多个复制文档，一个或多个复制文档中的每个复制文档都是对多个文档中的文档的复制。基于索引和复制索引生成经修订的索引映射(816)。例如，图4A的服务器系统104可以生成经修订的索引映射(例如，图7B的索引映射740)。
[0052]本公开的实施方式和在此提供的所有功能性操作均可以实现在数字电子电路中，或者实现在包括在本说明书和它们的结构等同物中公开的结构的计算机软件、固件、或硬件中，或者实现在其一个或多个的组合中。本公开的实施方式可被实现为一个或多个计算机程序产品，即在计算机可读介质上编码的计算机程序指令的一个或多个模块，该计算机可读介质或者被数据处理设备执行，或者控制该数据处理设备的操作。计算机可读介质可以是机器可读存储设备、机器可读存储基板、存储设备、实施机器可读传播信号的物质组合物、或其一个或多个的组合。术语“数据处理设备”涵盖用于处理数据的所有设备、装置和机器，举例来说，其包括可编程处理器、计算机、或多台处理器或计算机。除硬件之外，设备可包括创建了用于正在讨论的计算机程序的执行环境的代码，例如，构成了处理器固件、协议栈、数据库管理系统、操作系统、或其一个或多个的组合的代码。
[0053]计算机程序(也称为程序、软件、软件应用、脚本、或代码)可以以包括编译或解释语言的编程语言的任何形式编写，它也可以以包括作为独立程序或作为适合于在计算环境中使用的模块、组件、子程序、或其他単元的任何形式部署。计算机程序不一定对应于在文档系统中的文档。程序可以存储在保存其他程序或数据(例如，存储在标记语言文档中的一个或多个脚本)的文档的一部分中，或者存储在专用于正在讨论的程序的单个文档中，或者存储在多个协作文档(例如，存储ー个或多个模块、子程序、或代码的部分的文档)中。可以在一台计算机上或在多台计算机上部署要被执行的计算机程序，所述计算机位于ー个站点处、或横跨多个站点分布并通过通信网络互连。
[0054]通过执行一个或多个计算机程序的一个或多个可编程处理器，可以执行本公开描述的所述进程和逻辑流程，以便通过操作输入数据和生成输出来执行功能。所述进程和逻辑流程也能被专用逻辑电路，例如FPGA (现场可编程门阵列)或ASIC (专用集成电路)执行，并且设备也能被实现为专用逻辑电路，例如FPGA (现场可编程门阵列)或ASIC (专用集成电路)。
[0055]适合于执行计算机程序的处理器，举例来说包括一般微处理器和专用微处理器，以及任何ー种数字计算机的一个或多个处理器。通常，处理器将从只读存储器或随机访问存储器或两者来接收指令和数据。计算机的元件可包括用于执行指令的处理器和用于存储指令和数据的一个或多个存储器设备。通常，计算机将还包括用于存储数据的例如磁盘、磁光盘、或光盘的ー个或多个大容量存储器，或者可操作地耦合至用于存储数据的例如磁盘、磁光盘、或光盘的ー个或多个大容量存储器，以便从其接收数据或向其转移数据，或者两者兼有。但是，计算机不必具有这样的设备。此外，计算机可以嵌入在另ー个设备中，例如，移动电话、个人数字助理(PDA)、移动音频播放器、全球定位系统接收机中,仅举几例。适合于存储计算机程序指令和数据的计算机可读介质包括各种形式的非易失性存储器、介质和存储设备，举例来说例如包括EPROM、EEPROM和闪存设备的半导体存储设备；例如内置硬盘或可装卸磁盘的磁盘；磁光盘；以及⑶ROM和DVD-ROM盘。可以用专用逻辑电路来补充该处理器和存储器，或者可以在专用逻辑电路内合并该处理器和存储器。
[0056]为了提供与用户进行的交互，本公开的实施方式可在计算机上实现，该计算机具有例如CRT (阴极射线管)或LCD (液晶显示器)监视器的、用于向用户显示信息的显示设备，还具有用户可以由其向计算机提供输入的键盘和指示设备，例如鼠标或轨迹球。其他类型的设备也可用于提供与用户的交互；例如，提供给用户的反馈可以是任何形式的感知反馈，例如可视的反馈、可听的反馈、或触觉反馈；并且可以包括声学、语音或触觉输入的任何形式接收来自于用户的输入。
[0057]虽然本公开包括一些细节，但是这些(细节)不应当被解释为限制本公开或可以要求保护的范围，而是可解释为对本公开的示例实施方式的特征的描述。本公开在单独实施方式的上下文中描述的某些特征也可以在单个实施方式中以组合的形式提供。反过来说，在单个实施方式的上下文中描述的各种特征也可在多个实施方式中单独地或以任何合适的子组合形式提供。此外，虽然特征可以被上文描述为以某些组合的形式作用，并且甚至是这样最初要求保护的，但是，来自于所要求保护的组合的一个或多个特征在某些情况下可以从该组合中剔除，并且所要求保护的组合可以涉及子组合或子组合的变型。
[0058]类似地，虽然在附图中以特定次序描述了操作，但是这不应当被理解成要实现所希望的结果就需要以所示出的特定次序或以顺序次序执行这样的操作，或需要执行所示出的所有操作。在某些情况下，多任务和并行处理可以是有利的。此外，对在上述实施方式中的各种系统组件的分离不应当被理解成:需要在所有实施方式中进行这样的分离，并且应该理解的是:所述描述的程序组件和系统一般可能以单个软件产品的形式或以封装成多个软件产品的形式集成在一起。
[0059]因而，已经描述了本公开的特定实施方式。其他实施方式落在下面的权利要求书范围内。例如，可能以不同的次序执行按权利要求书中详述的动作，并且还能实现所希望的結果。已经描述了很多实施方式。然而，将理解的是，可以无需不脱离本公开的精神和范围而做出各种修改。例如，上面所示出的各种形式的流程，可能以具有重新排序的、増加的、或删除的步骤的方式使用。因此，其他实施方式落在下面的权利要求书的范围内。
【权利要求】
1.一种系统，其包括: 一个或多个处理器；以及 计算机可读存储介质，所述计算机可读存储介质被耦合到所述ー个或多个处理器，在所述计算机可读存储介质上存储有指令，当由所述ー个或多个处理器执行所述指令吋，所述指令使得所述ー个或多个处理器执行操作，所述操作包括: 将多个文档存储在计算机可读存储器中，所述多个文档中的每个文档具有对应的访问控制表(ACL)，每个ACL限定被授权访问相应的文档的多个用户； 基于所述多个用户来生成索引，所述索引包括多个分区，每个分区对应于所述多个用户中的用户；以及 针对所述多个文档中的每个文档: 对所述多个用户中的所述用户排序； 基于所述排序来将用户选择为索引用户；以及 将所述文档存储在所述索引的分区中，所述分区对应于所述索引用户。
2.如权利要求1所述的系统，所述操作还包括基于所述多个用户来生成索引映射，所述索引映射包括多个映射分区，每个映射分区对应于所述多个用户中的用户并且包括对所述索引中的相应的ー个或多个分区的ー个或多个引用。
3.如权利要求1所述的 系统，其中，排序包括: 确定多个用户标识符，每个用户标识符对应于所述多个用户中的用户；以及 基于所述多个用户标识符来对所述用户排序。
4.如权利要求3所述的系统，其中，基于所述多个用户标识符来对所述用户排序包括: 针对每个用户标识符，生成对应的哈希值以提供多个哈希值； 对所述多个哈希值排序以便提供排序；以及 基于所述排序来选择所述索引用户。
5.如权利要求4所述的系统，其中，所述索引用户对应于所述排序内的最小哈希值。
6.如权利要求4所述的系统，其中，所述索引用户对应于所述排序内的最大哈希值。
7.如权利要求1所述的系统，所述操作还包括: 基于所述索引来生成复制索引，所述复制索引包括至少ー个分区，所述至少ー个分区包括ー个或多个复制文档，ー个或多个复制文档中的每个复制文档是对所述多个文档中的文档的复制；以及 基于所述多个用户来生成索引映射，所述索引映射包括多个映射分区，每个映射分区对应于所述多个用户中的用户并且包括对所述索引和所述复制索引的相应的ー个或多个分区的ー个或多个引用。
8.如权利要求7所述的系统，所述操作还包括: 监控所述多个文档中的文档被更新的频率；以及 基于所述频率来确定是否复制所述文档。
9.如权利要求7所述的系统，所述操作还包括: 监控对应于特定用户的ー个或多个文档被作为搜索结果提供的频率，响应于一个或多个搜索查询而提供所述搜索结果；以及 基于所述频率来确定是否复制所述文档。
10.如权利要求7所述的系统，所述操作还包括: 确定与所述多个文档中的文档相关联的重索引代价，基于ー个或多个文档大小、更新定时和搜索频率来确定所述重索引代价； 将所述重索引代价与代价阈值相比较；以及 当所述重索引代价小于所述阈值时，复制所述文档。
11.如权利要求7所述的系统，所述操作还包括: 接收输入，所述输入对应于所希望的重索引比率； 基于所述输入来调整将一个或多个文档复制到所述复制索引的发生比率。
12.如权利要求1所述的系统，所述操作还包括: 接收搜索查询，所述搜索查询包括一个或多个关键字和用户身份； 基于所述用户身份来选择所述多个分区中的分区； 基于所述一个或多个关键字来捜索与所述分区相关联的一个或多个文档；以及 基于所述捜索来生成捜索結果。
13.一种计算机可读存储介质，所述计算机可读存储介质被耦合到一个或多个处理器，在所述计算机可读存储介质上存储有指令，当由所述ー个或多个处理器执行所述指令吋，所述指令使得所述ー个或多个处理器执行操作，所述操作包括: 将多个文档存储在计算机可读存储器中，所述多个文档中的每个文档具有对应的访问控制表(ACL)，每个ACL限定被授权访问相应的文档的多个用户； 基于所述多个用户来生成索引，所述索引包括多个分区，每个分区对应于所述多个用户中的用户；以及 针对所述多个文档中的每个文档: 对所述多个用户中的所述用户排序； 基于所述排序来将用户选择为索引用户；以及 将所述文档存储在所述索引的分区中，所述分区对应于所述索引用户。
14.一种计算机实施的方法，所述方法包括: 将多个文档存储在计算机可读存储器中，所述多个文档中的每个文档具有对应的访问控制表(ACL)，每个ACL限定被授权访问相应的文档的多个用户； 基于所述多个用户来生成索引，所述索引包括多个分区，每个分区对应于所述多个用户中的用户；以及 针对所述多个文档中的每个文档: 对所述多个用户中的所述用户进行排序； 基于所述排序来将用户选择为索引用户；以及 将所述文档存储在所述索引的分区中，所述分区对应于所述索引用户。
【文档编号】G06F21/62GK103597474SQ201280021929
【公开日】2014年2月19日 申请日期:2012年3月9日 优先权日:2011年3月11日
【发明者】J·科恩, 庞若鸣, D·赫尔德, D·H·达玛尼亚 申请人:谷歌公司
最新回复(0)