Suppression and deduplication of place-entities on online social networks

• US 10,282,434 B2
• Filed: 06/24/2016
• Issued: 05/07/2019
• Est. Priority Date: 01/11/2016
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Ott, Myle Arif, Briceno, Jason Luis, Shmueli, Yaniv
• Primary Examiner(s): Chbouki, Tarek
• Application Number:
  US15/192,702
• Publication Number:
  US 20170199905A1
• Time in Patent Office: 1,047 Days
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/29 Geographical information databases
• 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: G06Q 50/01 Social networking
• CPC Class Codes: H04L 51/222 using geographical location information, e.g. messages transmitted or received in proximity of a certain spot or area
• CPC Class Codes: H04L 51/52 for supporting social networking services
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/306 User profiles
• CPC Class Codes: H04L 67/563 Data redirection of data network streams
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/80 Services using short range communication, e.g. near-field communication [NFC], radio-frequency identification [RFID] or low energy communication

Abstract

In one embodiment, an online social network accesses a place-entities graph that includes a plurality of place-entity nodes, each place-entity node representing a particular place-entity associated with a particular geographic location. From one of a plurality of search clients associated with the online social network, a threshold duplication value and a threshold redirect value is received. The online social network identifies place-entity clusters of place-entity nodes within the place-entities graph. In each place-entity cluster, the place-entity nodes have duplication values with respect to a canonical place-entity node in the cluster that are above the threshold duplication value. The online social network generates a redirection graph for the one search client. The redirection graph includes the identified place-entity clusters, where for each cluster, a redirection edge is established between a place-entity node and the corresponding canonical place-entity node based on the duplication value and the threshold redirect value.

Claims

1. A method comprising:

by one or more computing devices of an online social network, receiving, from a search client of a plurality of search clients of the online social network, a threshold duplication-value and a threshold redirect-value associated with the search client, wherein the threshold duplication-value is a threshold to determine whether to cluster two or more place-entities based on duplication-values for the place-entities, and wherein the threshold redirect-value is a threshold to determine whether to redirect one place-entity to another place-entity in a same place-entity cluster;

by the one or more computing devices, accessing a place-entities graph comprising a plurality of place-entity nodes, each place-entity node representing a place-entity associated with a particular geographic location;

by the one or more computing devices, identifying a plurality of place-entity clusters within the place-entities graph, wherein each place-entity cluster comprises place-entity nodes having duplication-values with respect to a canonical place-entity node in the place-entity cluster above the threshold duplication-value; and

by the one or more computing devices, generating a redirection graph for the search client based on the place-entities graph, wherein the redirection graph comprises the plurality of place-entity nodes and the identified place-entity clusters, and wherein for each place-entity node in each place-entity cluster a redirection edge is established between the place-entity node and the respective canonical place-entity node of the place-entity cluster if the duplication-value for the place-entity node is greater than the threshold redirect-value.

2. The method of claim 1, wherein the duplication-value for the place-entity node with respect to the canonical place-entity node represents a likelihood that the place-entity node and the canonical place-entity node each correspond to a same geographic location.

3. The method of claim 1, further comprising calculating a duplication-value for each pair of place-entity nodes, the duplication-value representing a likelihood that each place-entity node of the pair of place-entity nodes corresponds to a same geographic location.

4. The method of claim 1, further comprising designating, for each place-entity cluster, one of the place-entity nodes within the place-entity cluster to be the canonical place-entity node of the place-entity cluster.

5. The method claim 4, wherein the canonical place-entity node is determined based at least in part on duplication-values between the place-entity nodes within the place-entity cluster.

6. The method of claim 1, further comprising:

receiving, from a client system of a user of the online social network via the search client, a search query associated with a particular place-entity node in a particular place-entity cluster having a particular canonical place-entity node; and

sending, to the client system, a response to the search query, wherein;

if the particular place-entity node is connected to the particular canonical place-entity node by a redirection edge within the redirection graph for the search client, the response comprises a reference to the particular canonical place-entity node;

else the response comprises a reference to the particular place-entity node.

7. The method of claim 6, wherein the threshold duplication-value and the threshold redirect-value are based on attributes of the user.

8. The method of claim 1, further comprising:

receiving, from the search client, a threshold quality-score; and

calculating a quality-score for each place-entity node of the plurality of place-entity nodes.

9. The method of claim 8, wherein the quality-score for a place-entity node is based on one or more of an accuracy of attributes of a place-entity associated with the place-entity node, a number of photos associated with the place-entity, an amount of content associated with the place-entity, a recency-value associated with the content or photos, or a number of social signals associated with the place-entity.

10. The method of claim 9, wherein the social signals associated with the place-entity comprise check-ins, likes, comments, views, or reviews of the place-entity provided by users of the online social network.

11. The method of claim 8, wherein, for each place-entity cluster, the canonical place-entity node in the place-entity cluster has a highest quality-score of the place-entity nodes within the place-entity cluster.

