SYSTEMS AND METHODS FOR IMPROVED WEB SEARCHING

• US 20130268548A1
• Filed: 03/11/2013
• Published: 10/10/2013
• 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,892,592 B2
• Time in Patent Office: Days
• US Class Current: 707/765
• 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-32. -32. (canceled)

33. A computer-implemented method, comprising:

storing, in a memory device, a clustered set of search queries;

obtaining information identifying unique tokens or bi-grams within the clustered set of search queries;

determining, using at least one processor, that a least-frequent token or bi-gram of the identified tokens or bi-grams is misspelled when an edit distance for the least-frequent token or bi-gram falls below a threshold value; and

identifying, using the at least one processor, a most-frequent permutation of the misspelled token or bi-gram within the identified tokens or bi-grams as a corrected spelling for the misspelled token or bigram.

34. The method of claim 33, further comprising:

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

35. The method of claim 33, further comprising:

determining, using the at least one processor, whether a frequency of appearance associated with the most-frequent permutation of the misspelled token or bi-gram exceeds a threshold frequency; and

identifying the most-frequent permutation of the misspelled token or bi-gram as the corrected spelling when the appearance frequency exceeds the threshold frequency.

36. The method of claim 33, wherein the clustered set of search queries comprises suggested search queries related to an initial search query.

37. The method of claim 33, further comprising:

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

comparing, using the at least one processor, 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.

38. The method of claim 37, further comprising:

processing the keyword or URL portion to conform to one or more requirements of a search engine.

39. The method of claim 33, 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, using the at least one processor, 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.

40. The method of claim 39, further comprising:

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

41. The method of claim 40, further comprising:

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.

42. The method of claim 33, further comprising:

discarding the clustered set of search queries, when the identified tokens and bi-grams includes a spelling error.

43. 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 in order to;

obtain information identifying unique tokens or bi-grams within a clustered set of search queries;

determine that a least-frequent token or bi-gram of the identified tokens or bi-grams is misspelled when an edit distance for the least-frequent token or bi-gram falls below a threshold value; and

identify a most-frequent permutation of the misspelled token or bi-gram within the identified tokens or bi-grams as a corrected spelling for the misspelled token or bigram

44. The apparatus of claim 43, wherein the at least one processor is further operative with the set of instructions to:

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

45. The apparatus of claim 43, wherein the at least one processor is further operative with the set of instructions to:

determine whether a frequency of appearance associated with the most-frequent permutation of the misspelled token or bi-gram exceeds a threshold frequency; and

identify the most-frequent permutation of the misspelled token or bi-gram as the corrected spelling when the appearance frequency exceeds the threshold frequency.

46. The apparatus of claim 43, wherein the clustered set of search queries comprises suggested search queries related to an initial search query.

47. The apparatus of claim 43, wherein the at least one processor is further operative with the set of instructions 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.

48. The apparatus of claim 43, wherein the at least one processor is further operative with the set of instructions 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.

49. The apparatus of claim 48, wherein the at least one processor is further operative with the set of instructions to:

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

50. The apparatus of claim 49, wherein the at least one processor is further operative with the set of instructions 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.

51. The apparatus of claim 43, wherein the at least one processor is further operative with the set of instructions to:

discard the clustered set of search queries, when the identified tokens and bi-grams includes a spelling error.

52. A tangible, non-transitory computer-readable medium storing instructions that, when executed by at least one processor, cause the at least one processor to perform a method comprising:

storing, in a memory device, a clustered set of search queries;

obtaining information identifying unique tokens or bi-grams within the clustered set of search queries;

determining a least-frequent token or bi-gram of the identified tokens or bi-grams is misspelled when an edit distance for the least-frequent token or bi-gram falls below a threshold value; and

identifying a most-frequent permutation of the misspelled token or bi-gram within the identified tokens or bi-grams as a corrected spelling for the misspelled token or bigram.