公开(公告)号：US11354287B2

公开(公告)日：2022-06-07

申请号：US16715620

申请日：2019-12-16

Applicant: GOOGLE LLC

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

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

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.

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