Clustering data describing interactions performed after receipt of a query based on similarity between embeddings for different queries

Patent metadata

Field	Value
Publication number	US-12367220-B2
Application number	US-202418671761-A
Country	US
Kind code	B2
Filing date	May 22, 2024
Priority date	Feb 8, 2022
Publication date	Jul 22, 2025
Grant date	Jul 22, 2025

Abstract

An online system leverages stored interactions with items made by users after the online system received queries to determine display of items satisfying the query. For example, the online system trains a model to predict a likelihood of a user performing an interaction with an item displayed after a query was received. As different items receive different amounts of interaction from users, limited historical interaction with certain items may limit accuracy of the model. The online system generates embeddings for previously received queries and uses measures of similarity between embeddings for queries to generate clusters of queries. Previous interactions with queries in a cluster are combined, with the combined data being used for determining display of items in response to a query.

First claim

What is claimed is:

1. A method, performed at a system comprising at least one processor and memory, comprising:
receiving a query from a user, the query comprising one or more terms;
accessing a plurality of embeddings, each embedding representing a stored query in a latent space, wherein each stored query is associated with interaction information that describes one or more interactions performed by one or more users with items displayed after the system received the corresponding query, wherein accessing the plurality of embeddings comprises:
storing, in a data storage, a plurality of queries each including one or more terms;
recording interaction information for each stored query of the plurality of queries;
generating an embedding for each stored query of the plurality of queries; and
storing, in the data storage, the generated embedding with the interaction information for each stored query of the plurality of queries;

generating an embedding for the received query based on the one or more terms;
identifying, from the data storage, one or more of the stored queries having embeddings with at least a threshold measure of similarity to the generated embedding for the received query;
generating a cluster including the received query and the one or more of the stored queries;
combining the interaction information for each of the stored queries included in the cluster;
generating one or more metrics, each metric describing the combined interaction information with an item displayed after receiving a stored query included in the cluster; and
displaying a result for the received query comprising: modifying positions of one or more items in the result displayed in a user interface based on the one or more metrics of the combined interaction information.

2. The method of claim 1 , further comprising:
selecting a representative query for the cluster from the queries included in the cluster; and
storing the representative query in association with a cluster identifier and with the combined interaction information.

3. The method of claim 1 , wherein generating the cluster comprises:
generating a cluster embedding for the cluster from embeddings for the received query and each stored query included in the cluster; and
storing the cluster embedding in association with a cluster identifier.

4. The method of claim 3 , wherein generating the cluster embedding comprises:
calculating a centroid of the embeddings for received query and the stored queries included in the cluster.

5. The method of claim 1 , wherein generating the cluster comprises:
generating the cluster based on distances between the embedding for the received query and embeddings for the stored queries in the latent space.

6. The method of claim 5 , wherein generating the cluster based on distances between the embedding for the received query and embeddings for the stored queries in the latent space comprises:
selecting additional stored queries for the cluster by applying one or more approximate nearest neighbor methods to the embedding for the received query and embeddings for additional stored queries.

7. The method of claim 1 , wherein each metric is based on a number of occurrences of a specific interaction with the item when displayed in results for each query included in the cluster and a number of times the item was displayed in results for each query included in the cluster.

8. A computer program product comprising a non-transitory computer readable storage medium having instructions encoded thereon that, when executed by a processor, cause the processor to:
receive a query from a user, the query comprising one or more terms;
access a plurality of embeddings, each embedding representing a stored query in a latent space, wherein each stored query is associated with interaction information that describes one or more interactions performed by one or more users with items displayed after receiving the corresponding query, wherein the instructions to access the plurality of embeddings cause the processor to:
store, in a data storage, a plurality of queries each including one or more terms;
record interaction information for each stored query of the plurality of queries;
generate an embedding for each stored query of the plurality of queries; and
store, in the data storage, the generated embedding with the interaction information for each stored query of the plurality of queries;

generate an embedding for the received query based on the one or more terms;
identify, from the data storage, one or more of the stored queries having embeddings with at least a threshold measure of similarity to the generated embedding for the received query;
generate a cluster including the received query and the one or more of the stored queries;
combine the interaction information for each of the stored queries included in the cluster;
generate one or more metrics, each metric describing the combined interaction information with an item displayed after receiving a stored query included in the cluster; and
display a result for the received query comprising: modifying positions of one or more items in the result displayed in a user interface based on the one or more metrics of the combined interaction information.

9. The computer program product of claim 8 , wherein the non-transitory computer readable storage medium further has instructions encoded thereon that, when executed by the processor, cause the processor to:
select a representative query for the cluster from the queries included in the cluster; and
store the representative query in association with a cluster identifier and with the combined interaction information.

10. The computer program product of claim 8 , wherein the instructions to generate the cluster, when executed by the processor, cause the processor to:
generate a cluster embedding for the cluster from embeddings for the received query and each stored query included in the cluster; and
store the cluster embedding in association with a cluster identifier.

11. The computer program product of claim 10 , wherein the instructions to generate the cluster, when executed by the processor, cause the processor to:
calculate a centroid of the embeddings for received query and the stored queries included in the cluster.

12. The computer program product of claim 8 , wherein the instructions to generate the cluster, when executed by the processor, cause the processor to:
generate the cluster based on distances between the embedding for the received query and embeddings for the stored queries in a latent space.

13. The computer program product of claim 12 , wherein the instructions to generate the cluster based on distances between the embedding for the received query and embeddings for the stored queries in a latent space, when executed by the processor, cause the processor to:
select additional stored queries for the cluster by applying one or more approximate nearest neighbor methods to the embedding for the received query and embeddings for additional stored queries.

14. The computer program product of claim 8 , wherein each metric is based on a number of occurrences of a specific interaction with the item when displayed in results for each query included in the cluster and a number of times the item was displayed in results for each query included in the cluster.

15. A system comprising:
a processor; and
a non-transitory computer readable storage medium having instructions encoded thereon that, when executed by the processor, cause the system to:
receive a query from a user, the query comprising one or more terms

Assignees

• Maplebear Inc

Inventors

• Na Taesik
• Tenneti Tejaswi
• Wang Haixun
• Xiao Xiao

Classifications

• G06F18/24147

  Distances to closest patterns, e.g. nearest neighbour classification · CPC title

• G06F16/24575

  using context · CPC title

• G06F16/248

  Presentation of query results · CPC title

• G06F16/24573

  using data annotations, e.g. user-defined metadata · CPC title

• G06Q10/08

  Logistics, e.g. warehousing, loading or distribution; Inventory or stock management · CPC title