# US 11,310,539 B1 · Grouping a first set of video items to efficiently match against a second set of video items using embedding similarity

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,310,539 B1
- Document ID: US11310539B1
- Status: Granted
- Kind: B1
- Application number: 17/189,029
- Filed: 2021-03-01
- Granted: 2022-04-19
- Earliest claimed: 2021-03-01
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Young Jin Yun; Sneha Chaudhari; Mahesh Subhash Joshi; Fares Hedayati; Gungor Polatkan; Gautam Borooah
- Web page: https://patentgrep.com/patent/US11310539B1

## CPC

- H04N 21/23418: {involving operations for analysing video streams, e.g. detecting features or characteristics (television picture signal circuitry for scene change detection H04N5/147; filtering for image enhancement G06T5/00; methods or arrangements for recognising scenes G06V20/00; arrangements characterised by components specially adapted for monitoring, identification or recognition of video in broadcast systems H04H60/59)}
- G06F 18/23213: with fixed number of clusters, e.g. K-means clustering
- G06V 20/41: {Higher-level, semantic clustering, classification or understanding of video scenes, e.g. detection, labelling or Markovian modelling of sport events or news items (segmenting video sequences G06V20/49)}
- G06V 20/48: {Matching video sequences}
- H04N 21/251: {Learning process for intelligent management, e.g. learning user preferences for recommending movies (details of learning user preferences for the retrieval of video data in a video database G06F16/739; computer systems using learning methods G06N3/08)}
- H04N 21/4668: {for recommending content, e.g. movies}
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

Techniques for efficiently matching two sets of video items are provided. In on technique, an embedding is generated for each video item in each set. For the first set of video items, multiple groups are generated. The first set of video items may have a relatively little amount of metadata information for them. Each video item in the first set is assigned to one of the groups. Then, for each video item in the second set, one of the groups is selected based on embedding similarity. For each video item in the selected group, an embedding similarity is determined between that video item in the selected group and the video item in the second set. If the embedding similarity is above a certain threshold, then an association is generated for that pair of video items.

## Claims

### Claim 1

A method comprising:
identifying a first plurality of video items;
identifying metadata of each video item in the first plurality of video items;
by inserting the metadata of each video item into a machine-learned embedding generator, generating an embedding for each video item in the first plurality of video items;
generating a plurality of groups of the first plurality of video items, wherein each video item in the first plurality of video items is assigned to a group in the plurality of groups based on the embedding generated for said each video item;
identifying a second plurality of video items;
generating an embedding for each video item in the second plurality of video items;
for each particular video item in the second plurality of video items:
for each group of the plurality of groups;
comparing the embedding of said each particular video item with an embedding associated with said each group to generate a group score;
adding the group score to a set of group scores;
identifying a particular group, in the plurality of groups, that is associated with the highest group score in the set of group scores;
for each video item in the particular group:
comparing the embedding of said each particular video item with an embedding associated with said each video item in the particular group to generate a video pair score;
adding the video pair score to a set of video pair scores;
based on the set of video pair scores, storing a mapping that associates said each particular video item with one or more video items in the particular group;
adding the mapping to a set of mappings;
wherein the method is performed by one or more computing devices.

### Claim 2 (depends on 1)

The method of claim 1, wherein generating the plurality of groups comprises using a k-means clustering technique to generate the plurality of groups.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
identifying, for a particular user, a subset of the second plurality of video items;
for each video item in the subset:
identifying said each video item in a particular mapping in the set of mappings;
based on the particular mapping, identifying one or more video items in the first plurality of video items;
adding the one or more video items to a set of video items;
causing first data about each video item in the set of video items to be presented on a computing device of the particular user.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
causing second data about each video item in the subset to be presented on the computing device of the particular user.

### Claim 5 (depends on 3)

The method of claim 3, wherein identifying, for the particular user, the subset of the second plurality of video items, comprises:
identifying a first plurality of attribute values of the particular user;
for each video item in a second subset of the second plurality of video items:
identifying a second plurality of attribute values of said each video item;
generating a plurality of feature values based on the first plurality of attribute values and the second plurality of attribute values;
inputting the plurality of feature values into a machine-learned model to generate a user-item pair score;
adding the user-item pair score to a set of user-item pair scores;
selecting the subset from the second subset based on the set of user-item pair scores.

### Claim 6 (depends on 1)

The method of claim 1, wherein the embedding generated for each video item in the first plurality of video items is a first embedding, wherein the plurality of groups is a first plurality of groups, the method further comprising:
generating a second embedding for each video item in the first plurality of video items;
generating a second plurality of groups of the first plurality of video items, wherein each video item in the second plurality of video items is assigned to a group in the second plurality of groups based on the second embedding generated for said each video item.

### Claim 7 (depends on 6)

The method of claim 6, wherein the first embedding of each video item in the first plurality of video items is a title of said each video item and the second embedding of each video item in the first plurality of video items is a description of said each video item.

### Claim 8 (depends on 1)

