Systems and methods of retrieving topic specific information

• US 20060074910A1
• Filed: 09/16/2005
• Published: 04/06/2006
• Est. Priority Date: 09/17/2004
• Status: Abandoned Application

• Current Assignee: Become Incorporated (Connexity, Inc.)
• Original Assignee: Become Incorporated (Connexity, Inc.)
• Inventors: Yun, Yeogirl, Kaul, Rohit, Kadluczka, Marcin, Kim, Seong-Gon
• Application Number:
  US11/229,090
• Publication Number:
  US 20060074910A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06F 16/907 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• 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

Abstract

The present invention provides systems and methods of searching web pages relevant to a specific topic based on quality of individual pages. The rank of a page for a keyword may be a combination of analytic rank and editorial rank. The analytic rank of a page may be calculated by combining intrinsic and extrinsic ranks. Intrinsic rank is a measure of relevancy of a page to a given keyword as claimed by an author of the page, while extrinsic rank is a measure of the relevancy of a page on a given keyword as indicated by other pages. The former may be obtained from an analysis of keyword matching in various parts of the page while the latter is obtained from context-sensitive connectivity analysis of the link structure of the entire Internet. Methods are described to solve the self-consistent equation satisfied by the page-weights and site-weights in a very efficient iterative way. The ranking mechanism for multi-word query is also described.

Claims

1. A computer-implemented method of ranking the relevancy of a collection of hypertext pages to a topic specific keyword-based query, comprising:

calculating an analytic rank of a page;

calculating an editorial rank of the page; and

calculating a rank of the page by combining the analytic rank and the editorial rank.

2. The method of claim 1, wherein the analytic rank is a function of an intrinsic rank and an extrinsic rank of the page.

3. The method of claim 2, wherein the intrinsic rank is a function of a content score and a page popularity score of the page.

4. The method of claim 3, wherein the content score is a function of frequency, location, or font size of a keyword in the page.

5. The method of claim 3, wherein the page popularity score of the page is a function of a page-weight of the page and a site-weight of a site.

6. The method of claim 5, wherein the page-weight is defined as a probability of a user visiting the page when traveling in the collection of hypertext pages in a random fashion.

7. The method of claim 5, wherein the page-weight is obtained as a sum of a product of a link-weight of each inbound link to the page and a page-weight of an originating page.

8. The method of claim 5, wherein the page-weight is computed by:

constructing a connectivity graph, which represents the collection of hypertext pages and a link structure between the pages;

adding a page-weight reservoir with virtual inbound links from each of the pages in the collection of hypertext pages and outbound links to a few selected authoritative web pages; and

summing all products of each inbound link-weight with the page-weight of an originating page providing the inbound link.

9. The method of claim 5, further comprising computing the page-weights by:

initializing a page-weight vector to a constant;

constructing a connectivity graph representative of a link structure of the collection of hypertext pages;

computing an output page-weight vector from an input page-weight vector and the connectivity graph; and

comparing the output page-weight vector with the input page-weight vector for convergence, and if convergence is reached, writing the output page-weight vector in a page-weight database, and if not, mixing the input and output page-weight vectors to generate a new input page-weight vector and repeating until convergence is reached.

10. The method of claim 7, wherein the link-weight is defined as a probability of a user randomly choosing the link to visit other pages when traveling in the collection of hypertext pages.

11. The method of claim 7, wherein the link-weight of each inbound links has a uniform value corresponding to a reciprocal of a total number of links outbound from an originating page.

12. The method of claim 7, wherein the link-weight has a variable value, which depends on a number of outbound links, an offset of the link, a size of a paragraph where the link is located, or whether the link is an external or internal link.

13. The method of claim 8, wherein a link-weight of an outbound virtual link to reservoir is a globally fixed value.

14. The method of claim 8, wherein a link-weight of an outbound virtual link to reservoir is a variable value depending on a number of total outbound links.

15. The method of claim 2, wherein the extrinsic rank is a function of an anchor-weight and a page-weight of pages providing inbound links to the page.

16. The method of claim 2, wherein the extrinsic rank is obtained by summing products of an anchor-weight and a page-weight of an originating page providing each inbound link.

17. The method of claim 15, wherein the anchor-weight is a function of inbound link-weights and a keyword being present in an anchor text, in a vicinity of the anchor text, or in text related to a topic of the anchor text.

