OPTIONALIZATION AND FUZZY SEARCH ON ONLINE SOCIAL NETWORKS

• US 20170103110A1
• Filed: 10/07/2015
• Published: 04/13/2017
• Est. Priority Date: 10/07/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: Winstanley, Melissa Rose
• Granted Patent: US 10,810,217 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/2468 Fuzzy queries
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence

Abstract

In one embodiment, a method includes receiving a search query and parsing the search query to identify one or more terms to optionalize, searching one or more data stores to identify a plurality of objects, including a second set of objects associated with the online social network that matches one or more of the search terms and does not match at least one of the optionalized terms, scoring each of the identified objects, where for each object of the second set of objects the score calculated by the scoring algorithm is based on one or more fuzzy matching terms of the object corresponding to one or more optionalized terms of the search query, respectively, and sending a search-results page to the client system of the first user.

Claims

1. A method comprising:

receiving, from a client system of a first user of an online social network, a search query comprising a plurality of terms;

parsing the search query to identify one or more terms to optionalize;

searching one or more data stores to identify a plurality of objects, wherein the identified objects comprise;

a first set of objects associated with the online social network that match each term of the search query; and

a second set of objects associated with the online social network that matches one or more of the search terms and does not match at least one of the optionalized terms;

scoring each of the identified objects based on one or more scoring algorithms, wherein for each object in the first set of objects the score calculated by the scoring algorithms is based on the matching terms of the object, and wherein for each object of the second set of objects the score calculated by the scoring algorithm is based on the matching terms of the object and one or more fuzzy matching terms of the object corresponding to one or more optionalized terms of the search query, respectively; and

sending, responsive to the search query, a search-results page to the client system of the first user for display, the search-results page comprising one or more search results referencing one or more of the identified objects, respectively, each search result corresponding to an identified object having a score greater than a threshold score.

2. The method of claim 1, wherein each term of the search query is identified to optionalize.

3. The method of claim 1, wherein parsing the search query to identify one or more terms to optionalize comprises applying a term frequency-inverse document frequency (TF-IDF) analysis of the terms in the search query.

4. The method of claim 1, wherein parsing the search query to identify one or more search terms to optionalize comprises identifying word segments in the search query based on a word segment dictionary.

5. The method of claim 1, further comprising parsing the query to identify one or more query constraints, wherein at least one query constraint is an optionalized constraint for identifying objects that do not match one of the optionalized terms.

6. The method of claim 5, further comprising generating a query command based on the search query, wherein the query command comprises at least the optionalized constraint.

7. The method of claim 1, wherein the fuzzy matching terms are identified based on one or more of lower-probability expansions, reverse stems, synonyms, spell correction, or tokenization of the optionalized words.

8. The method of claim 1, wherein scoring is based at least on one or more of a percent of keywords in the search results, a distance between fuzzy matching terms in a search results, or whether the fuzzy matching terms occur in a same order as the search query.

9. The method of claim 1, wherein the fuzzy matching terms are identified based on a calculated edit-distance with respect to the fuzzy matching term and the corresponding optionalized term of the search query.

10. The method of claim 1, wherein the fuzzy matching terms are identified based on a word2vec calculation with respect to the fuzzy matching term and the corresponding optionalized term of the search query.

11. The method of claim 1, further comprising generating one or more search results corresponding to one or more of the identified objects, respectively, each search result comprising a reference to the corresponding identified object, wherein at least one of the search results corresponds to an object from the first set of objects, and wherein at least one of the search results corresponds to an object from the second set of objects.

12. The method of claim 1, further comprising blending the first and second sets of identified objects to form a set of blended search results comprising a threshold number of identified objects from each set.

13. The method of claim 1, further comprising accessing a social graph comprising a plurality of nodes and plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the nodes comprising:

a first node corresponding to the first user; and

a plurality of second nodes corresponding to a plurality of objects associated with the online social network, respectively.

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 comprising a plurality of terms;

parse the search query to identify one or more terms to optionalize;

search one or more data stores to identify a plurality of objects, wherein the identified objects comprise;

a first set of objects associated with the online social network that match each term of the search query; and

a second set of objects associated with the online social network that matches one or more of the search terms and does not match at least one of the optionalized terms;

score each of the identified objects based on one or more scoring algorithms, wherein for each object in the first set of objects the score calculated by the scoring algorithms is based on the matching terms of the object, and wherein for each object of the second set of objects the score calculated by the scoring algorithm is based on the matching terms of the object and one or more fuzzy matching terms of the object corresponding to one or more optionalized terms of the search query, respectively; and

send, responsive to the search query, a search-results page to the client system of the first user for display, the search-results page comprising one or more search results referencing one or more of the identified objects, respectively, each search result corresponding to an identified object having a score greater than a threshold score.

15. A system comprising:

one or more processors; and

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

receive, from a client system of a first user of an online social network, a search query comprising a plurality of terms;

parse the search query to identify one or more terms to optionalize;

search one or more data stores to identify a plurality of objects, wherein the identified objects comprise;

a first set of objects associated with the online social network that match each term of the search query; and

a second set of objects associated with the online social network that matches one or more of the search terms and does not match at least one of the optionalized terms;

score each of the identified objects based on one or more scoring algorithms, wherein for each object in the first set of objects the score calculated by the scoring algorithms is based on the matching terms of the object, and wherein for each object of the second set of objects the score calculated by the scoring algorithm is based on the matching terms of the object and one or more fuzzy matching terms of the object corresponding to one or more optionalized terms of the search query, respectively; and

send, responsive to the search query, a search-results page to the client system of the first user for display, the search-results page comprising one or more search results referencing one or more of the identified objects, respectively, each search result corresponding to an identified object having a score greater than a threshold score.