SEARCH ENGINE AND METHOD WITH IMPROVED RELEVANCY, SCOPE, AND TIMELINESS

• US 20110173181A1
• Filed: 03/25/2011
• Published: 07/14/2011
• Est. Priority Date: 04/24/2003
• Status: Active Grant

• Current Assignee: William I. Chang
• Original Assignee: William I. Chang
• Inventors: Chang, William I.
• Granted Patent: US 8,645,345 B2
• Time in Patent Office: Days
• US Class Current: 707/711
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results

Abstract

A search engine and a method achieve timeliness of documents returned in a search result by a relevancy feedback mechanism driven by the frequency in which a URL is returned in recent searches. The relevancy feedback mechanism includes one or more random processes which determine whether or not a cached or indexed web page associated with a URL in the search result should be refreshed. In addition, the random processes also determine whether or not hyperlinks in the cached or indexed web page should be followed to access related web pages. Accesses of web pages resulting from the operations of the random processes are used to update any document index maintained by the search engine. Relevancy scoring functions implemented in look-up tables are also disclosed. A more accurate relevancy scoring function is achieved using a lexicon based on anchortexts of extracted hyperlinks of web documents.

Claims

1. A method for providing a training set to build a statistical relevancy scoring function to be used in a search engine, comprising:

(a) identifying an initial set of hypertext documents in a collection of documents as a training set of relevant documents;

(b) identifying hyperlinks included in each hypertext document of the training set; and

(c) including the hypertext documents pointed to by the identified hyperlinks.

2. The method of claim 1, further comprising;

(d) identifying the anchortexts associated with the identified hyperlinks; and

(e) including the identified anchortexts in a lexicon.

3. The method of claim 2, further comprising including in the lexicon terms input by the user in search queries.

4. The method as in claim 2, further comprising ascertaining, using an independent method, the relevance of the terms in the lexicon.

5. The method of claim 2, wherein the lexicon includes terms consisting more than one word.

6. The method of claim 2, further comprising clustering terms in the lexicon.

7. The method of claim 1, further comprising repeating steps (b)-(e).

8. The method of claim 1, wherein the collection of documents comprise documents identified by search queries processed by the search engine.

9. The method of claim 1, wherein the training set is used to tune a scoring function, the scoring function assigning a value to each document in the corpus for each term in the lexicon.

10. The method of claim 9, wherein the scoring function is determined in part by a term frequency, the term frequency being related to the frequency of occurrence in the document of the term.

11. The method of claim 10, wherein the scoring function is determined in part by a document frequency, the document frequency being related to the number of documents in the collection that include the term.

12. The method of claim 11, further comprises providing a look-up table for accessing the assigned values of the scoring function, indexed by a document frequency and a term frequency.

13. The method of claim 12, wherein the assigned value of the scoring function is a product of the document frequency and the term frequency.

14. The method of claim 12, wherein the assigned value of the scoring function is a sum of the logarithm of the document frequency and the logarithm of the term frequency.

15. The method of claim 9, wherein the scoring function is determined in part by a document frequency, the document frequency being related to the number of documents in the collection that include the term.

16. A method for providing a relevancy scoring function for scoring documents in a search result, comprising:

compiling a lexicon including tei s used in search queries that are input to a search engine; and

for each term in the lexicon;

identifying from a corpus of documents those documents in which the term appears;

computing a document frequency based on the relative numbers of the identified documents and the documents in the corpus; and

computing a term frequency for each identified document based on the number of times the term appears in the document.

17. The method of claim 16, further comprising creating a look-up table for the relevancy scoring function for each document and each tenn, indexed by a document frequency and a term frequency.

18. The method as in claim 17, further comprising smoothing or interpolating the adjacent entries of the look-up table.

19. The method of claim 16, wherein the relevancy scoring function for each document and each term is a function of both the document frequency and the term frequency in a correlated manner.

20. The method of claim 16, wherein the relevancy scoring function for each document and each term represents a probability that the document is relevant to the term.

21. The method of claim 16, wherein the relevancy scoring function is compiled by tallying a number of times that the document is adjudged to be relevant to an included term and the number of times the document is adjudged to be not relevant to the included term.

22. The method of claim 21, wherein the documents adjudged are each referenced by a hyperlink in which the included term appears in the anchortext of the hyperlink.

23. The method of claim 21, wherein the included term is selected from search queries submitted to the search engine.

24. The method of claim 21, wherein the included term is provided by a user.

25. The method of claim 16, further comprising:

computing the term frequency for each of the identified documents; and

computing the relevancy scoring function for each document and each term based the term frequency for the term in the document.

26. The method of claim 16, wherein the lexicon and the corpus are deemed a set of terms and known relevant documents for each term.

27. The method as in claim 16, wherein the relevancy scoring function is derived from two scoring functions.

28. The method as in claim 25, wherein when the search result is responsive to a query including more than one term from the lexicon, a document returned in the search result is assigned the sum of all values of the relevancy scoring function associated with all the terms from the lexicon included in the query.

29. The method claim 25, wherein the relevancy scoring function is compiled statistically using the entire corpus.

30. The method as in claim 25, wherein the relevancy scoring function is compiled statistically using a selected fraction of the corpus.