Systems and Methods for Improved Web Searching

• US 20100306229A1
• Filed: 06/01/2010
• Published: 12/02/2010
• Est. Priority Date: 06/01/2009
• Status: Active Grant

• Current Assignee: Yahoo Assets LLC
• Original Assignee: AOL Inc. (Apollo Global Management, Inc.)
• Inventors: TIMM, Sean Christopher, ACHUTHAN, Sudhir
• Granted Patent: US 8,176,069 B2
• Time in Patent Office: Days
• US Class Current: 707/767
• CPC Class Codes: G06F 16/162 Delete operations erasing in storage systems G06F3/0652
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/9032 Query formulation
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06F 16/9566 URL specific, e.g. using aliases, detecting broken or misspelled links

Abstract

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.

Claims

1. A computer-implemented method for providing suggested search queries, the method comprising the following steps, performed by one or more processors, of:

receiving an initial search query, the initial search query comprising one or more of a keyword and a portion of a URL;

processing the initial search query to conform with one or more requirements of a search engine;

comparing the processed 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, on the basis of the comparison, one or more suggested search queries related to the initial search query.

2. The method of claim 1, further comprising:

transmitting the one or more suggested search queries to a user.

3. The method of claim 1, further comprising:

processing a log of the search engine to obtain records related to previous search queries and click data;

filtering and normalizing the obtained records;

grouping the filtered and normalized records to generate one or more sets of suggested search queries;

clustering the one or more sets of suggested search queries on the basis of at least one of a frequency, a click count, and a sponsored click count; and

indexing the clustered sets of suggested search queries to generate the index of suggested search queries.

4. The method of claim 3, wherein the filtering and normalizing step comprises:

processing the obtained records to remove records related to restricted content.

5. The method of claim 4, wherein the restricted content comprises search queries and URLs associated with one or more of classified content or adult content.

6. The method of claim 4, wherein the processing step comprises:

selecting a record from the obtained records;

matching a substring of the selected record against listings of a first list, the first list comprising one or more search queries and URLs related to restricted content;

blocking the selected record when the substring of the selected record matches a listing within the first list;

matching a substring of the blocked record against listings of a second list; and

discarding the blocked record when no substring of the blocked record matches a listing within the second list.

7. The method of claim 6, further comprising:

adding at least a substring of discarded record to first list.

8. The method of claim 3, further comprising:

identifying spelling errors within each of the clustered sets of suggested search queries.

9. The method of claim 8, further comprising:

discarding a clustered set of search queries upon identification of a spelling error.

10. The method of claim 8, wherein identifying the spelling errors comprises:

identifying, for the clustered sets of suggested search queries, unique tokens of length four or more and each unique bi-gram;

generating sets of the identified tokens and bi-grams, wherein each set comprises tokens or bi-grams within length one of each other token or bi-gram in the set;

computing an edit distance for the tokens and bi-grams in the generated sets; and

identifying the least-frequent token or bi-gram in each generated set as misspelled when the edit distance for that token or bi-gram is one or less.

11. The method of claim 10, wherein the generating step comprises:

applying a Damerau-Levenshtein distance algorithm to the tokens and bi-grams of the generated sets to determine the edit distance.

12. The method of claim 10, further comprising:

determining a corrected spelling for at least one of the identified misspelled tokens or bi-grams.

13. The method of claim 12, wherein determining the corrected spelling comprises:

determining a most-frequent permutation of each of the misspelled token or bi-gram based on a correction chain associated with each of the misspelled token or bi-gram; and

identifying the most-frequent permutation of each of the misspelled token or bi-gram as the corrected spelling of the corresponding token or bi-gram.

14. The method of claim 10, further comprising:

returning the corrected spelling of at least one of the misspelled tokens or bi-grams to one or more of a user and a search engine.

15. The method of claim 3, wherein the filtering and normalizing step comprises:

filtering the obtained search query and click records based on a time stamp associated with the obtained search query and click records.

16. An apparatus, comprising:

a storage device; and

a processor coupled to the storage device, wherein the storage device stores a program for controlling the processor, and wherein the processor, being operative with the program, is configured to;

