公开(公告)号：US10720231B1

公开(公告)日：2020-07-21

申请号：US15690844

申请日：2017-08-30

Applicant: Google Inc.

Inventor： David Konerding ,  Jeffrey Adgate Dean ,  Sanjay Ghemawat ,  Jonathan Bingham

IPC: G16B50/00 ,  G06F16/13 ,  G06F16/28 ,  G06F16/174

Abstract: A method includes receiving, by a processing device, a plurality of genome files. Each genome file corresponds to a different sample and defining a genetic sequence. The method also includes generating, by the processing device, a two-dimensional alignment file based on the genome files and a reference sequence. A first dimension of the alignment file corresponds to individual genetic sequences and each of the genetic sequences is aligned with respect to the reference sequence along a second dimension of the alignment file. The method includes separating, by the processing device, the alignment file into a plurality of groups and storing the groups in a non-transitory genome data store. Each group contains segments of the genetic sequences of two or more of the genomic files.

公开(公告)号：US20190065154A1

公开(公告)日：2019-02-28

申请号：US15685048

申请日：2017-08-24

Applicant: Google Inc.

Inventor： Gautham Thambidorai ,  Matthew Rosencrantz ,  Sanjay Ghemawat ,  Srdjan Petrovic ,  Ivan Posva

IPC: G06F9/44 ,  G06F17/30 ,  G06F9/45

Abstract: A programming model provides a method for type inference in programming operations. Information defining one or more attributes of an operation is received, the information specifying a field including a field name and a field type identifier for each of the attributes. Constraints for the operation are determined at least based on the attributes, wherein the constraints restrict at least one of a type of input for the operation or a type of output for the operation. Information defining an input for the operation is received, and it is determined, based on the constraints and the received information defining the input, the type of output for the operation. The type of output is associated with an output for the operation.

公开(公告)号：US09747347B1

公开(公告)日：2017-08-29

申请号：US14476133

申请日：2014-09-03

Applicant: Google Inc.

Inventor： Jeffrey Adgate Dean ,  Sanjay Ghemawat ,  Sachin Jain ,  Boris Mazniker

IPC: G06F17/30 ,  H04L12/18

CPC classification number: G06F17/3053 ,  G06Q10/101 ,  G06Q10/107 ,  G06Q50/01 ,  H04L12/1813

Abstract: A system includes: an engaging post identifier for identifying and retrieving engaging posts; an extended network post identifier for identifying extended posts from an extended network; a combining module for creating a combined list of added posts from the engaging post and the extended posts, the combining module generating one or more ranked posts by ranking the list of added posts by relevance to a user; and a user interface module for providing the one or more ranked posts. The disclosure also includes a method for finding and providing engaging posts that includes determining engaging posts; determining extended posts from an extended social network using a social graph of the user; adding the engaging posts and the extended posts to create a combined list of added posts; ranking the added posts by relevance to a user; and providing one or more of the ranked posts.

公开(公告)号：US09659038B2

公开(公告)日：2017-05-23

申请号：US13909029

申请日：2013-06-03

Applicant: Google Inc.

Inventor： Yasushi Saito ,  Sanjay Ghemawat ,  Sebastian Kanthak ,  Christopher Cunningham Frost

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

CPC classification number: G06F17/30289 ,  G06F17/30067 ,  G06F17/30575

Abstract: A computer system issues a batch read operation to a tablet in a first replication group in a distributed database and obtains a most recent version of data items in the tablet that have a timestamp no great than a snapshot timestamp T. For each data item in the one tablet, the computer system determines whether the data item has a move-in timestamp less than or equal to the snapshot timestamp T, which is less than a move-out timestamp, and whether the data item has a creation timestamp less than the snapshot timestamp T, which is less than or equal to a deletion timestamp. If the determination is true, the computer system determines whether the move-out timestamp has an actual associated value and, if so, the computer system determines a second tablet in a second replication group in the database that includes the data item and issues the snapshot read operation to the second table in the second replication group to obtain a most-recent version of the data item that has a timestamp no greater than the snapshot timestamp T; otherwise, the computer system issues the snapshot read to the one tablet to obtain a most recent version of the data item that has a timestamp no greater than the snapshot timestamp T.

公开(公告)号：US09195611B2

公开(公告)日：2015-11-24

申请号：US13910059

申请日：2013-06-04