12. The method of claim 8, further comprising generating, from the redirection graph, a filtered graph by removing from the redirection graph one or more place-entity nodes having quality-scores below the threshold quality-score.

13. The method of claim 8, further comprising:

receiving, from a client system of a user of the online social network via the search client, a search query associated with a particular place-entity node in a particular place-entity cluster having a particular canonical place-entity node; and

sending, to the client system, a response to the search query, wherein;

if the particular place-entity node has a quality-score less than the threshold quality-score, then the response comprises a reference to the particular canonical place-entity node;

else the response comprises a reference to the particular place-entity node.

14. The method of claim 1, further comprising:

receiving, from a client system of a user of the online social network via the search client, a search query associated with a particular place-entity node in a particular place-entity cluster having a particular canonical place-entity node;

determining that;

the user is an administrator of the particular place-entity node; and

the particular place-entity node is connected to the particular canonical place-entity node by a redirection edge; and

overriding, based on the user being the administrator of the particular place-entity node, the redirection edge between the particular place-entity node and the particular canonical place-entity node by sending to the client system a response to the search query comprising a reference to the particular place-entity node.

15. The method of claim 1, further comprising accessing a social graph of the online social network, the social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each edge between two nodes representing a single degree of separation between the two nodes, the plurality of nodes comprising a plurality of user nodes corresponding to a plurality of users of the online social network, respectively.

16. The method of claim 1, further comprising:

receiving, from a client system of a user of the online social network via the search client, a search query associated with a particular place-entity node in a particular place-entity cluster having a particular canonical place-entity node;

determining that;

the user has a social-graph affinity with respect to the particular place-entity node greater than a threshold affinity; and

the particular place-entity node is connected to the particular canonical place-entity node by a redirection edge; and

overriding, based on the user having the social-graph affinity with respect to the particular place-entity node greater than the threshold affinity, the redirection edge between the particular place-entity node and the particular canonical place-entity node by sending to the client system of the user a response to the search query comprising a reference to the particular place-entity node.

17. The method of claim 1, further comprising:

receiving, from a client system of a user of the online social network via the search client, a search query;

identifying a plurality of place-entity nodes matching the search query within the redirection graph for the search client;

ranking the identified place-entity nodes based on quality-scores associated with the identified place-entity nodes; and

sending, to the client system of the user, a search-results page comprising references to each place-entity node having a ranking greater than a threshold ranking.

18. The method of claim 17, further comprising:

determining that the user has a social-graph affinity, with respect to particular identified place-entity nodes, greater than a threshold affinity; and

boosting a ranking of the particular identified place-entity nodes based on the user having the social-graph affinity with respect to the particular identified place-entity nodes greater than the threshold affinity.

19. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

receive, from a search client of a plurality of search clients of an online social network, a threshold duplication-value and a threshold redirect-value associated with the search client, wherein the threshold duplication-value is a threshold to determine whether to cluster two or more place-entities based on duplication-values for the place-entities, and wherein the threshold redirect-value is a threshold to determine whether to redirect one place-entity to another place-entity in a same place-entity cluster;

access a place-entities graph comprising a plurality of place-entity nodes, each place-entity node representing a place-entity associated with a particular geographic location;

identify a plurality of place-entity clusters within the place-entities graph, wherein each place-entity cluster comprises place-entity nodes having duplication-values with respect to a canonical place-entity node in the place-entity cluster above the threshold duplication-value; and

generate a redirection graph for the search client based on the place-entities graph, wherein the redirection graph comprises the plurality of place-entity nodes and the identified place-entity clusters, and wherein for each place-entity node in each place-entity cluster a redirection edge is established between the place-entity node and the respective canonical place-entity node of the place-entity cluster if the duplication-value for the place-entity node is greater than the threshold redirect-value.

20. A system comprising:

one or more processors; and

a memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to;

receive, from a search client of a plurality of search clients of an online social network, a threshold duplication-value and a threshold redirect-value associated with the search client, wherein the threshold duplication-value is a threshold to determine whether to cluster two or more place-entities based on duplication-values for the place-entities, and wherein the threshold redirect-value is a threshold to determine whether to redirect one place-entity to another place-entity in a same place-entity cluster;

access a place-entities graph comprising a plurality of place-entity nodes, each place-entity node representing a place-entity associated with a particular geographic location;

identify a plurality of place-entity clusters within the place-entities graph, wherein each place-entity cluster comprises place-entity nodes having duplication-values with respect to a canonical place-entity node in the place-entity cluster above the threshold duplication-value; and

generate a redirection graph for the search client based on the place-entities graph, wherein the redirection graph comprises the plurality of place-entity nodes and the identified place-entity clusters, and wherein for each place-entity node in each place-entity cluster a redirection edge is established between the place-entity node and the respective canonical place-entity node of the place-entity cluster if the duplication-value for the place-entity node is greater than the threshold redirect-value.