METHOD AND DEVICE FOR EFFICIENTLY RANKING DOCUMENTS IN A SIMILARITY GRAPH

• US 20070250502A1
• Filed: 04/24/2007
• Published: 10/25/2007
• Est. Priority Date: 04/24/2006
• Status: Active Grant

• Current Assignee: Telenor Asa (Government of Norway)
• Original Assignee: Telenor Asa (Government of Norway)
• Inventors: Engo-Monsen, Kenth, CANRIGHT, Geoffrey
• Granted Patent: US 7,752,198 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 computer based 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, 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 all nonzero entries S(D,X) in a row of said similarity matrix S corresponding to an electronic document D

summing said nonzero 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.

2. The method of claim 1, further comprising:

populating a hyperlink matrix H of all inlinks;

counting inlinks to said node 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.

6. A computer program stored in a computer readable medium containing instructions configured to cause a 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 all nonzero entries S(D,X) in a row of said similarity matrix S corresponding to an electronic document D

summing said nonzero 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 method of claim 6, further comprising:

populating a hyperlink matrix H of all inlinks;

counting inlinks to said node 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 method 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 method 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 method of claim 7, wherein said at least a submatrix H'"'"' of hyperlink matrix H is an entire amount of said similarity matrix H.