SYSTEMS AND METHODS FOR ONLINE CLUSTERING OF CONTENT ITEMS

• US 20170185665A1
• Filed: 12/28/2015
• Published: 06/29/2017
• Est. Priority Date: 12/28/2015
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Gong, Yunchao, Bourdev, Lubomir, Pawlowski, Marcin, Yang, Fei, Fergus, Robert D., Brandy, Louis Dominic
• Granted Patent: US 11,003,692 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

Systems, methods, and non-transitory computer-readable media can obtain a first batch of content items to be clustered. A set of clusters can be generated by clustering respective binary hash codes for each content item in the first batch, wherein content items included in a cluster are visually similar to one another. A next batch of content items to be clustered can be obtained. One or more respective binary hash codes for the content items in the next batch can be assigned to a cluster in the set of clusters.

Claims

1. A computer-implemented method comprising:

obtaining, by a computing system, a first batch of content items to be clustered;

generating, by the computing system, a set of clusters by clustering respective binary hash codes for each content item in the first batch, wherein content items included in a cluster are visually similar to one another;

obtaining, by the computing system, a next batch of content items to be clustered; and

assigning, by the computing system, one or more respective binary hash codes for the content items in the next batch to a cluster in the set of clusters.

2. The computer-implemented method of claim 1, wherein obtaining, by the computing system, the first batch of content items to be clustered further comprises at least one of:

determining that a threshold number of content items have been received, or

determining that a threshold period of time has elapsed.

3. The computer-implemented method of claim 1, wherein generating, by the computing system, the set of clusters further comprises:

generating a respective binary hash code for each content item in the first batch;

selecting a set of cluster centers from the content items in the first batch, wherein each cluster center is associated with a respective binary hash code;

determining, for each content item in the first batch, a corresponding cluster from the set of clusters; and

determining an updated set of cluster centers for the set of clusters.

4. The computer-implemented method of claim 3, wherein determining, for each content item in the first batch, the corresponding cluster from the set of clusters further comprises:

determining a nearest cluster center for each content item in the first batch;

determining, for each content item in the first batch, a respective distance between the binary hash code for the content item and a binary hash code corresponding to the nearest cluster center for the content item; and

assigning each content item in the first batch to a cluster corresponding to the nearest cluster center for the content item based at least in part on the respective distance satisfying a threshold.

5. The computer-implemented method of claim 4, wherein determining the nearest cluster center for each content item in the first batch further comprises:

obtaining information describing the nearest cluster center for the content item using a multi-index hash table by hashing a binary hash code for the content item.

6. The computer-implemented method of claim 1, the method further comprising:

generating, by the computing system and for the set of clusters, at least one additional cluster by clustering the respective unassigned binary hash codes for the content items in the next batch.

7. The computer-implemented method of claim 1, the method further comprising:

removing, from each cluster in the set of clusters, content items in the cluster that are at least a threshold distance from a cluster center corresponding to the cluster.

8. The computer-implemented method of claim 1, the method further comprising:

removing, from the set of clusters, clusters that are smaller than a threshold size.

9. The computer-implemented method of claim 1, wherein assigning, by the computing system, the one or more respective binary hash codes for the content items in the next batch to a cluster in the set of clusters further comprises:

determining a nearest cluster center for each content item in the next batch; and

determining, for each content item in the next batch, that a respective distance between the binary hash code for the content item and a binary hash code corresponding to the nearest cluster center for the content item satisfies a threshold.

10. The computer-implemented method of claim 1, the method further comprising:

determining that a content item is categorized as spam;

determining a cluster in which the content item was clustered, the cluster including a plurality of other content items; and

determining that the plurality of other content items in the cluster are spam.

11. A system comprising:

at least one processor; and

a memory storing instructions that, when executed by the at least one processor, cause the system to perform;

obtaining a first batch of content items to be clustered;

generating a set of clusters by clustering respective binary hash codes for each content item in the first batch, wherein content items included in a cluster are visually similar to one another;

obtaining a next batch of content items to be clustered; and

assigning one or more respective binary hash codes for the content items in the next batch to a cluster in the set of clusters.

12. The system of claim 11, wherein obtaining the first batch of content items to be clustered further comprises at least one of:

determining that a threshold number of content items have been received, or

determining that a threshold period of time has elapsed.

13. The system of claim 11, wherein generating the set of clusters further comprises:

generating a respective binary hash code for each content item in the first batch;

selecting a set of cluster centers from the content items in the first batch, wherein each cluster center is associated with a respective binary hash code;

determining, for each content item in the first batch, a corresponding cluster from the set of clusters; and

determining an updated set of cluster centers for the set of clusters.

14. The system of claim 13, wherein determining, for each content item in the first batch, the corresponding cluster from the set of clusters further comprises:

determining a nearest cluster center for each content item in the first batch;

determining, for each content item in the first batch, a respective distance between the binary hash code for the content item and a binary hash code corresponding to the nearest cluster center for the content item; and

assigning each content item in the first batch to a cluster corresponding to the nearest cluster center for the content item based at least in part on the respective distance satisfying a threshold.

15. The system of claim 14, wherein determining the nearest cluster center for each content item in the first batch further comprises:

obtaining information describing the nearest cluster center for the content item using a multi-index hash table by hashing a binary hash code for the content item.

16. A non-transitory computer-readable storage medium including instructions that, when executed by at least one processor of a computing system, cause the computing system to perform a method comprising:

obtaining a first batch of content items to be clustered;

generating a set of clusters by clustering respective binary hash codes for each content item in the first batch, wherein content items included in a cluster are visually similar to one another;

obtaining a next batch of content items to be clustered; and

assigning one or more respective binary hash codes for the content items in the next batch to a cluster in the set of clusters.

17. The non-transitory computer-readable storage medium of claim 16, wherein obtaining the first batch of content items to be clustered further comprises at least one of:

determining that a threshold number of content items have been received, or

determining that a threshold period of time has elapsed.

18. The non-transitory computer-readable storage medium of claim 16, wherein generating the set of clusters further comprises:

generating a respective binary hash code for each content item in the first batch;

selecting a set of cluster centers from the content items in the first batch, wherein each cluster center is associated with a respective binary hash code;

determining, for each content item in the first batch, a corresponding cluster from the set of clusters; and

determining an updated set of cluster centers for the set of clusters.

19. The non-transitory computer-readable storage medium of claim 18, wherein determining, for each content item in the first batch, the corresponding cluster from the set of clusters further comprises:

determining a nearest cluster center for each content item in the first batch;

determining, for each content item in the first batch, a respective distance between the binary hash code for the content item and a binary hash code corresponding to the nearest cluster center for the content item; and

assigning each content item in the first batch to a cluster corresponding to the nearest cluster center for the content item based at least in part on the respective distance satisfying a threshold.

20. The non-transitory computer-readable storage medium of claim 19, wherein determining the nearest cluster center for each content item in the first batch further comprises:

obtaining information describing the nearest cluster center for the content item using a multi-index hash table by hashing a binary hash code for the content item.