公开(公告)号：US20240119052A1

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

申请号：US18474907

申请日：2023-09-26

Applicant: Google LLC

Inventor： Philip Wenjie Sun ,  Ruiqi Guo ,  Sanjiv Kumar

IPC: G06F16/2453 ,  G06F16/953

CPC classification number: G06F16/24545 ,  G06F16/24549 ,  G06F16/953

Abstract: The disclosure is directed towards automatically tuning quantization-based approximate nearest neighbors (ANN) search methods and systems (e.g., search engines) to perform at the speed-recall pareto frontier. With a desired search cost or recall as input, the embodiments employ Lagrangian-based methods to perform constrained optimization on theoretically-grounded search cost and recall models. The resulting tunings, when paired with the efficient quantization-based ANN implementation of the embodiments, exhibit excellent performance on standard benchmarks while requiring minimal tuning or configuration complexity.

公开(公告)号：US11775589B2

公开(公告)日：2023-10-03

申请号：US17001850

申请日：2020-08-25

Applicant: Google LLC

Inventor： Ruiqi Guo ,  David Simcha ,  Quan Geng ,  Felix Chern ,  Sanjiv Kumar ,  Xiang Wu

IPC: G06F16/20 ,  G06F16/906 ,  G06F16/25 ,  H03M7/30 ,  G06F16/2457

CPC classification number: G06F16/906 ,  G06F16/24578 ,  G06F16/258 ,  H03M7/30

Abstract: Generally, the present disclosure is directed to systems and methods of quantizing a database with respect to a novel loss or quantization error function which applies a weight to an error measurement of quantized elements respectively corresponding to the datapoints in the database. The weight is determined based on the magnitude of an inner product between the respective datapoints and a query compared therewith. In contrast to previous work, embodiments of the proposed loss function are responsive to the expected magnitude of an inner product between the respective datapoints and a query compared therewith and can prioritize error reduction for higher-ranked pairings of the query and the datapoints. Thus, the systems and methods of the present disclosure provide solutions to some of the problems with traditional quantization approaches, which regard all error as equally impactful.

公开(公告)号：US20240054102A1

公开(公告)日：2024-02-15

申请号：US17886860

申请日：2022-08-12

Applicant: Google LLC

Inventor： Filip Pavetic ,  David Simcha ,  Alexander-Teodor Voicu ,  Felix Chern ,  Philip Wenjie Sun ,  Ruiqi Guo ,  Hanna Maria Pasula ,  Martin Ulrich Seiler

IPC: G06F16/13 ,  G06F3/06

CPC classification number: G06F16/13 ,  G06F3/0649 ,  G06F3/0611 ,  G06F3/0685

Abstract: Provided is a scalable and cost-efficient storage architecture for large-scale datasets, such as Internet-scale datasets that include very large numbers (e.g., billions) of data elements. More particularly, provided is a bifurcated storage architecture that includes a first data index stored by a first set of storage media and a second data index stored by a second set of storage media, where the first set of storage media has a lower latency than the second set of storage media.

公开(公告)号：US20200257668A1

公开(公告)日：2020-08-13

申请号：US16715620

申请日：2019-12-16

Applicant: GOOGLE LLC

Inventor： Xiang Wu ,  David Morris Simcha ,  Sanjiv Kumar ,  Ruiqi Guo

IPC: G06F16/22 ,  G06F16/27 ,  G06F16/2458 ,  G06F16/28 ,  G06F17/16 ,  G06F16/248

Abstract: Techniques of indexing a database and processing a query involve decomposing the residual term according to a projection matrix that is based on a given direction v. For example, for each database element of a partition, the residual for that database element is split into a component parallel to a given direction and a component perpendicular to that direction. The parallel component lies in a one-dimensional subspace spanned by the direction and may be efficiently quantized with a scalar quantization. The perpendicular component is quantized using multiscale quantization techniques. The quantized residual components and the center elements of each partition define the indexed database. Upon receipt of a query from a user, the inner products of q with the residual may be computed efficiently using the quantized residual components. From these inner products, the database elements that are most similar to the query are selected and returned to the user.

公开(公告)号：US12235845B2

公开(公告)日：2025-02-25

申请号：US18474907

申请日：2023-09-26

Applicant: Google LLC

Inventor： Philip Wenjie Sun ,  Ruiqi Guo ,  Sanjiv Kumar

IPC: G06F16/245 ,  G06F16/2453 ,  G06F16/95 ,  G06F16/953

Abstract: Example quantization-based approximate nearest neighbors (ANN) search methods and systems (e.g., search engines) are tuned to perform at the speed-recall pareto frontier. With a desired search cost or recall as input, embodiments employ Lagrangian-based methods to perform constrained optimization on theoretically-grounded search cost and recall models. The resulting tunings, when paired with the efficient quantization-based ANN implementation of the embodiments, exhibit excellent performance on standard benchmarks while requiring minimal tuning or configuration complexity.

公开(公告)号：US20240061889A1

公开(公告)日：2024-02-22

申请号：US18456688

申请日：2023-08-28

