Linguistically aware link analysis method and system

• US 20030061214A1
• Filed: 08/13/2001
• Published: 03/27/2003
• Est. Priority Date: 08/13/2001
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Alpha, Shamim A.
• Granted Patent: US 7,010,527 B2
• Time in Patent Office: Days
• US Class Current: 707/7
• 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/959 Network
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method and system for determining relevance rankings for pages identified in a search query is provided. In response to the search query, an information retrieval system identifies candidate pages/documents from a network that potentially match the search query. A relevance ranking system determines a relevance value for each of candidate pages so that the most relevant pages are displayed to a user. The relevance value is based on a combination of content-based relevance values of the pages and link values determined from a link structure of the pages. A link value is a function of a probability that a user will follow the link as compared to following all other links. With the present invention, improved relevance rankings are obtained for a candidate set of pages.

Claims

1. A method of determining a relevance rank for each of a plurality of pages identified by a search query, the method comprising the steps of:

determining a content-based relevance rank for each of the pages based on a content of each page; and

adjusting the content-based relevance rank of each page based on a link structure of the pages including link rank values from in-coming links.

2. The method of determining a relevance rank as set forth in claim 1 wherein the content-based relevance rank for each page is determined from a probability value that a user will be on the page in relation to other pages of the identified pages.

3. The method of determining a relevance rank as set forth in claim 2 further including determining the link rank value for each out-going link from an associated page based on a probability of leaving the associated page.

4. The method of determining a relevance rank as set forth in claim 3 wherein the determining the link rank value step includes distributing the probability of leaving the associated page to all out-going links of the associated page weighted by the content-based relevance rank of a page referenced by the out-going link.

5. The method of determining a relevance rank as set forth in claim 4 wherein the adjusting the relevance rank step includes combining the relevance rank of a page with the link rank values of all in-coming links to the page.

6. The method of determining a relevance rank as set forth in claim 1 further including translating the content-based relevance rank for each page to a staying probability value representing a probability that a user will stay on a page.

7. The method of determining a relevance rank as set forth in claim 6 wherein the adjusting step includes adjusting the content-based relevance value for a page based on a link rank value from all in-coming links to the page.

8. The method of determining a relevance rank as set forth in claim 1 further including identifying a candidate set of pages in response to the search query.

9. A system for determining a relevance rank for each page of a candidate set of pages identified by a search query, the system comprising:

content analyzer logic for obtaining a content-based relevance rank for each of the pages based on a content of each page; and

a relevance rank analyzer for obtaining a relevance rank for each page where the relevance rank for a page being obtained by combining the content-based relevance rank of the page with a link analysis rank from in-coming page links.

10. The system for determining a relevance rank as set forth in claim 9 further including link structure logic for obtaining a link structure of the candidate set of pages to determine in-coming and out-going page links.

11. The system for determining a relevance rank as set forth in claim 10 further including a probability logic for determining a staying probability for each page being a probability that a user will stay on a given page, and for determining a leaving probability for each page being a probability that a user will leave a given page.

12. The system for determining a relevance rank as set forth in claim 11 further including link analysis logic for determining the link analysis rank for each out-going page link from the candidate set of pages, where the link analysis rank for an out-going page link from a selected page represents a probability that a user will follow the out-going page link from the selected page.

13. The system for determining a relevance rank as set forth in claim 12 wherein the link analysis logic further includes logic for distributing the leaving probability for the selected page to the out-going page links based on a ratio of the content-based relevance rank of child pages referred to by the out-going page links.

14. The system for determining a relevance rank as set forth in claim 9 further including an information retrieval system for identifying the candidate set of pages from a network in response to the search query.

15. A system for determining a relevance ranking for pages obtained from a network search query, the system comprising:

link structure logic for obtaining a link structure of the pages which identifies out-going links from each of the pages which become in-coming links to other pages;

a content analyzer for determining a content of each page;

a content relevance ranking logic for determining a content relevance rank for each page based on a content of the page in relation to the network query;

link analysis logic for determining a link ranking for each of the out-going links for each of the pages, the link ranking representing a probability of leaving an associated page by the out-going link; and

a relevance rank adjuster for determining and adjusting a relevance rank of a page by combining the content relevance rank with the link rankings associated to in-coming links for the page.

16. The system for determining a relevance ranking as set forth in claim 15 wherein the relevance rank of each page is represented by a probability of a user being on the page in relation to all pages obtained from the search query.

17. The system for determining a relevance ranking as set forth in claim 15 wherein the link analysis logic includes logic for determining a total probability of leaving a page and distributing the total probability of leaving the page to the out-going links of the page.

18. The system for determining a relevance ranking as set forth in claim 17 wherein the link analysis logic distributes the total probability of leaving the page in proportion to a relevance ranking of a child page referred to by the out-going link.

19. The system for determining a relevance ranking as set forth in claim 15 further including an information retrieval system for identifying a candidate set of pages from a network in response to the network search query.

20. A method of ranking a set of candidate pages in response to a search query, the method comprising the steps of:

identifying the candidate pages from a network that potentially match the search query;

assigning a content-based relevance rank to each candidate page based on a probability that a user will stay on a selected candidate page;

adjusting the content-based relevance rank of each candidate page where the content-based relevance rank for a selected candidate page is influenced by a quantity and relevance of candidate pages that point to the selected candidate page; and

ranking the candidate pages based on the adjusted content-based relevance rank.

21. The method of ranking a set of candidate pages as set forth in claim 20 further including determining a link value for each out-going link from the candidate pages in accordance with a probability that the user will leave a selected candidate page by following a selected out-going link.

22. The method of ranking a set of candidate pages as set forth in claim 21 wherein the probability of following an out-going link from the selected candidate page is a function of the relevance of all referred pages and the relevance of the selected candidate page.

23. The method of ranking a set of candidate pages as set forth in claim 20 wherein adjusting includes distributing, to the selected candidate page, the quantity and relevance of candidate pages that point to the selected candidate page based on a link structure of the candidate pages.

24. The method of ranking a set of candidate pages as set forth in claim 23 wherein the distributing includes determining a link value for a page link as a probability of following the page link based on a weighted probability of leaving a page by the page link and a relevance of a page being pointed to by the page link.

25. The method of ranking a set of candidate pages as set forth in claim 20 wherein the adjusting includes determining, for each candidate page, a probability of a user being on a page in relation to all candidate pages, the probability of a user being on a page being set as the adjusted content-based relevance rank for that page.