Method for identifying near duplicate pages in a hyperlinked database

• US 6,138,113 A
• Filed: 08/10/1998
• Issued: 10/24/2000
• Est. Priority Date: 08/10/1998
• Status: Expired due to Term

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: AltaVista Company (Apollo Global Management, Inc.)
• Inventors: Dean, Jeffrey, Henzinger, Monika R.
• Primary Examiner(s): HO, RUAY L
• Application Number:
  US09/131,469
• Time in Patent Office: 806 Days
• Field of Search: 707/1-10, 707/100-104, 707/200-206, 709/226, 711/163, 340/825.22, 340/825.44, 370/390, 370/400, 370/408
• US Class Current: 715/208
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A method is described for identifying pages that are near duplicates in a linked database. In the linked database, pages can have incoming links and outgoing links. Two pages are selected, a first page and a second page. For each selected page, the number of outgoing links is determined. The two pages are marked as near duplicates based on the number of common outgoing links for the two pages.

Claims

1. A method for identifying pages that are near duplicates in a linked database, the pages in the database having incoming links and outgoing links, comprising the steps of:

selecting a first page and a second page;

determining the outgoing links for the first page and the second page;

determining the number of outgoing links that are common for the first page and the second page;

marking the first page and the second page as near duplicate pages based on the number of common outgoing links.

2. The method of claim 1 wherein the number of common outgoing links is the intersection of the outgoing links of the first and second pages.

3. The method of claim 1 wherein the first and second pages are near duplicate pages when the ratio of the number of common outgoing links divided by the union of the outgoing links of the first and second pages is larger than a predetermined threshold.

4. The method of claim 1 wherein the first and second pages are near duplicate pages when the ratio of the number of common outgoing links divided by the total number of outgoing links is larger than a predetermined threshold.