公开(公告)号：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.

公开(公告)号：US10255323B1

公开(公告)日：2019-04-09

申请号：US14878357

申请日：2015-10-08

Applicant: GOOGLE INC.

Inventor： Ruiqi Guo ,  Sanjiv Kumar ,  Krzysztof Marcin Choromanski ,  David Morris Simcha

IPC: G06F17/30

Abstract: Implementations provide an improved system for efficiently calculating inner products between a query item and a database of items. An example method includes generating a plurality of subspaces from search items in a database, the search items being represented as vectors of elements, a subspace being a block of elements from each search item that occur at the same vector position, generating a codebook for each subspace within soft constraints that are based on example queries, assigning each subspace of each search item an entry in the codebook for the subspace, the assignments for all subspaces of a search item representing a quantized search item, and storing the codebooks and the quantized search items. Generating a codebook for a particular subspace can include clustering the search item subspaces that correspond to the particular subspace, finding a cluster center for each cluster, and storing the cluster center as the codebook entry.

公开(公告)号：US20170091240A1

公开(公告)日：2017-03-30

申请号：US14951909

申请日：2015-11-25

Applicant: Google Inc.

Inventor： Xinnan Yu ,  Sanjiv Kumar ,  Ruiqi Guo

IPC: G06F17/30

CPC classification number: G06F16/2237 ,  G06F16/3331 ,  G06F16/951

Abstract: Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for efficiently performing linear projections. In one aspect, a method includes actions for obtaining a plurality of content items from one or more content sources. Additional actions include, extracting a plurality of features from each of the plurality of content items, generating a feature vector for each of the extracted features in order to create a search space, generating a series of element matrices based upon the generated feature vectors, transforming the series of element matrices into a structured matrix such that the transformation preserves one or more relationships associated with each element matrix of the series of element matrices, receiving a search object, searching the enhanced search space based on the received search object, provided one or more links to a content item that are responsive to the search object.