Systems and methods for improved web searching
View Patent ↗Systems and methods are provided for improved web searching. In one implementation, suggested search queries are provided based on previous search queries and click data. A weighted bi-partite graph or index may be used to identify related search queries based on overlapping clicked URLs. According to a method, query-click log data of a search engine is processed to generate sets of suggested search queries, data corresponding to each suggested search query, and a set of clicked URLs related to each suggested search query. Additionally, or independently, methods may be provided for contextually correcting spelling errors within sets of suggested search queries using a contextual algorithm, and/or identifying and discarding sets of suggested search queries and URLs that lead to restricted material, such as restricted content and related URLs.
1. A computer-implemented method, comprising:
identifying one or more unique tokens and bi-grams within a clustered set of search queries, the unique tokens having corresponding lengths that exceed a first threshold value;
computing, using at least one processor, edit distances for a subset of the identified tokens and bi-grams, the subset comprising tokens or bi-grams within unit length of each other token or bi-gram in the subset; and
determining, using the at least one processor, that a least-frequent token or bi-gram in the subset is misspelled, when the edit distance for the least-frequent token or bi-gram falls below a second threshold value.
2. The method of claim 1 , wherein the clustered set of search queries comprises suggested search queries related to an initial search query.
3. The method of claim 1 , further comprising:
receiving an initial search query comprising one or more of a keyword and a portion of a URL;
comparing the initial search query against an index of suggested search queries, the index comprising stored search queries and related click data based on previous search queries; and
identifying the clustered set of search queries, based on the comparison.
4. The method of claim 3 , further comprising processing the keyword or URL portion to conform to one or more requirements of a search engine.
5. The method of claim 1 , further comprising:
processing a log of a search engine to obtain records related to previous search queries and click data;
grouping the records to generate one or more sets of suggested search queries; and
identifying the clustered set of search queries based on at least one of a frequency, a click count, or a sponsored click count associated with the sets of suggested search queries.
6. The method of claim 5 , further comprising processing the obtained records to remove records related to restricted content.
7. The method of claim 6 , wherein the processing step comprises:
selecting a record from the obtained records;
matching a substring of the selected record against a first list comprising one or more search queries and URLs related to restricted content;
identifying the selected record as a blocked record, when the substring of the selected record matches a listing within the first list;
matching a substring of the blocked record against a second list; and
discarding the blocked record when no substring of the blocked record matches a listing within the second list.
8. The method of claim 1 , further comprising discarding the clustered set of search queries, when the subset of the identified tokens and bi-grams includes the spelling error.
9. The method of claim 1 , further comprising:
determining a corrected spelling for the misspelled token or bigram; and
providing the corrected spelling to one or more of a user and a search engine.
10. The method of claim 9 , wherein determining the corrected spelling comprises:
determining a most-frequent permutation of the misspelled token or bi-gram based on a correction chain associated with the misspelled token or bi-gram; and
identifying the most-frequent permutation of the misspelled token or bi-gram as the corrected spelling of the corresponding token or bi-gram.
11. An apparatus, comprising:
a storage device that stores a set of instructions; and
at least one processor coupled to the storage device, the at least one processor being operative with the set of instructions and being configured to:
identify one or more unique tokens and bi-grams within a clustered set of search queries, the unique tokens having corresponding lengths that exceed a first threshold value;
compute edit distances for a subset of the identified tokens and bi-grams, the subset comprising tokens or bi-grams within unit length of each other token or bi-gram in the subset; and
determine that a least-frequent token or bi-gram in the subset is misspelled, when the edit distance for the least-frequent token or bi-gram falls below a second threshold value.
12. The apparatus of claim 11 , wherein the clustered set of search queries comprises suggested search queries related to an initial search query.
13. The apparatus of claim 11 , wherein the at least one processor is further configured to:
receive an initial search query comprising one or more of a keyword and a portion of a URL;
compare the initial search query against an index of suggested search queries, the index comprising stored search queries and related click data based on previous search queries; and
identify the clustered set of search queries, based on the comparison.
14. The apparatus of claim 11 , wherein the at least one processor is further configured to:
process a log of a search engine to obtain records related to previous search queries and click data;
group the records to generate one or more sets of suggested search queries; and
identify the clustered set of search queries based on at least one of a frequency, a click count, or a sponsored click count associated with the sets of suggested search queries.
15. The apparatus of claim 14 , wherein the at least one processor is further configured to process the obtained records to remove records related to restricted content.
16. The apparatus of claim 15 , wherein the at least one processor is further configured to:
select a record from the obtained records;
match a substring of the selected record against a first list comprising one or more search queries and URLs related to restricted content;
identify the selected record as a blocked record, when the substring of the selected record matches a listing within the first list;
match a substring of the blocked record against a second list; and
discard the blocked record when no substring of the blocked record matches a listing within the second list.
17. The apparatus of claim 12 , wherein the at least one processor is further configured to discard the clustered set of search queries, when the subset of the identified tokens and bi-grams includes the spelling error.
18. The apparatus of claim 12 , wherein the at least one processor is further configured to:
determine a corrected spelling for the misspelled token or bigram; and
provide the corrected spelling to one or more of a user and a search engine.
19. The apparatus of claim 12 , wherein the at least one processor is further configured to:
determine a most-frequent permutation of the misspelled token or bi-gram based on a correction chain associated with the misspelled token or bi-gram; and
identify the most-frequent permutation of the misspelled token or bi-gram as the corrected spelling of the corresponding token or bi-gram.
20. A tangible, non-transitory computer-readable medium storing instructions that, when executed by at least one processor, perform a method comprising:
identifying one or more unique tokens and bi-grams within a clustered set of search queries, the unique tokens having corresponding lengths that exceed a first threshold value;
computing edit distances for a subset of the identified tokens and bi-grams, the subset comprising tokens or bi-grams within unit length of each other token or bi-gram in the subset; and
determining that a least-frequent token or bi-gram in the subset is misspelled, when the edit distance for the least-frequent token or bi-gram falls below a second threshold value.