公开(公告)号：US09501506B1

公开(公告)日：2016-11-22

申请号：US14107848

申请日：2013-12-16

Applicant: GOOGLE INC.

Inventor： Marcus Fontoura ,  Daniel N. Meredith ,  Douglas Lee Taylor Rohde ,  Mahesh S. Palekar ,  Asim Shankar ,  Denis Murray Baylor ,  Zigmars Rasscevskis ,  Andras Csomai

IPC: G06F17/30

CPC classification number: G06F17/30631

Abstract: A hybrid-sharded index includes document-sharded posting lists and term-sharded posting lists. Implementations include systems and methods for updating a hybrid-sharded index. For example, a method may include receiving updates to the hybrid-sharded index and generating, at a first leaf node, replacement posting lists and change information for a respective second leaf node. The method may also include dividing the replacement posting lists into portions, a portion having associated change information and being associated with a respective one of the second leaf nodes and sending the portions to respective leaf nodes. At a particular leaf node of the second leaf nodes, the method includes merging a received portion into an updated posing list portion, swapping the updated posting list portion into memory. During the swap, the change information and the updated posting list portion are used to respond to a query with an older version of the hybrid-sharded index.

Abstract translation: 混合分片索引包括文档分片的发布列表和条目分片的发布列表。 实现包括用于更新混合分片索引的系统和方法。 例如，方法可以包括接收对混合分片索引的更新，并且在第一叶节点处生成用于相应的第二叶节点的替换发布列表和改变信息。 该方法还可以包括将替换发布列表划分为部分，具有相关联的改变信息的部分，并且与相应的第二叶节点相关联，并将部分发送到相应的叶节点。 在第二叶节点的特定叶节点处，该方法包括将接收到的部分合并到更新的构图列表部分中，将更新的发布列表部分交换到存储器中。 在交换期间，更改信息和更新的发布列表部分用于响应具有旧版本的混合分片索引的查询。

公开(公告)号：US09483568B1

公开(公告)日：2016-11-01

申请号：US14107851

申请日：2013-12-16

Applicant: GOOGLE INC.

Inventor： Marcus Fontoura ,  Daniel N. Meredith ,  Douglas Lee Taylor Rohde ,  Mahesh S. Palekar ,  Asim Shankar ,  Denis Murray Baylor ,  Zigmars Rasscevskis ,  Andras Csomai

IPC: G06F17/30

CPC classification number: G06F17/30864 ,  G06F17/30631

Abstract: A hybrid-sharded index includes document-sharded posting lists and term-sharded posting lists. Implementations include systems and methods using a distributed hybrid-sharded index. For example, a method may include receiving, at a root node, a query having a first term and a second term and determining, that the first term is term-sharded. The method may also include retrieving a term-sharded posting list for the first term from a first leaf node that stores the term-sharded posting list and determining, at the root node, a second leaf node that stores a document-sharded posting list for the second term. The method may include sending the second term and a sub-set of documents from the term-sharded posting list to the second leaf node, the sub-set being documents assigned to the second leaf node; and generating a search result using a response received from the second leaf node.

Abstract translation: 混合分片索引包括文档分片的发布列表和条目分片的发布列表。 实现包括使用分布式混合分片索引的系统和方法。 例如，一种方法可以包括在根节点处接收具有第一项和第二项的查询，并确定第一项是术语划分的。 所述方法还可以包括从存储所述术语分片的发布列表的第一叶节点检索用于所述第一术语的术语分片的发布列表，以及在所述根节点处确定存储文档分片的发布列表的第二叶节点， 第二学期 该方法可以包括将第二项和一组文档从该术语分片的发布列表发送到第二叶节点，该子集是分配给第二叶节点的文档; 以及使用从所述第二叶节点接收的响应来生成搜索结果。