Search engine and method with improved relevancy, scope, and timeliness

• US 8,645,345 B2
• Filed: 03/25/2011
• Issued: 02/04/2014
• Est. Priority Date: 04/24/2003
• Status: Expired due to Fees

• Current Assignee: Affini, Inc.
• Original Assignee: Affini, Inc.
• Inventors: Chang, William I.
• Primary Examiner(s): Choi, Yuk Ting
• Application Number:
  US13/072,455
• Publication Number:
  US 20110173181A1
• Time in Patent Office: 1,047 Days
• Field of Search: 707/999.005, 707/999.003, 707/705, 707/709, 706/45
• US Class Current: 707/705
• 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 for a document relative to selected terms in a lexicon, comprising:

in a search engine that accesses servers of documents in a computer network,

(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;

(c) including in the training set the hypertext documents pointed to by the identified hyperlinks;

(d) identifying anchortexts associated with the hypertext documents of the training set; and

(e) including the anchortexts in the lexicon;

wherein the statistical scoring function is determined by combining individual contributions to the statistical scoring function by each of the selected terms, wherein the individual contribution by each selected term is related to a term frequency, being the frequency of occurrence of that selected term in the document, and a document frequency, being the number of documents in the collection of documents that include that selected term.

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

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

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

5. The method of claim 1, further comprising clustering terms in the lexicon.

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

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

8. The method of claim 1, wherein the training set is used to tune the individual contributions by the terms in the lexicon to the statistical scoring function, wherein the individual contribution by each term in the lexicon to the statistical scoring function is computed using all documents in the training set.

9. The method of claim 1, further comprising providing a look-up table for accessing the individual contribution by each term to the statistical scoring function, indexed by document frequency and term frequency.

10. The method of claim 9, wherein the individual contribution by each selected term to the statistical scoring function is a product of the corresponding document frequency and the corresponding term frequency.

11. The method of claim 9, wherein the individual contribution by each selected term to the statistical scoring function is a sum of the logarithm of the corresponding document frequency and the logarithm of the corresponding term frequency.

12. A method for evaluating a relevancy scoring function for scoring documents in a search engine that accesses servers of documents in a computer network, comprising:

compiling a lexicon;

for each term in the lexicon;

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

computing a document frequency that relates linearly to a ratio of the number of the identified documents to the number of documents in the corpus;

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

deriving an individual contribution by the term to the relevancy scoring function using the computed term frequency and the computed document frequency;

receiving a search query including one or more terms present in the lexicon;

recovering a collection of documents based on the terms in the search query; and

evaluating the relevancy scoring function for each recovered document by combining the derived individual contributions by the terms in the search query to the relevancy scoring function.

13. The method of claim 12, further comprising creating, for each term, a look-up table for the individual contributions by the term to the relevancy scoring function, indexed by document frequency and term frequency.

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

15. The method of claim 12, wherein individual contribution by a term to the relevancy scoring function for a document represents a probability that the document is relevant to the term.

16. The method of claim 12, wherein the individual contribution by a term to the relevancy scoring function is compiled by tallying a number of times that the documents in the corpus of documents are adjudged to be relevant to the term and the number of times the documents in the corpus of the documents are adjudged to be not relevant to the included term.

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

18. The method of claim 12, wherein the lexicon and the corpus are deemed a set of terms and a set of known relevant documents for the terms included in the lexicon, respectively.

19. The method as in claim 12, wherein the individual contribution by each term to the relevancy scoring function is compiled statistically using a selected fraction of the corpus.