IP Library › Granted Patent US 8,176,069

Granted Patent B2

US 8,176,069 · App. 12/791,481 · Granted May 8, 2012

Systems and methods for improved web searching

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 8,176,069
App. No.: 12/791,481
Granted: May 8, 2012
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

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 (106)

1. A computer-implemented method for providing suggested search queries, 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;

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

identifying, using a processor, spelling errors within the clustered sets of suggested search queries, 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 the generated sets comprise 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 at least one of the generated sets as misspelled, when the edit distance for that token or bi-gram is one or less.

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 , wherein identifying the clustered sets of suggested search queries comprises:

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 1 , further comprising:

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

9. The method of claim 1 , 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.

10. The method of claim 1 , further comprising:

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

11. The method of claim 10 , 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.

12. The method of claim 1 , 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.

13. 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.

14. 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;

identify, on the basis of the comparison, one or more clustered sets of suggested search queries related to the initial search query; and

identify spelling errors within the clustered sets of suggested search queries, wherein the processor 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 at least one of the generated sets as misspelled, when the edit distance for that token or bi-gram is one or less.

15. The apparatus of claim 14 , wherein the processor is further configured to:

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

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

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

filter and normalize the obtained records;

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

cluster 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

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

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

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

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

19. The apparatus of claim 17 , 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.

20. The apparatus of claim 19 , the processor is further configured to:

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

21. The apparatus of claim 14 , wherein the processor is further configured to:

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

22. The apparatus of claim 14 , 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.

23. The apparatus of claim 14 , wherein the processor is further configured to:

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

24. The apparatus of claim 23 , 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.

25. The apparatus of claim 14 , 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.

26. The apparatus of claim 16 , 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.

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