公开(公告)号：US10102268B1

公开(公告)日：2018-10-16

申请号：US15390906

申请日：2016-12-27

Applicant: Google Inc.

Inventor： Muthian Sivathanu ,  Puneet Garg ,  Rajesh S R

IPC: G06F7/00 ,  G06F17/30

Abstract: A system for efficiently responding to proximity queries may include a memory storing an index for searching a graph-based data store, the index including posting lists for one or more proximity ranges compatible with a space. A posting list can include one or more entities of a type compatible with the space, each entity having a location within the space, the location being a basic unit in a location hierarchy for the space and, for each entity, at least one node in the location hierarchy that falls within the proximity range of the posting list with reference to the location of the entity. The system may also include a memory storing instructions that cause the system to use the index to respond to a query that includes a query proximity range for the space. The space can be a geographic space or a time space.

公开(公告)号：US10073874B1

公开(公告)日：2018-09-11

申请号：US14086536

申请日：2013-11-21

Applicant: GOOGLE INC.

Inventor： Muthian Sivathanu ,  Saurabh Goyal ,  Rajiv Mathews

IPC: G06F7/00 ,  G06F17/00 ,  G06F17/30 ,  G06F11/14

CPC classification number: G06F16/2228 ,  G06F11/1402 ,  G06F16/31

Abstract: Implementations provide an indexing system with an instant failover that uses a moving snapshot window. For example, a method may include receiving, by a processor, a query and determining that a main query processing engine is not responding. The method may further include generating a search result for the query using a secondary query processing engine that applies at least one snapshot record to a portion of a posting list, the snapshot record including the portion of the posting list as it appeared before a modification, and the modification occurring within a predetermined time before receiving the query. The portion is a fixed size smaller than the posting list. Applying the snapshot record can include overlaying the portion of the posting list with the snapshot record beginning at an offset specified by the snapshot record. The main query processing engine generates a search result without applying snapshot records.

公开(公告)号：US20160352743A1

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

申请号：US14723760

申请日：2015-05-28

Applicant: Google Inc.

Inventor： Brent VerWeyst ,  Martin James Cochran ,  Muthian Sivathanu

IPC: H04L29/06 ,  G06F21/62 ,  G06F17/30

CPC classification number: H04L63/101 ,  G06F17/30289 ,  G06F21/604 ,  G06F21/6218 ,  G06F21/6227 ,  G06F2221/2141

Abstract: Methods, systems, and apparatus, including computer programs encoded on a computer storage medium for access control for enterprise information. In one aspect, a method includes receiving resources of an enterprise, each resource having a respective access control list specifying access privileges to the resource for one or more members, and the resources including entities related to the enterprise and relationships; identifying entity facts of the entities from the resources; determining, for each entity fact, an entity fact access control list; storing data describing the entities, entity facts and the respective entity fact access control lists, wherein each entity fact is associated with its corresponding entity fact access control list; and providing, to each of the members of the enterprise, access privileges to the data describing the entities and the entity facts according to the respective entity fact access control lists.

Abstract translation: 方法，系统和装置，包括在计算机存储介质上编码的用于企业信息的访问控制的计算机程序。 一方面，一种方法包括接收企业的资源，每个资源具有指定对一个或多个成员资源的访问权限的相应访问控制列表，以及包括与企业和关系相关的实体的资源; 从资源中确定实体的实体事实; 为每个实体事实确定实体访问控制列表; 存储描述实体的数据，实体事实和相应的实体事实访问控制列表，其中每个实体事实与其相应的实体事实访问控制列表相关联; 并且根据相应的实体访问控制列表向企业的每个成员提供对描述实体和实体事实的数据的访问权限。

公开(公告)号：US10474650B1

公开(公告)日：2019-11-12

申请号：US14086527

申请日：2013-11-21

Applicant: GOOGLE INC.

Inventor： Muthian Sivathanu ,  Saurabh Goyal ,  Rajiv Mathews

IPC: G06F16/22 ,  G06F16/951 ,  G06F16/953

Abstract: Implementations provide an indexing system with near-instant updates to an inverted index while maintaining techniques for query optimization. The system may provision empty positions in posting lists to enable in-place updating, without having to rebuild the posting list or append updates to the end of the posting list. For example, a system comprises at least one processor and memory storing an index that includes at least one posting list that maps a term to a set of the documents. The posting list includes an ordered list of documents and has a plurality of open positions within the ordered list. The memory also stores instructions that, when executed by the at least one processor, cause the system to locate an open position of the plurality of open positions for a new document and to insert the new document into the at least one posting list using the open position.

公开(公告)号：US09576007B1

公开(公告)日：2017-02-21

申请号：US14101878

申请日：2013-12-10

Applicant: GOOGLE INC.

Inventor： Muthian Sivathanu ,  Puneet Garg ,  Rajesh S R

IPC: G06F7/00 ,  G06F17/30

CPC classification number: G06F17/30321 ,  G06F17/3053

Abstract: A search index for searching a graph-based data store can include triple entries, each triple entry having a posting list value, at least one intersection identifier associated with the posting list value, and at least one result identifier associated with the intersection identifier. The index may also include search entries having a posting list value that corresponds to a text search aid. The search index may also include pre-computed path entries, such as chain path entries and converge path entries. The index may also include bucket posting lists representing ranges of object values for a particular predicate and proximity posting lists that include one or more entities and the areas of a location hierarchy with locations within the proximity of the entity. Queries for the data graph may have at least two stages, each stage being associated with a posting list from a graph index.

Abstract translation: 用于搜索基于图表的数据存储的搜索索引可以包括三个条目，每个三重条目具有发布列表值，至少一个与发布列表值相关联的交集标识符以及与该交集标识符相关联的至少一个结果标识符。 索引还可以包括具有对应于文本搜索辅助的发布列表值的搜索条目。 搜索索引还可以包括预先计算的路径条目，例如链路路径条目和收敛路径条目。 该索引还可以包括表示包括一个或多个实体的特定谓词和邻近发布列表的对象值的范围的桶发布列表以及具有位于该实体附近的位置的位置层次结构的区域。 数据图表的查询可能至少有两个阶段，每个阶段都与图表索引的发布列表相关联。