Applicant: Google Inc.

Inventor： Jeffrey Adgate Dean ,  Sanjay Ghemawat ,  Andrew Fikes

IPC: G06F12/00 ,  G06F12/12 ,  G06F17/30

CPC classification number: G06F12/121 ,  G06F17/30345 ,  G06F17/30368

Abstract: A method of storing data is disclosed. The method is performed on a data storage server having one or more processors and memory storing one or more programs for execution by the one or more processors. The data storage server receives a first and second data request, the requests including a first and second range of one or more keys and an associated first and second value respectively. The data storage server identifies one or more overlap points associated with the first range and the second range. For each of the overlap points, the data storage server then creates data items including ranges of keys, the ranges of each data item including one or more keys that are either: (a) the keys between a terminal key of the first or second range and the overlap point, or (b) the keys between two adjacent overlap points.

Abstract translation: 公开了存储数据的方法。 该方法在具有一个或多个处理器的数据存储服务器和存储一个或多个程序的存储器中执行，以供一个或多个处理器执行。 数据存储服务器接收第一和第二数据请求，所述请求分别包括一个或多个密钥的第一和第二范围以及关联的第一和第二值。 数据存储服务器识别与第一范围和第二范围相关联的一个或多个重叠点。 对于每个重叠点，数据存储服务器然后创建包括密钥范围的数据项，每个数据项的范围包括一个或多个密钥，它们是：（a）第一或第二范围的终端密钥之间的密钥 和重叠点，或（b）两个相邻重叠点之间的键。

公开(公告)号：US20130346540A1

公开(公告)日：2013-12-26

申请号：US13899495

申请日：2013-05-21

Applicant: Google Inc.

Inventor： Jeffrey Adgate Dean ,  Sanjay Ghemawat ,  Yasushi Saito ,  Andrew Fikes ,  Christopher Jorgen Taylor ,  Sean Quinlan ,  Michal Piotr Szymaniak ,  Sebastian Kanthak ,  Wilson Cheng-Yi Hsieh ,  Alexander Lloyd ,  Michael James Boyer Epstein

IPC: H04L29/08

CPC classification number: H04L67/1097

Abstract: A system, computer-readable storage medium storing at least one program, and a computer-implemented method for identifying a storage group in a distributed storage system into which data is to be stored is presented. A data structure including information relating to storage groups in a distributed storage system is maintained, where a respective entry in the data structure for a respective storage group includes placement metrics for the respective storage group. A request to identify a storage group into which data is to be stored is received from a computer system. The data structure is used to determine an identifier for a storage group whose placement metrics satisfy a selection criterion. The identifier for the storage group whose placement metrics satisfy the selection criterion is returned to the computer system.

Abstract translation: 呈现存储至少一个程序的系统，计算机可读存储介质和用于识别要存储数据的分布式存储系统中的存储组的计算机实现的方法。 维护包括与分布式存储系统中的存储组有关的信息的数据结构，其中相应存储组的数据结构中的相应条目包括各个存储组的布局度量。 从计算机系统接收到识别要存储数据的存储组的请求。 数据结构用于确定其布局度量满足选择标准的存储组的标识符。 其位置指标满足选择标准的存储组的标识符返回给计算机系统。

公开(公告)号：US20130339301A1

公开(公告)日：2013-12-19

申请号：US13909029

申请日：2013-06-03

Applicant: Google Inc.

Inventor： Yasushi Saito ,  Sanjay Ghemawat ,  Sebastian Kanthak ,  Christopher Cunningham Frost

IPC: G06F17/30

CPC classification number: G06F17/30289 ,  G06F17/30067 ,  G06F17/30575

Abstract: A computer system issues a batch read operation to a tablet in a first replication group in a distributed database and obtains a most recent version of data items in the tablet that have a timestamp no great than a snapshot timestamp T. For each data item in the one tablet, the computer system determines whether the data item has a move-in timestamp less than or equal to the snapshot timestamp T, which is less than a move-out timestamp, and whether the data item has a creation timestamp less than the snapshot timestamp T, which is less than or equal to a deletion timestamp. If the determination is true, the computer system determines whether the move-out timestamp has an actual associated value and, if so, the computer system determines a second tablet in a second replication group in the database that includes the data item and issues the snapshot read operation to the second table in the second replication group to obtain a most-recent version of the data item that has a timestamp no greater than the snapshot timestamp T; otherwise, the computer system issues the snapshot read to the one tablet to obtain a most recent version of the data item that has a timestamp no greater than the snapshot timestamp T.

