Measuring phrase association on online social networks

• US 10,248,645 B2
• Filed: 05/30/2017
• Issued: 04/02/2019
• Est. Priority Date: 05/30/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: Ringger, Eric, Kamichetty, Hetunandan Munisharan, Raina, Rajat
• Primary Examiner(s): Stevens, Robert
• Application Number:
  US15/608,216
• Publication Number:
  US 20180349347A1
• Time in Patent Office: 672 Days
• Field of Search: 707736
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/90324 using system suggestions
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/295 Named entity recognition
• CPC Class Codes: G06Q 30/0251 Targeted advertisements
• CPC Class Codes: G06Q 30/0277 Online advertisement
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

In one embodiment, a method includes retrieving multiple posts containing each of the query terms after receiving a search query for posts from a user of an online social network, identifying, from an index of known phrases, one or more known phrases in the text of the retrieved posts, filtering the retrieved posts to generate a filtered set of posts, wherein the filtering comprises removing each post not containing at least one of the identified known phrases, computing features for each of the identified known phrases, calculating a score for each post in the filtered set based on the features of the identified known phrases, ranking the posts based on the calculated scores, and sending instructions, to the client system, for generating a search-results interface comprising references to one or more of the posts presented in ranked order.

Claims

1. A method comprising, by a computing device:

receiving, from a client system of a first user of an online social network, a search query for posts of the online social network, the search query comprising one or more query terms;

retrieving a plurality of posts of the online social network, each post containing each of the one or more query terms in a text of the post;

identifying, from an index of known phrases, one or more known phrases in the text of the one or more retrieved posts, each identified known phrase containing at least one of the one or more query terms, wherein the index of known phrases comprises a plurality of pre-identified phrases having a length less than or equal to a pre-determined maximum length;

filtering the plurality of retrieved posts to generate a filtered set of posts, wherein the filtering comprises removing each post not containing at least one of the identified known phrases;

computing a plurality of features for each of the identified known phrases, each feature measuring a degree of equivalence between the identified known phrase and the one or more query terms included in the identified known phrase;

calculating, for each post in the filtered set of posts, a score for the post based on the plurality of features of the identified known phrases included in the post;

ranking the posts based on the calculated scores; and

sending, to the client system in response to the search query, instructions for generating a search-results interface comprising references to one or more of the posts presented in ranked order.

2. The method of claim 1, wherein identifying one or more known phrases comprises:

identifying, in the text of each of the one or more retrieved posts, a plurality of candidate phrases comprising at least one of the one or more query terms and having a length less than or equal to the pre-determined maximum length; and

determining whether each of the identified candidate phrases matches in the index of known phrases.

3. The method of claim 2, wherein identifying the plurality of candidate phrases comprises:

searching, in the text of each retrieved post, any of the one or more query terms; and

for each searched query term;

for a target length from 2 to the pre-determined maximum length being increased by one at each iteration;

identifying, around the searched term in the text, all phrases containing the searched query term and having a length equal to the target length.

4. The method of claim 1, wherein each phrase in the index of known phrases comprises a plurality of element terms, each element term of a phrase having an association greater than a threshold with respect to each other element term of the phrase, and wherein the association is measured with respect to terms extracted from a set of posts associated with the online social network posts created during a pre-determined period of time.

5. The method of claim 4, wherein the association is measured by a Normalized Pointwise Mutual Information (NPMI) score.

6. The method of claim 1, wherein the index of known phrases is stored in a phrase table comprising a plurality of entries, each entry in the phrase table comprising a phrase, element terms of the phrase, and their respective counts.

7. The method of claim 6, wherein the counts are user counts, each user count for an element being the number of unique users that mentioned the element in their posts.

8. The method of claim 6, wherein the counts are post counts, each post count for an element being the number of unique posts that contain the element.

9. The method of claim 1, further comprising aggregating features for all known phrases in a post, wherein the aggregated features are used for scoring the post.

10. The method of claim 9, wherein the aggregated features for the known phrases in each post comprises one or more of:

calculated mean values of respective kind of features for the known phrases in the post;

calculated minimum values of respective kind of features for the known phrases in the post;

or

calculated maximum values of respective kind of features for the known phrases in the post.

11. The method of claim 1, wherein the features are computed from counts in the index of known phrases.

12. The method of claim 1, wherein calculating the score for the post comprises applying a pre-determined evaluation model on the features.

13. The method of claim 1, wherein each identified known phrase comprises query term element and non-query term elements, wherein the query term element comprises one or more query terms in the identified known phrase and the non-query term elements comprise element terms excluding the query term element in the identified known phrase, wherein the features comprise one or more of:

