Similarity search using progressive inner products and bounds

• US 10,489,468 B2
• Filed: 08/22/2017
• Issued: 11/26/2019
• Est. Priority Date: 08/22/2017
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Lytkin, Nikita Igorevych, Douze, Matthys
• Primary Examiner(s): Ortiz Ditren, Belix M
• Application Number:
  US15/683,488
• Publication Number:
  US 20190065594A1
• Time in Patent Office: 826 Days
• Field of Search: None
• CPC Class Codes: G06F 16/24553 of query operations
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9536 Search customisation based on social or collaborative filtering

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.

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.

2. The method of claim 1, wherein accessing a plurality of n object vectors representing a plurality of n objects comprises:

identifying a plurality of n objects matching the query; and

retrieving a plurality of n object vectors corresponding to the plurality of n objects, respectively.

3. The method of claim 1, wherein checking whether to calculate the 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 comprises:

calculating a bound on the estimated inner product of the query vector and the object vector; and

if the calculated bound is less than the minimum inner product associated with the set of top object vectors, terminating the computing of the estimated inner product of the query vector and the object vector.

4. The method of claim 1, wherein:

the query vector comprises d components;

each object vector comprises d components; and

the first partial inner product is an inner product of a query sub-vector comprising components 1 to j of the d components of the query vector and an object sub-vector comprising components 1 to j of the d components of the object vector.

5. The method of claim 4, wherein calculating one or more subsequent partial inner products comprises:

calculating a subsequent partial inner product of the query vector and the object vector, the subsequent partial inner product being an inner product of a query sub-vector comprising components 1 to j′

of the d components of the query vector and an object sub-vector comprising components 1 to j′

of the d components of the object vector, wherein j′

is greater than j;

calculating a bound on a remaining inner product, the remaining inner product being an inner product of a query sub-vector comprising components j′

+1 to d of the d components of the query vector and an object sub-vector comprising components j′

+1 to d of the d components of the object vector;

calculating an updated bound on the estimated inner product based on the subsequent partial inner product and the bound on the remaining inner product; and

if the updated bound is less than the minimum inner product associated with the set of top object vectors, terminating the computing of the estimated inner product of the query vector with the object vector;

else,

setting j equal to j′

; and

calculating an additional subsequent inner product.

6. The method of claim 5, wherein the complete inner product of the object vector and the query vector is computed when j′

is equal to d.

7. The method of claim 1, wherein:

the query is a search query received from the user; and

the plurality of n objects are n search results matching the search query, respectively.

8. The method of claim 1, wherein:

the query is a content-recommendation request associated with the user responsive to the user requesting to access a communication channel of an online social network; and

the plurality of n objects are n recommended content objects receivable by the user through the communication channel, respectively.

9. The method of claim 1, wherein:

the query is an advertising request associated with the user; and

the plurality of n objects are n advertisements receivable by the user at a client system of the user, respectively.

10. The method of claim 1, wherein the plurality of n objects comprise one or more of:

a digital media item;

an application;

an event;

a location;

a page;

an advertisement;

or

an external webpage.

11. The method of claim 1, wherein the inner product, first partial inner product, or each subsequent partial inner product is a dot product of two vectors.

12. The method of claim 1, wherein the inner product, first partial inner product, or each subsequent partial inner product is a norm of a difference vector between two vectors.

13. The method of claim 1, wherein the bound on the estimated inner product h(q,v) is an upper bound calculated by an algorithm comprising:

h(q,v)≤

∥

q∥

∥

v∥

, wherein;

q is the query vector;

v is an object vector; and

∥

q∥

=√

{square root over (q^Tq)}.

14. The method of claim 1, wherein the bound on the estimated inner product h(q,v) is an upper bound calculated by an algorithm comprising:

15. The method of claim 1, wherein accessing a plurality of n object vectors representing a plurality of n objects comprises:

partitioning the plurality of n object vectors into a plurality of disjoint sets, each set being represented by a centroid vector;

determining one or more centroid vectors of the plurality of centroid vectors having an inner product with the query vector satisfying a threshold value; and

identifying the object vectors belonging to the sets represented by the determined centroid vectors as the plurality of n object vectors.

16. The method of claim 15, wherein the object vectors are partitioned based on at least an approximate nearest neighbors approach applying coarse quantization.

17. The method of claim 1, wherein the set of top object vectors is maintained as a heap, each object vector in the set of top object vectors represented in the heap by the complete inner product of the query vector with the object vector.

18. The method of claim 1, wherein calculating one or more subsequent partial inner products comprises:

calculating a complete inner product of the query vector and the object vector if a lower bound on the estimated inner product is greater than the minimum inner product associated with the set of top object vectors, the lower bound being calculated with each subsequent partial inner product.

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.