Similarity search using progressive inner products and bounds
First Claim
1. A method comprising, by one or more computing systems:
- receiving a query associated with a user;
determining a query vector representing the query;
accessing a plurality of n object vectors representing a plurality of n objects, respectively;
calculating, for each of object vectors 1 to k of the plurality of n object vectors, a complete inner product of the query vector and the object vector, wherein object vectors 1 to k are identified as a set of top object vectors;
computing, for each of object vectors k+1 to n of the plurality of n object vectors, an estimated inner product of the query vector and each object vector, wherein the estimated inner product is computed progressively using one or more partial inner products by;
checking whether to calculate a first partial inner product based on a comparison of a bound on the estimated inner product to a minimum inner product associated with the set of top object vectors;
calculating one or more subsequent partial inner products until a complete inner product of the query vector and the object vector is computed, each subsequent partial inner product being calculated if an updated bound on the estimated inner product is greater than the minimum inner product associated with the set of top object vectors, the updated bound being calculated with each subsequent partial inner product; and
substituting, in the set of top object vectors, the object vector associated with the complete inner product for the object vector associated with the minimum inner product if the complete inner product is greater than the minimum inner product associated with the set of top object vectors; and
sending, to the client system of the user, a set of references to the objects corresponding to the set of top object vectors, respectively.
2 Assignments
0 Petitions
Accused Products
Abstract
In one embodiment, a method includes receiving a query and determining a query vector. The method includes accessing multiple object vectors representing multiple objects, respectively. The method includes, for a first set of object vectors identified as top object vectors, calculating an inner product with the query vector. The method includes progressively computing an inner product of the query vector and each remaining object vector and sending, to a user, the objects corresponding to the top object vectors. Progressively computing an inner product includes checking whether to calculate a first partial inner product based on a bound on the inner product and the minimum inner product for a top object vector, calculating subsequent partial inner products until the inner product is complete, and substituting the object vector for a top object vector if the complete inner product is greater than the minimum inner product.
-
Citations
20 Claims
-
1. A method comprising, by one or more computing systems:
-
receiving a query associated with a user; determining a query vector representing the query; accessing a plurality of n object vectors representing a plurality of n objects, respectively; calculating, for each of object vectors 1 to k of the plurality of n object vectors, a complete inner product of the query vector and the object vector, wherein object vectors 1 to k are identified as a set of top object vectors; computing, for each of object vectors k+1 to n of the plurality of n object vectors, an estimated inner product of the query vector and each object vector, wherein the estimated inner product is computed progressively using one or more partial inner products by; checking whether to calculate a first partial inner product based on a comparison of a bound on the estimated inner product to a minimum inner product associated with the set of top object vectors; calculating one or more subsequent partial inner products until a complete inner product of the query vector and the object vector is computed, each subsequent partial inner product being calculated if an updated bound on the estimated inner product is greater than the minimum inner product associated with the set of top object vectors, the updated bound being calculated with each subsequent partial inner product; and substituting, in the set of top object vectors, the object vector associated with the complete inner product for the object vector associated with the minimum inner product if the complete inner product is greater than the minimum inner product associated with the set of top object vectors; and sending, to the client system of the user, a set of references to the objects corresponding to the set of top object vectors, respectively. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:
-
receive a query associated with a user; determine a query vector representing the query; access a plurality of n object vectors representing a plurality of n objects, respectively; calculate, for each of object vectors 1 to k of the plurality of n object vectors, a complete inner product of the query vector and the object vector, wherein object vectors 1 to k are identified as a set of top object vectors; compute, for each of object vectors k+1 to n of the plurality of n object vectors, an estimated inner product of the query vector and each object vector, wherein the estimated inner product is computed progressively using one or more partial inner products by; check whether to calculate a first partial inner product based on a comparison of a bound on the estimated inner product to a minimum inner product associated with the set of top object vectors; calculate one or more subsequent partial inner products until a complete inner product of the query vector and the object vector is computed, each subsequent partial inner product being calculated if an updated bound on the estimated inner product is greater than the minimum inner product associated with the set of top object vectors, the updated bound being calculated with each subsequent partial inner product; and substitute, in the set of top object vectors, the object vector associated with the complete inner product for the object vector associated with the minimum inner product if the complete inner product is greater than the minimum inner product associated with the set of top object vectors; and send, to the client system of the user, a set of references to the objects corresponding to the set of top object vectors, respectively.
-
-
20. A system comprising:
- one or more processors; and
a non-transitory memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to;receive a query associated with a user; determine a query vector representing the query; access a plurality of n object vectors representing a plurality of n objects, respectively; calculate, for each of object vectors 1 to k of the plurality of n object vectors, a complete inner product of the query vector and the object vector, wherein object vectors 1 to k are identified as a set of top object vectors; compute, for each of object vectors k+1 to n of the plurality of n object vectors, an estimated inner product of the query vector and each object vector, wherein the estimated inner product is computed progressively using one or more partial inner products by; check whether to calculate a first partial inner product based on a comparison of a bound on the estimated inner product to a minimum inner product associated with the set of top object vectors; calculate one or more subsequent partial inner products until a complete inner product of the query vector and the object vector is computed, each subsequent partial inner product being calculated if an updated bound on the estimated inner product is greater than the minimum inner product associated with the set of top object vectors, the updated bound being calculated with each subsequent partial inner product; and substitute, in the set of top object vectors, the object vector associated with the complete inner product for the object vector associated with the minimum inner product if the complete inner product is greater than the minimum inner product associated with the set of top object vectors; and send, to the client system of the user, a set of references to the objects corresponding to the set of top object vectors, respectively.
- one or more processors; and
Specification