公开(公告)号：US11196800B2

公开(公告)日：2021-12-07

申请号：US15708793

申请日：2017-09-19

Applicant: Google Inc.

Inventor： Ananda Theertha Suresh ,  Sanjiv Kumar ,  Hugh Brendan McMahan ,  Xinnan Yu

IPC: H04L29/08 ,  G06N7/00 ,  G06F17/16 ,  H03M7/30 ,  H03M7/40 ,  G06F17/12 ,  G06N20/00 ,  G06F17/18 ,  H04L29/06

Abstract: The present disclosure provides systems and methods for communication efficient distributed mean estimation. In particular, aspects of the present disclosure can be implemented by a system in which a number of vectors reside on a number of different clients, and a centralized server device seeks to estimate the mean of such vectors. According to one aspect of the present disclosure, a client computing device can rotate a vector by a random rotation matrix and then subsequently perform probabilistic quantization on the rotated vector. According to another aspect of the present disclosure, subsequent to quantization but prior to transmission, the client computing can encode the quantized vector according to a variable length coding scheme (e.g., by computing variable length codes).

公开(公告)号：US20180089590A1

公开(公告)日：2018-03-29

申请号：US15708793

申请日：2017-09-19

Applicant: Google Inc.

Inventor： Ananda Theertha Suresh ,  Sanjiv Kumar ,  Hugh Brendan McMahan ,  Xinnan Yu

IPC: G06N99/00 ,  G06F17/16 ,  G06N7/00 ,  G06F17/12 ,  H03M7/30 ,  H03M7/40

CPC classification number: G06N20/00 ,  G06F17/12 ,  G06F17/16 ,  G06F17/18 ,  G06N7/005 ,  H03M7/3059 ,  H03M7/3082 ,  H03M7/40 ,  H04L67/42

Abstract: The present disclosure provides systems and methods for communication efficient distributed mean estimation. In particular, aspects of the present disclosure can be implemented by a system in which a number of vectors reside on a number of different clients, and a centralized server device seeks to estimate the mean of such vectors. According to one aspect of the present disclosure, a client computing device can rotate a vector by a random rotation matrix and then subsequently perform probabilistic quantization on the rotated vector. According to another aspect of the present disclosure, subsequent to quantization but prior to transmission, the client computing can encode the quantized vector according to a variable length coding scheme (e.g., by computing variable length codes).

公开(公告)号：US10719509B2

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

申请号：US15290198

申请日：2016-10-11

Applicant: GOOGLE INC.

Inventor： Sanjiv Kumar ,  David Morris Simcha ,  Ananda Theertha Suresh ,  Ruiqi Guo ,  Xinnan Yu ,  Daniel Holtmann-Rice

IPC: G06F16/2453 ,  G06F16/28 ,  G06F16/22 ,  G06F16/2457 ,  G06F17/10 ,  G06K9/62 ,  G06F16/33 ,  G06F16/35

Abstract: Implementations provide an efficient system for calculating inner products between high-dimensionality vectors. An example method includes clustering database items represented as vectors, selecting a cluster center for each cluster, and storing the cluster center as an entry in a first layer codebook. The method also includes, for each database item, calculating a residual based on the cluster center for the cluster the database item is assigned to and projecting the residual into subspaces. The method also includes determining, for each of the subspaces, an entry in a second layer codebook for the subspace, and storing the entry in the first layer codebook and the respective entry in the second layer codebook for each of the subspaces as a quantized vector for the database item. The entry can be used to categorize an item represented by a query vector or to provide database items responsive to a query vector.

公开(公告)号：US20180089587A1

公开(公告)日：2018-03-29

申请号：US15676076

申请日：2017-08-14

Applicant: Google Inc.

Inventor： Ananda Theertha Suresh ,  Sanjiv Kumar ,  Hugh Brendan McMahan ,  Xinnan Yu

IPC: G06N99/00 ,  G06N7/00

CPC classification number: G06N20/00 ,  G06N7/005

Abstract: The present disclosure provides systems and methods for communication efficient distributed mean estimation. In particular, aspects of the present disclosure can be implemented by a system in which a number of vectors reside on a number of different clients, and a centralized server device seeks to estimate the mean of such vectors. According to one aspect of the present disclosure, a client computing device can rotate a vector by a random rotation matrix and then subsequently perform probabilistic quantization on the rotated vector. According to another aspect of the present disclosure, subsequent to quantization but prior to transmission, the client computing can encode the quantized vector according to a variable length coding scheme (e.g., by computing variable length codes).