The method of claim 1, wherein the plurality of groups is a first plurality of groups, further comprising:
generating a second plurality of groups of the first plurality of video items, wherein each video item in the second plurality of video items is assigned to a group in the second plurality of groups based on the embedding generated for said each video item;
identifying the second plurality of video items;
for each particular video item in the second plurality of video items:
for each particular group of the second plurality of groups;
comparing the embedding of said each particular video item with an embedding associated with said each particular group to generate a second group score;
adding the second group score to a second set of group scores;
identifying a second particular group, in the second plurality of groups, that is associated with the highest group score in the second set of group scores;
for each video item in the second particular group:
comparing the embedding of said each particular video item with an embedding associated with said each video item in the second particular group to generate a second video pair score;
adding the second video pair score to a second set of video pair scores;
based on the second set of video pair scores, storing a second mapping that associates said each particular video item with one or more video items in the second particular group;
adding the second mapping to a second set of mappings.

### Claim 9 (depends on 1)

The method of claim 1, wherein:
identifying the particular group that is associated with the highest group score in the set of group scores comprises identifying two or more groups, in the plurality of groups, that are associated with the highest group scores in the set of group scores;
the particular group is a first group in the two or more groups that includes the first group and a second group;
the method further comprising:
for each video item in the second group:
comparing the embedding of said each particular video item, in the second plurality of video items, with an embedding associated with said each video item in the second group to generate a second video pair score;
adding the second video pair score to a second set of video pair scores;
based on the second set of video pair scores, storing a second mapping that associates said each particular video item, in the second plurality of video items, with one or more video items in the second group;
adding the second mapping to a second set of mappings.

### Claim 10 (depends on 1)

The method of claim 1, wherein:
each video item in the second plurality of video items is associated with values for a set of metadata attributes;
each video item in the first plurality of video items is not associated with values for the set of metadata attributes.

### Claim 11

One or more storage media storing instructions which, when executed by one or more processors, cause:
identifying a first plurality of video items;
identifying metadata of each video item in the first plurality of video items;
by inserting the metadata of each video item into a machine-learned embedding generator, generating an embedding for each video item in the first plurality of video items;
generating a plurality of groups of the first plurality of video items, wherein each video item in the first plurality of video items is assigned to a group in the plurality of groups based on the embedding generated for said each video item;
identifying a second plurality of video items;
generating an embedding for each video item in the second plurality of video items;
for each particular video item in the second plurality of video items:
for each group of the plurality of groups;
comparing the embedding of said each particular video item with an embedding associated with said each group to generate a group score;
adding the group score to a set of group scores;
identifying a particular group, in the plurality of groups, that is associated with the highest group score in the set of group scores;
for each video item in the particular group:
comparing the embedding of said each particular video item with an embedding associated with said each video item in the particular group to generate a video pair score;
adding the video pair score to a set of video pair scores;
based on the set of video pair scores, storing a mapping that associates said each particular video item with one or more video items in the particular group;
adding the mapping to a set of mappings.

### Claim 12 (depends on 11)

The one or more storage media of claim 11, wherein generating the plurality of groups comprises using a k-means clustering technique to generate the plurality of groups.

### Claim 13 (depends on 11)

The one or more storage media of claim 11, wherein the instructions, when executed by the one or more processors, further cause:
identifying, for a particular user, a subset of the second plurality of video items;
for each video item in the subset:
identifying said each video item in a particular mapping in the set of mappings;
based on the particular mapping, identifying one or more video items in the first plurality of video items;
adding the one or more video items to a set of video items;
causing first data about each video item in the set of video items to be presented on a computing device of the particular user.

### Claim 14 (depends on 13)

The one or more storage media of claim 13, wherein the instructions, when executed by the one or more processors, further cause:
causing second data about each video item in the subset to be presented on the computing device of the particular user.

### Claim 15 (depends on 13)

The one or more storage media of claim 13, wherein identifying, for the particular user, the subset of the second plurality of video items, comprises:
identifying a first plurality of attribute values of the particular user;
for each video item in a second subset of the second plurality of video items:
identifying a second plurality of attribute values of said each video item;
generating a plurality of feature values based on the first plurality of attribute values and the second plurality of attribute values;
inputting the plurality of feature values into a machine-learned model to generate a user-item pair score;
adding the user-item pair score to a set of user-item pair scores;
selecting the subset from the second subset based on the set of user-item pair scores.

### Claim 16 (depends on 11)

The one or more storage media of claim 11, wherein the embedding generated for each video item in the first plurality of video items is a first embedding, wherein the plurality of groups is a first plurality of groups, wherein the instructions, when executed by the one or more processors, further cause:
generating a second embedding for each video item in the first plurality of video items;
generating a second plurality of groups of the first plurality of video items, wherein each video item in the second plurality of video items is assigned to a group in the second plurality of groups based on the second embedding generated for said each video item.

### Claim 17 (depends on 16)

The one or more storage media of claim 16, wherein the first embedding of each video item in the first plurality of video items is a title of said each video item and the second embedding of each video item in the first plurality of video items is a description of said each video item.

### Claim 18 (depends on 11)

The one or more storage media of claim 11, wherein:
each video item in the second plurality of video items is associated with values for a set of metadata attributes;
each video item in the first plurality of video items is not associated with values for the set of metadata attributes.