18. The method of claim 15, wherein the page-weight is defined as a probability of a user randomly visiting a page in the collection of hypertext pages.

19. The method of claim 15, wherein the page-weight is obtained by summing products of a link-weight of each inbound link to the page and the page-weight of an originating page providing the inbound links.

20. The method of claim 15, wherein the page-weight is computed:

constructing a connectivity graph, which represents the collection of hypertext pages and a link structure between the pages;

adding a page-weight reservoir with virtual inbound links from each of the pages in the collection of hypertext pages and outbound links to a few selected authoritative web pages; and

summing all products of each inbound link-weight with the page-weight of an originating page providing the inbound link.

21. The method of claim 15, further comprising computing the page-weights by:

initializing a page-weight vector to a constant;

constructing a connectivity graph representative of a link structure of the collection of pages;

computing an output page-weight vector from an input page-weight vector and the connectivity graph; and

comparing the output page-weight vector with the input page-weight vector for convergence, and if convergence is reached, writing the output page-weight vector in a page-weight database, and if not, mixing the input and output page-weight vectors to generate a new input page-weight vector and repeating until convergence is reached.

22. The method of claim 19, wherein the link-weight is defined as a probability of a user randomly choosing the link to visit other pages when traveling in the collection of hypertext pages.

23. The method of claim 19, wherein the link-weight of the inbound links has a uniform value corresponding to a reciprocal of a total number of links outbound from an originating page.

24. The method of claim 19, wherein the link-weight has a variable value, which depends on a number of outbound links, an offset of the link, a size of a paragraph where the link is located, or whether the link is an external or internal link.

25. The method of claim 1, wherein the collection of hypertext pages is fetched from the Internet.

26. A web search engine, comprising:

a web page database;

a crawler configured to fetch pages from the Internet and store the pages in the web page database;

a URL extractor configured to extract outbound link information from the pages;

a URL management system configured to assign an identification number to a URL of each page, and store the identification number and URL pairs in the web page database and send new URLs to the crawler to be retrieved from the Internet;

a link database;

a link extractor configured to extract anchor text and a link information from the pages and store in the link database;

an index database;

an indexer configured to parse keywords from the pages and store the keyword and URL identification pairs in the index database; and

a ranker configured to rank a page based on analytic rank and editorial rank of the page.

27. The web search engine of claim 26, wherein the ranker is further configured to determine the analytic rank from intrinsic rank and extrinsic rank of the page.

28. The web search engine of claim 27, wherein the ranker is further configured to determine the intrinsic rank from a content score and a page popularity score of the page.

29. The web search engine of claim 28, wherein the ranker is further configured to determine the content score from content information in the index database and the page-popularity computed from the page-weight of a page and site-weight of the site.

30. The web search engine of claim 29, wherein the ranker is further configured to determine the page-weight from link information in the link database, and the extrinsic rank from anchor text information in the link database and the computed page-weight.

31. The web search engine of claim 27, wherein the ranker is further configured to determine the intrinsic rank of the page based on a content score and a page-weight.

32. The web search engine of claim 27, wherein the ranker is further configured to determine the extrinsic rank of the page based on an anchor-weight of each inbound link and a page-weight of the originating page.

33. The web search engine of claim 32, wherein the ranker is further configured to determine the anchor-weight based on a link-weight and a keyword being present in anchor text or related text.

34. The web search engine of claim 27, wherein the ranker is further configured to calculate the intrinsic rank and extrinsic rank of a page for a multi-keyword query, wherein the intrinsic rank is a function of content score and a page-weight, the extrinsic rank of the page is a function of the partial extrinsic ranks and proximity values.

35. The web search engine of claim 27, further comprising a page-weight generator and a page-weight database, the page-weight generator configured to compute page-weights by initializing a page-weight vector to a constant, construct a connectivity graph representing a link structure of the fetched pages, compute an output page-weight vector from the input page-weight vector and the connectivity graph, and compare the output page-weight vector with the input page-weight vector and if convergence is reached, write the output page-weight vector in a page-weight database, and if not, mix the input and output page-weight vectors to generate a new input page-weight vector and repeat until convergence is reached.

36. A computer readable medium having embodied thereon a program, the program being executable by a machine to perform a method for ranking the relevancy of a collection of hypertext pages to a topic specific keyword-based query, the method comprising:

calculating an analytic rank of a page;

calculating an editorial rank of the page; and

calculating a rank of the page by combining the analytic rank and the editorial rank.