a log probability of the query term element;

a log joint-probability of the non-query term elements;

a Pointwise Kullback-Leibler divergence score of a probability of the query term element compared to a conditional probability of the query term element given the non-query term elements;

a Pointwise Kullback-Leibler divergence score of a conditional probability of the query term element given the non-query term elements compared to a probability of the query term element;

a Pointwise Jensen-Shannon divergence score of a probability of the query term element compared to a conditional probability of the query term element given the non-query term elements;

a Pointwise Kullback-Leibler divergence score of a joint-probability of the non-query term elements compared to a conditional joint-probability of the non-query term elements given the query term element;

a Pointwise Kullback-Leibler divergence score of a conditional joint-probability of the non-query term elements given the query term element compared to a joint-probability of the non-query term elements;

a Pointwise Jensen-Shannon divergence score of a joint-probability of the non-query term elements compared to a conditional joint-probability of the non-query term elements given the query term element;

a Pointwise Mutual Information score of the non-query term elements and the query term element;

a Normalized Pointwise Mutual Information of the non-query term elements and the query term element;

or

an Euclidean distance between the word2vec embedding of the query term element from the word2vec embedding of the identified known phrase.

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

receive, from a client system of a first user of an online social network, a search query for posts of the online social network, the search query comprising one or more query terms;

retrieve a plurality of posts of the online social network, each post containing each of the one or more query terms in a text of the post;

identify, from an index of known phrases, one or more known phrases in the text of the one or more retrieved posts, each identified known phrase containing at least one of the one or more query terms, wherein the index of known phrases comprises a plurality of pre-identified phrases having a length less than or equal to a pre-determined maximum length;

filter the plurality of retrieved posts to generate a filtered set of posts, wherein the filtering comprises removing each post not containing at least one of the identified known phrases;

compute a plurality of features for each of the identified known phrases, each feature measuring a degree of equivalence between the identified known phrase and the one or more query terms included in the identified known phrase;

calculate, for each post in the filtered set of posts, a score for the post based on the plurality of features of the identified known phrases included in the post;

rank the posts based on the calculated scores; and

send, to the client system in response to the search query, instructions for generating a search-results interface comprising references to one or more of the posts presented in ranked order.

15. The media of claim 14, wherein identifying one or more known phrases comprises:

identifying, in the text of each of the one or more retrieved posts, a plurality of candidate phrases comprising at least one of the one or more query terms and having a length less than or equal to the pre-determined maximum length; and

determining whether each of the identified candidate phrases matches in the index of known phrases.

16. The media of claim 14, wherein identifying the plurality of candidate phrases comprises:

searching, in the text of each retrieved post, any of the one or more query terms; and

for each searched query term;

for a target length from 2 to the pre-determined maximum length being increased by one at each iteration;

identifying, around the searched term in the text, all phrases containing the searched query term and having a length equal to the target length.

17. The media of claim 14, wherein each phrase in the index of known phrases comprises a plurality of element terms, each element term of a phrase having an association greater than a threshold with respect to each other element term of the phrase, and wherein the association is measured with respect to terms extracted from a set of posts associated with the online social network posts created during a pre-determined period of time.

18. The media of claim 14, wherein the association is measured by a Normalized Pointwise Mutual Information (NPMI) score.

19. The media of claim 14, wherein the index of known phrases is stored in a phrase table comprising a plurality of entries, each entry in the phrase table comprising a phrase, element terms of the phrase, and their respective counts.

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, from a client system of a first user of an online social network, a search query for posts of the online social network, the search query comprising one or more query terms;

retrieve a plurality of posts of the online social network, each post containing each of the one or more query terms in a text of the post;

identify, from an index of known phrases, one or more known phrases in the text of the one or more retrieved posts, each identified known phrase containing at least one of the one or more query terms, wherein the index of known phrases comprises a plurality of pre-identified phrases having a length less than or equal to a pre-determined maximum length;

filter the plurality of retrieved posts to generate a filtered set of posts, wherein the filtering comprises removing each post not containing at least one of the identified known phrases;

compute a plurality of features for each of the identified known phrases, each feature measuring a degree of equivalence between the identified known phrase and the one or more query terms included in the identified known phrase;

calculate, for each post in the filtered set of posts, a score for the post based on the plurality of features of the identified known phrases included in the post;

rank the posts based on the calculated scores; and

send, to the client system in response to the search query, instructions for generating a search-results interface comprising references to one or more of the posts presented in ranked order.