Systems and methods of retrieving relevant information

• US 20030208482A1
• Filed: 06/03/2003
• Published: 11/06/2003
• Est. Priority Date: 01/10/2001
• Status: Abandoned Application

• Current Assignee: Anurag Dod, Brian S Kim, Michael W. Kim, Sudong Chung, Yeogirl Yun
• Original Assignee: Anurag Dod, Brian S Kim, Michael W. Kim, Sudong Chung, Yeogirl Yun
• Inventors: Yun, Yeogirl, Kim, Michael, Kim, Brian S., Dod, Anurag, Chung, Sudong
• Application Number:
  US10/454,452
• Publication Number:
  US 20030208482A1
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

The present invention provides systems and methods of retrieving the pages according to the quality of the individual pages. The rank of a page for a keyword is a combination of intrinsic and extrinsic ranks. Intrinsic rank is the measure of the relevancy of a page to a given keyword as claimed by the 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 is obtained from the analysis of the keyword matching in various pads of the page while the latter is obtained from the context-sensitive connectivity analysis of the links connecting the entire Web. The present invention also provides the methods to solve the self-consistent equation satisfied by the page weights iteratively in a very efficient way. The ranking mechanism for multi-word query is also described. Finally, the present invention provides a method to obtain the more relevant page weights by dividing the entire hypertext pages into distinct number of groups.

Claims

1. A Web search engine, comprising:

a Web page database;

a crawler to fetch pages from the Web and store the pages in the Web page database;

a link extractor to extract link information from the pages;

a URL management system to assign an identification number to the 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 Web;

anchor text and link database;

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

indexed database;

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

a ranker to rank a page based on intrinsic rank and extrinsic rank of the page.

2. The Web search engine of claim 1, wherein the ranker determines the intrinsic rank from content information in the indexed database and the page weight computed from the link information in anchor text and link database, and the extrinsic rank from the anchor text information in the anchor text and link database and the computed page weight.

3. The Web search engine of claim 1, wherein the ranker determines the intrinsic rank of the page based on the content score and the page weight.

4. The Web search engine of claim 1, wherein the ranker determines the extrinsic rank of the page based on the anchor weight of each inbound link and the page weight of the originating page.

5. The Web search engine of claim 1, wherein the ranker determines the anchor weight based on the link weight and the keyword being present in the anchor text or related text.

6. The Web search engine of claim 1, wherein the ranker calculates 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 the page weight, the extrinsic rank of the page is a function of the partial extrinsic ranks and proximity values.

7. The Web search engine of claim 1, further comprising a page weight generator and a page weight database, computing page weights by initializing a page weight vector to a constant, constructing a connectivity graph representing the link structure of the fetched pages, computing an output page weight vector from the input page weight vector and the connectivity graph, and comparing the output page weight vector with the input page weight vector 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.

8. A computer system for ranking search results from a query on a collection of hypertext pages, comprising:

a crawler to fetch pages from the collection of hypertext pages;

a link extractor to extract page locator information from the fetched pages;

a page locator management system for storing and retrieving the page locator information;

a page database to store the pages;

an indexer to parse keywords from the pages and store the keyword page locator pairs in the indexed database;

an anchor text and link extractor to extract the anchor text and link structures from the pages;

an anchor text and link database, wherein the anchor text and link extractor writes the anchor text and link structures into the anchor text and link database; and

a ranker to assign a rank value to a page based on intrinsic and extrinsic rank.

9. The system of claim 8, wherein the ranker assigns an intrinsic rank to the page based on a combination of content score and page weight.

10. The system of claim 8, wherein the ranker assigns the content score to the page for a keyword based on a combination of location, frequency, and/or font size of the keyword in the page.

11. The system of claim 8, wherein the ranker assigns a page weight to the page as the probability of a searcher visiting the page when traveling in the collection of hypertext pages in a random fashion.

12. The system of claim 8, wherein the ranker assigns a uniform value corresponding to the reciprocal of the total number of links outbound from an originating page to link weight.

13. The system of claim 8, wherein the ranker assigns link weight based on location of the link.

14. The system of claim 8, wherein the ranker assigns an extrinsic rank to the page for a given keyword as a combination of anchor weight of the links from other pages and the page weight of referring pages.

15. The system of claim 8, wherein the ranker assigns a rank value to a page for a multi-keyword query as a combination of intrinsic rank and extrinsic rank for the multi-keyword.

16. The system of claim 8, wherein the ranker assigns an intrinsic rank to a page for a multi-keyword query as a combination of content score and page weight.

17. The system of claim 8, wherein the ranker assigns a content score to a page for a multi-keyword query as a combination of content score based on intersection of the given keywords and proximity value.

18. The system of claim 8, wherein the ranker assigns a partial extrinsic rank for each variation of identical anchor text.

19. The system of claim 8, wherein the ranker assigns a extrinsic rank to a page for a multi-keyword query as a combination of partial extrinsic rank of identical anchor text and proximity values in each anchor text.

20. The system of claim 8, wherein the ranker obtains a link connectivity graph of the pages.

21. The system of claim 8, wherein the ranker obtains the rank values from the link connectivity graph.

22. The system of claim 8, wherein the ranker calculates the page weight by iterative numerical procedure.

23. The system of claim 8, wherein the ranker accelerates the convergence of the iterative numerical procedure in obtaining connectivity rank scores.

24. The system of claim 8, wherein the ranker calculates rank values by dividing the pages into distinct number of groups.

25. The system of claim 8, further comprising a rate controller to control the rate of request for page retrieval.

26. The system of claim 8, wherein the Web page database stores the pages in a fixed record large enough to contain a predetermined percentage of all of the pages, wherein if the page is smaller, the fixed record has some empty space, and if the page is larger, the Web page database stores as much of the page as possible in the fixed record and the rest in a record file.