Abstract translation: 计算机系统向分布式数据库中的第一复制组中的平板电脑发出批量读取操作，并获得平板电脑中具有不大于快照时间戳T的时间戳的最新版本的数据项。对于 一个平板电脑，计算机系统确定数据项是否具有小于或等于快照时间戳T的移入时间戳，小于移出时间戳，以及数据项是否具有小于快照的创建时间戳 时间戳T，小于或等于删除时间戳。 如果确定为真，则计算机系统确定移出时间戳是否具有实际相关联的值，如果是，则计算机系统确定数据库中包括数据项的第二复制组中的第二个平板电脑并发布快照 读操作到第二复制组中的第二表以获得具有不大于快照时间戳T的时间戳的数据项的最新版本; 否则，计算机系统将快照读取发送到一个平板电脑以获得具有不大于快照时间戳T的时间戳的数据项的最新版本。

公开(公告)号：US10599482B2

公开(公告)日：2020-03-24

申请号：US15685055

申请日：2017-08-24

Applicant: Google Inc.

Inventor： Gautham Thambidorai ,  Matthew Rosencrantz ,  Sanjay Ghemawat ,  Srdjan Petrovic ,  Ivan Posva

IPC: G06F9/44 ,  G06F9/50 ,  G06F8/41 ,  G06F17/50

Abstract: A programming model generates a graph for a program, the graph including a plurality of nodes and edges, wherein each node of the graph represents an operation and edges between the nodes represent streams of data input to and output from the operations represented by the nodes. The model determines where in a distributed architecture to execute the operations represented by the nodes. Such determining may include determining which nodes have location restrictions, assigning locations to each node having a location restriction based on the restriction, and partitioning the graph into a plurality of subgraphs, the partitioning including assigning locations to nodes without location restrictions in accordance with a first set of constraints, wherein each node within a particular subgraph is assigned to the same location. Each of the subgraphs is executed at its assigned location in a respective single thread.

公开(公告)号：US20170206232A1

公开(公告)日：2017-07-20

申请号：US15479228

申请日：2017-04-04

Applicant: Google Inc.

Inventor： Jeffrey Dean ,  Sanjay Ghemawat

IPC: G06F17/30

CPC classification number: G06F17/30339 ,  G06F9/4881 ,  G06F9/54 ,  G06F17/30377 ,  G06F17/30445

Abstract: A method performs large-scale data processing in a distributed and parallel processing environment. The method defines application-independent map and reduce operations, each invoking one or more library functions that automatically handle data partitioning, parallelization of computations, and fault tolerance. A user specifies a map operation, which calls one or more of the application-independent map operators to perform data read and write operations. A user also specifies a reduce operation, which calls one or more of the application-independent reduce operators to perform data read and write operations. The method executes application-independent map worker processes. Each map worker process executes the user-specified map operation to read designated portions of input files and store intermediate data values in intermediate data structures. The method also executes application-independent reduce worker processes. Each reduce worker process executes the user-specified reduce operation to read intermediate data values from the intermediate data structures and produce final output data.

公开(公告)号：US09621651B1

公开(公告)日：2017-04-11

申请号：US14723011

申请日：2015-05-27

Applicant: Google Inc.

Inventor： Sanjay Ghemawat ,  Howard Gobioff ,  Shun-Tak Leung

IPC: G06F17/30 ,  H04L29/08

CPC classification number: H04L67/1095 ,  G06F17/30174 ,  G06F17/30215

Abstract: A system facilitates the distribution and redistribution of chunks of data among multiple servers. The system may identify servers to store a replica of the data based on at least one of utilization of the servers, prior data distribution involving the servers, and failure correlation properties associated with the servers, and place the replicas of the data at the identified servers. The system may also monitor total numbers of replicas of the chunks available in the system, identify chunks that have a total number of replicas below one or more chunk thresholds, assign priorities to the identified chunks, and re-replicate the identified chunks based substantially on the assigned priorities. The system may further monitor utilization of the servers, determine whether to redistribute any of the replicas, select one or more of the replicas to redistribute based on the utilization of the servers, select one or more of the servers to which to move the one or more replicas, and move the one or more replicas to the selected one or more servers.