Applicant: Google LLC

Inventor： Ruiqi Guo ,  David Simcha ,  Quan Geng ,  Felix Chern ,  Sanjiv Kumar ,  Xiang Wu

IPC: G06F16/906 ,  G06F16/2457 ,  G06F16/25 ,  H03M7/30

CPC classification number: G06F16/906 ,  G06F16/24578 ,  G06F16/258 ,  H03M7/30

Abstract: Generally, the present disclosure is directed to systems and methods of quantizing a database with respect to a novel loss or quantization error function which applies a weight to an error measurement of quantized elements respectively corresponding to the datapoints in the database. The weight is determined based on the magnitude of an inner product between the respective datapoints and a query compared therewith. In contrast to previous work, embodiments of the proposed loss function are responsive to the expected magnitude of an inner product between the respective datapoints and a query compared therewith and can prioritize error reduction for higher-ranked pairings of the query and the datapoints. Thus, the systems and methods of the present disclosure provide solutions to some of the problems with traditional quantization approaches, which regard all error as equally impactful.

公开(公告)号：US11874866B2

公开(公告)日：2024-01-16

申请号：US18081376

申请日：2022-12-14

Applicant: Google LLC

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

IPC: G06F16/33 ,  G06F16/31 ,  G06N20/00

CPC classification number: G06F16/3347 ,  G06F16/313 ,  G06F16/319 ,  G06N20/00

Abstract: The present disclosure provides systems and methods that include or otherwise leverage use of a multiscale quantization model that is configured to provide a quantized dataset. In particular, the multiscale quantization model can receive and perform vector quantization of a first dataset. The multiscale quantization model can generate a residual dataset based at least in part on a result of the vector quantization. The multiscale quantization model can apply a rotation matrix to the residual dataset to generate a rotated residual dataset that includes a plurality of rotated residuals. The multiscale quantization model can perform reparameterization of each rotated residual in the rotated residual dataset into a direction component and a scale component. The multiscale quantization model can perform product quantization of the direction components of the plurality of rotated residuals, and perform scalar quantization of the scale components of the plurality of rotated residuals.

公开(公告)号：US11531695B2

公开(公告)日：2022-12-20

申请号：US16638802

申请日：2018-05-14

Applicant: Google LLC

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

IPC: G06F16/33 ,  G06F16/31 ,  G06N20/00

Abstract: The present disclosure provides systems and methods that include or otherwise leverage use of a multiscale quantization model that is configured to provide a quantized dataset. In particular, the multiscale quantization model can receive and perform vector quantization of a first dataset. The multiscale quantization model can generate a residual dataset based at least in part on a result of the vector quantization. The multiscale quantization model can apply a rotation matrix to the residual dataset to generate a rotated residual dataset that includes a plurality of rotated residuals. The multiscale quantization model can perform reparameterization of each rotated residual in the rotated residual dataset into a direction component and a scale component. The multiscale quantization model can perform product quantization of the direction components of the plurality of rotated residuals, and perform scalar quantization of the scale components of the plurality of rotated residuals.

公开(公告)号：US20200183964A1

公开(公告)日：2020-06-11

申请号：US16638802

申请日：2018-05-14

Applicant: Google LLC

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

IPC: G06F16/33 ,  G06N20/00 ,  G06F16/31

Abstract: The present disclosure provides systems and methods that include or otherwise leverage use of a multiscale quantization model that is configured to provide a quantized dataset. In particular, the multiscale quantization model can receive and perform vector quantization of a first dataset. The multiscale quantization model can generate a residual dataset based at least in part on a result of the vector quantization. The multiscale quantization model can apply a rotation matrix to the residual dataset to generate a rotated residual dataset that includes a plurality of rotated residuals. The multiscale quantization model can perform reparameterization of each rotated residual in the rotated residual dataset into a direction component and a scale component. The multiscale quantization model can perform product quantization of the direction components of the plurality of rotated residuals, and perform scalar quantization of the scale components of the plurality of rotated residuals.

公开(公告)号：US20230418797A1

公开(公告)日：2023-12-28

申请号：US18341697

申请日：2023-06-26

Applicant: Google LLC

Inventor： Felix Ren-Chyan Chern ,  Blake Alan Hechtman ,  Andrew Thomas Davis ,  Ruiqi Guo ,  Sanjiv Kumar ,  David Alexander Majnemer

IPC: G06F16/22 ,  G06F16/28

CPC classification number: G06F16/2237 ,  G06F16/285

Abstract: Methods, systems, and apparatus, including computer programs encoded on computer storage media, for performing a kNN computation using a hardware accelerator. One of the methods includes obtaining a set of one or more query vectors; obtaining a set of database vectors; and performing, on a hardware accelerator and for each query vector in the set, a search for the k most similar database vectors to the query vector, comprising: computing, by circuitry of the hardware accelerator and for each query vector, a respective similarity value between the query vector and each database vector; and for each query vector, identifying, by the hardware accelerator and for each bin, (i) an index of the most similar database vector within the bin and (ii) the respective similarity value for the most similar database vector within the bin.