receive an initial search query, the initial search query comprising one or more of a keyword and a portion of a URL;

process the initial search query to conform with one or more requirements of a search engine;

compare the processed 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, on the basis of the comparison, one or more suggested search queries related to the initial search query.

17. The apparatus of claim 16, wherein the processor is further configured to:

transmit the one or more suggested search queries to a user.

18. The apparatus of claim 16, wherein the processor is further configured to:

processing a log of the search engine to obtain records related to previous search queries and click data;

filtering and normalizing the obtained records;

grouping the filtered and normalized records to generate one or more sets of suggested search queries;

clustering the one or more sets of suggested search queries on the basis of at least one of a frequency, a click count, and a sponsored click count; and

indexing the clustered sets of suggested search queries to generate the index of suggested search queries.

19. The apparatus of claim 18, wherein the processor configured to filter and normalize is further configured to:

process the obtained records to remove records related to restricted content.

20. The apparatus of claim 19, wherein the restricted content comprises search queries and URLs associated with one or more of classified content or adult content.

21. The method of claim 19, wherein the processor is further configured to:

select a record from the obtained records;

match a substring of the selected record against listings of a first list, the first list comprising one or more search queries and URLs related to restricted content;

block the selected record when the substring of the selected record matches a listing within the first list;

match a substring of the blocked record against listings of a second list; and

discard the blocked record when no substring of the blocked record matches a listing within the second list.

22. The method of claim 21, the processor is further configured to:

add at least a substring of discarded record to first list.

23. The method of claim 18, wherein the processor is further configured to:

identify spelling errors within the clustered sets of suggested search queries.

24. The method of claim 23, wherein the processor is further configured to:

discard a clustered set of search queries upon identification of a spelling error.

25. The method of claim 23, wherein the processor configured to identify is further configured to:

identify, for the clustered sets of suggested search queries, unique tokens of length four or more and each unique bi-gram;

generate sets of the identified tokens and bi-grams, wherein each set comprises tokens or bi-grams within length one of each other token or bi-gram in the set;

compute an edit distance for the tokens and bi-grams in the generated sets; and

identify the least-frequent token or bi-gram in each generated set as misspelled when the edit distance for that token or bi-gram is one or less.

26. The method of claim 25, wherein the processor configured to generate is further configured to:

apply a Damerau-Levenshtein distance algorithm to the tokens and bi-grams of the generated sets to determine the edit distance.

27. The method of claim 25, wherein the processor is further configured to:

determine a corrected spelling for at least one of the identified misspelled tokens or bi-grams.

28. The method of claim 27, wherein the processor configured to determine is further configured to:

determine a most-frequent permutation of each of the misspelled token or bi-gram based on a correction chain associated with each of the misspelled token or bi-gram; and

identify the most-frequent permutation of each of the misspelled token or bi-gram as the corrected spelling of the corresponding token or bi-gram.

29. The method of claim 25, wherein the processor is further configured to:

return the corrected spelling of at least one of the misspelled tokens or bi-grams to one or more of a user and a search engine.

30. The method of claim 18, wherein the processor configured to filter and normalize is further configured to:

filter the obtained search query and click records based on a time stamp associated with the obtained search query and click records.

31. A computer-readable medium storing instructions that, when executed by a processor, perform a method for providing suggested search queries, the method comprising:

receiving an initial search query, the initial search query comprising one or more of a keyword and a portion of a URL;

processing the initial search query to conform with one or more requirements of a search engine;

comparing the processed 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, on the basis of the comparison, one or more suggested search queries related to the initial search query.

32. A computer-implemented method for requesting online content based on suggested search queries, the method comprising the following steps, performed by one or more processors, of:

receiving an initial search query, the initial search query comprising one or more of a keyword and a portion of a URL;

processing the initial search query to conform with one or more requirements of a search engine;

comparing the processed search query against an index of suggested search queries, the index comprising stored search queries and related click data based on previous search queries;

identifying, on the basis of the comparison, one or more suggested search queries related to the initial search query;

generating a request for submission of online content relating to the one or more suggested search queries; and

displaying the request for submission of online content to one or more Internet users.