Linguistically aware link analysis method and system

• US 7,010,527 B2
• Filed: 08/13/2001
• Issued: 03/07/2006
• Est. Priority Date: 08/13/2001
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Alpha, Shamim A.
• Primary Examiner(s): Gaffin, Jeffrey
• Assistant Examiner(s): Veillard, Jacques
• Application Number:
  US09/928,962
• Publication Number:
  US 20030061214A1
• Time in Patent Office: 1,667 Days
• Field of Search: 707/3, 707/5, 707/10, 707/104.1, 707/205, 707/7, 707/100, 709/203, 709/218, 709/219, 715/501.1, 715/513, 345/738, 345/762, 345/848
• US Class Current: 707/749
• 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:

identifying a candidate set of pages in response to the search query;

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 for a selected page from the candidate set of pages by distributing the content-based relevance rank from one or more pages that point to the selected page where the distributing is based on a link structure of the pages including link rank values from in-coming links where the link rank values are determined from distributed values of the content-based relevance from the one or more pages that point to the selected page.

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 claim 1 where the plurality of pages are the candidate set of pages.

9. 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.

10. The method of ranking a set of candidate pages as set forth in claim 9 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.

11. The method of ranking a set of candidate pages as set forth in claim 10 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.

12. The method of ranking a set of candidate pages as set forth in claim 9 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.

13. The method of ranking a set of candidate pages as set forth in claim 12 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.

14. 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, 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; and

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

15. 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, the link rank values being based on distributing a probability of leaving a selected page from the plurality of pages identified to out-going links of the selected page.

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

an information retrieval system for identifying the candidate set of pages from a network in response to the search query;

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 selected page being obtained by combining the content-based relevance rank of the selected page with distributed values of the content-based relevance rank from one or more pages that point to the selected page where the distributed values include a link analysis rank from in-coming page links, where the link analysis rank being determined from the distributed values of content-based relevance from the one or more pages that point to the selected page.

17. The system for determining a relevance rank as set forth in claim 16 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.

18. The system for determining a relevance rank as set forth in claim 17 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.

19. The system for determining a relevance rank as set forth in claim 18 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.

20. The system for determining a relevance rank as set forth in claim 19 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.

21. 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 for a selected page representing a probability of leaving the selected 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.

22. The system for determining a relevance ranking as set forth in claim 21 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.

23. The system for determining a relevance ranking as set forth in claim 21 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.

24. The system for determining a relevance ranking as set forth in claim 23 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.

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

26. A system for determining a relevance rank for each page of a candidate set of pages identified by a search query where the system is embodied as a computer-readable medium that provides processor executable instructions, the system comprising:

an information retrieval system for identifying the candidate set of pages from a network in response to the search query;

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 selected page being obtained by combining the content-based relevance rank of the selected page with distributed values of the content-based relevance rank from one or more pages that point to the selected page where the distributed values include a link analysis rank from in-coming page links, where the link analysis rank being determined from distributed values of content-based relevance from one or more pages that point to the selected page.

27. A computer-readable medium for providing processor executable instructions operable to perform a method of determining a relevance rank of a plurality of pages identified by a search query, the method comprising:

identifying a candidate set of pages in response to the search query;

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 for a selected page from the candidate set of pages by distributing the content-based relevance rank from one or more pages that point to the selected page where the distributing is based on a link structure of the pages including link rank values from in-coming links where the link rank values are determined from distributed values of content-based relevance from one or more pages that point to the selected page.

28. A computer-readable medium for providing processor executable instructions operable to perform 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.

29. A computer-readable medium for providing processor executable instructions operable to perform a method 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, the link rank values being based on distributing a probability of leaving a selected page from the plurality of pages identified to out-going links of the selected page.