Method for identifying related pages in a hyperlinked database

• US 20040193636A1
• Filed: 11/03/2003
• Published: 09/30/2004
• Est. Priority Date: 08/10/1998
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Black, Jeffrey Dean, Broder, Andrei Z., Henzinger, Monika R.
• Granted Patent: US 7,630,973 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method is described for identifying related pages among a plurality of pages in a linked database such as the World Wide Web. An initial page is selected from the plurality of pages. Pages linked to the initial page are represented as a graph in a memory. The pages represented in the graph are scored on content, and a set of pages is selected, the selected set of pages having scores greater than a first predetermined threshold. The selected set of pages is scored on connectivity, and a subset of the set of pages that have scores greater than a second predetermined threshold are selected as related pages.

Claims

1. A method for identifying related pages from a plurality of pages in a linked database, comprising the steps of:

selecting an initial page from the plurality of pages;

representing the initial page and pages linked to the initial page as a graph of nodes and edges in a memory;

repeatedly scoring the initial page and the pages linked to the initial page on connectivity of the pages; and

selecting a subset of the pages scored on connectivity that have scores greater than a first predetermined threshold as the related pages of the linked database.

2. The method of claim 1 further including:

scoring the pages represented in the graph on content of the pages; and

selecting the subset of the pages scored on content that have scores greater than a second predetermined threshold.

3. The method of claim 1 wherein the initial page is selected by specifying an address of the page.

4. The method of claim 1 wherein the initial page is selected by a user interface.

5. The method of claim 2 wherein the pages are scored on content by measuring the similarity of the pages to a topic.

6. The method of claim 5 wherein the topic is extracted from the initial page.

7. The method of claim 5 wherein the topic is extracted from the pages represented in the graph.

8. The method of claim 1 wherein pages linked in any direction to the initial page are represented in the graph.

9. The method of claim 8 wherein the pages represented in the graph are linked to the initial page by a predetermined number of links.

10. The method of claim 8 wherein each page represented in the graph depends on a path form each page to the initial page, the path including the length of the path and the direction of edges on the path.

11. The method of claim 8 wherein the pages represented in the graph as nodes are linked to the node representing the initial page by a number of edges that is determined dynamically.

12. The method of claim 1 performed in a client computer.

13. The method of claim 1 performed in a server computer.

14. The method of claim 1 including removing any nodes from the graph that have scores higher than a third predetermined threshold.

15. The method of claim 14 wherein the third predetermined threshold is larger than ninety percent of the score.

16. The method of claim 14 wherein the third predetermined threshold is about three times larger than a next highest scoring node.