Method and device for efficiently ranking documents in a similarity graph

• US 7,752,198 B2
• Filed: 04/24/2007
• Issued: 07/06/2010
• Est. Priority Date: 04/24/2006
• Status: Expired due to Fees

• Current Assignee: Telenor Asa (Government of Norway)
• Original Assignee: Telenor Asa (Government of Norway)
• Inventors: Canright, Geoffrey, Engo-Monsen, Kenth
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Thai; Hanh B
• Application Number:
  US11/739,492
• Publication Number:
  US 20070250502A1
• Time in Patent Office: 1,169 Days
• Field of Search: 707 3- 5, 707/102, 707/104.1, 715/234
• US Class Current: 707/723
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/382 using citations hypermedia G06F16/94
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: G06F 16/9558 Details of hyperlinks; Management of linked annotations

Abstract

A method, device and computer program product for determining an importance score for a document D in a document set by exploiting a similarity matrix/graph S or subgraph S′.

Claims

1. A link analysis method, implemented using a computer based link analysis apparatus, for determining a context-based relevance of a first electronic document of a plurality of electronic documents to remaining electronic documents of said plurality of electronic documents, comprising:

populating, using the link analysis apparatus, a weighted symmetric similarity matrix S with link weights representing a measure of similarity between pairs of said plurality of electronic documents;

determining, using the link analysis apparatus, entries S(D,X) in a row of said similarity matrix S corresponding to an electronic document D;

summing, using the link analysis apparatus, said entries of at least a submatrix S′

of similarity matrix S to produce a first importance score regarding said electronic document D; and

one of searching, navigating and ranking, using the link analysis apparatus, at least a subset of said plurality of electronic documents based on a total score including said first importance score.

2. The method of claim 1, further comprising:

populating a hyperlink matrix H of all inlinks;

counting inlinks to said document D in at least a submatrix H′

of said hyperlink matrix H and outputting a total number of counted inlinks as a second importance score;

multiplying said second importance score by a scaling factor C, where 0<

C≦

1;

adding said first and second score to form said total score.

3. The method of claim 1, wherein said at least a submatrix S′

of similarity matrix S is an entire amount of said similarity matrix S.

4. The method of claim 2, wherein said at least a submatrix S′

of similarity matrix S is an entire amount of said similarity matrix S.

5. The method of claim 2, wherein said at least a submatrix H′

of hyperlink matrix H is an entire amount of said similarity matrix H.

11. The method of claim 1, wherein the determining further comprises determining only nonzero entries S(D,X) in a row of said similarity matrix S corresponding to an electronic document D.

6. A computer readable storage medium containing stored thereon instructions that when executed by a computing device cause the computing device to execute a link analysis method for determining a context-based relevance of a first electronic document of a plurality of electronic documents to remaining electronic documents of said plurality of electronic documents, the method comprising:

populating a weighted symmetric similarity matrix S with link weights representing a measure of similarity between pairs of said plurality of electronic documents;

determining entries S(D,X) in a row of said similarity matrix S corresponding to an electronic document D;

summing said entries of at least a submatrix S′

of similarity matrix S to produce a first importance score regarding said electronic document D; and

one of searching, navigating and ranking at least a subset of said plurality of electronic documents based on a total score including said first importance score.

7. The computer readable storage medium of claim 6, further comprising:

populating a hyperlink matrix H of all inlinks;

counting inlinks to said document D in at least a submatrix H′

of said hyperlink matrix H and outputting a total number of counted inlinks as a second importance score;

multiplying said second importance score by a scaling factor C, where 0<

C≦

1;

adding said first and second score to form said total score.

8. The computer readable storage medium of claim 6, wherein said at least a submatrix S′

of similarity matrix S is an entire amount of said similarity matrix S.

9. The computer readable storage medium of claim 7, wherein said at least a submatrix S′

of similarity matrix S is an entire amount of said similarity matrix S.

10. The computer readable storage medium of claim 7, wherein said at least a submatrix H′

of hyperlink matrix H is an entire amount of said similarity matrix H.

12. The computer readable storage medium of claim 6, wherein the determining further comprises determining only nonzero entries S(D,X) in a row of said similarity matrix S corresponding to an electronic document D.