DOCUMENT SIMILARITY SCORING AND RANKING METHOD, DEVICE AND COMPUTER PROGRAM PRODUCT

• US 20100131515A1
• Filed: 11/13/2009
• Published: 05/27/2010
• Est. Priority Date: 02/08/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,844,595 B2
• Time in Patent Office: Days
• US Class Current: 707/742
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A device, computer program product and a method for computing the similarity of a set of documents that avoids the large, wasted computational effort involved in calculating very small similarity scores by using thresholds to stop a similarity calculation between documents, thus ensuring that, with high probability, all document pairs with higher similarity than the thresholds have been found.

Claims

1. A computer-based method of electronic document searching, navigating or retrieving documents in a set of electronic documents, comprising:

analyzing the set of documents based on at least a portion of a similarity graph and at least a portion of a hyperlink graph constructed from hyperlinks between the set of documents, wherein;

said step of analyzing the set of documents using said at least a portion of the similarity graph and at least a portion of a hyperlink graph includes one of;

combining the at least a portion of the similarity graph and the at least a portion of the hyperlink graph into a single, hybrid graph by adding at least a portion of the hyperlink matrix to the at least a portion of the similarity matrix, and determining a score for the documents in the set of documents from an eigenvector of a matrix of the hybrid graph, the hybrid graph comprising one of;

the whole similarity graph and a subgraph of the hyperlink graph, and

a subgraph of the similarity graph and the whole hyperlink graph; and

obtaining two eigenvectors of scores, one from each of the at least a portion of the similarity graph and the at least a portion of the hyperlink graph, and determining a net score for each document in the set of documents from a weighted combination of said two eigenvectors of scores, said method of searching, navigating or retrieving further comprising;

ranking at least one of the set of documents against another of the set documents with corresponding document scores; and

at least one of electronically searching said set of electronic documents, navigating said set of electronic documents, and retrieving from said set of electronic documents based on said ranking.

2. The method of claim 1, further comprising:

building said similarity graph, comprising;

representing the similarity graph as a similarity matrix for said set of electronic documents, said step of representing comprising;

electronically constructing and storing a word corpus from said set of electronic documents, each document in said set of electronic documents having a corresponding document ID;

electronically constructing an inverted index, based on the electronic corpus and set of electronic documents;

for each word in the inverted index, obtaining a plurality of document similarity scores by;

electronically sorting document IDs of said set of electronic documents according to a word similarity score to form a sorted set of document IDs, each document ID in said sorted set corresponding uniquely to a document in said set of electronic documents, where said word appears in each document represented in said sorted set, said sorted set being an index word document list, and

electronically calculating a document similarity score between each pair of documents identified in said index-word document list, for which said pair of documents meets a set of threshold criteria;

collecting, into said similarity matrix, the document similarity scores calculated;

assigning a value from said similarity matrix as a link weight between a corresponding two documents identified in said index-word document list; and

treating all remaining matrix elements of said similarity matrix as zero.

3. The method of claim 1, further comprising:

identifying a principal eigenvector of a link structure matrix; and

assigning, for each document, a corresponding document weight in the principal eigenvector as a corresponding document link-analysis score.

4. The method of claim 1, further comprising:

when hyperlinks exist between said electronic documents, performing matrix addition of said similarity matrix with an adjacency matrix corresponding to an intra-document hyperlink structure, where said matrix addition comprises one of;

adding a directed hyperlink structure matrix to said similarity matrix to form a hybrid link structure matrix; and

adding a directed hyperlink structure matrix to said similarity matrix to form said hybrid link structure matrix, wherein one of said directed hyperlink structure matrix and said similarity matrix is weighted with a weight factor.

5. The method of claim 4, further comprising:

performing link analysis on said hybrid link structure matrix, and where said step of performing link analysis comprises

identifying a principal eigenvector of said hybrid link structure matrix, and

assigning, for each document, a corresponding document weight in the principal eigenvector as a document link-analysis score.

6. The method of claim 1, further comprising:

performing link analysis, wherein said step of performing link analysis comprises;

identifying a principal eigenvector of said similarity matrix;

identifying a principal eigenvector of a directed hyperlink structure matrix; and

one of

adding said principal eigenvector of said similarity matrix to said principal eigenvector of a directed hyperlink structure matrix to form a net link-analysis score for each document; and

adding said principal eigenvector of said similarity matrix to said principal eigenvector of a directed hyperlink structure matrix to form a net link-analysis score for each document, wherein one of said principal eigenvector of said similarity matrix and said principal eigenvector of a directed hyperlink structure matrix is weighted with a weight factor.

7. The method of claim 1, further comprising:

performing link analysis over one of a whole graph and a subgraph of said similarity matrix;

identifying a principal eigenvector of one of a whole graph and a subgraph of said similarity matrix; and

assigning, for each document, a corresponding document weight in said principal eigenvector as a corresponding document link-analysis score.

8. The method of claim 4, wherein said matrix addition comprises one of:

adding one of a whole graph and a subgraph of a directed hyperlink structure matrix to one of a whole graph and a subgraph of said similarity matrix to form a hybrid link structure matrix; and

adding one of a whole graph and a subgraph of a directed hyperlink structure matrix to one of a whole graph and a subgraph of said similarity matrix to form said hybrid link structure matrix, wherein one of said directed hyperlink structure matrix to said similarity matrix is weighted with a weight factor.

9. The method of claim 8, further comprising:

performing link analysis on said hybrid link structure matrix, and where said step of performing link analysis comprises identifying a principal eigenvector of said hybrid link structure matrix, and where, for each document, a corresponding document weight in the principal eigenvector is assigned as a corresponding link-analysis score.

10. The method of claim 6, wherein said step of identifying a principal eigenvector of said similarity matrix comprises:

identifying a principal eigenvector of one of a whole graph and a subgraph of said similarity matrix, and wherein said step of identifying a principal eigenvector of said directed hyperlink structure matrix comprises identifying a principal eigenvector of one of a whole graph and a subgraph of said directed hyperlink structure matrix.

11. The method of claim 7, wherein said link-analysis score for a document indicates a quality or importance of said document.

12. The method of claim 9, wherein said link-analysis score for a document indicates a quality or importance of said document.

13. The method of claim 10, wherein said link-analysis score for a document indicates a quality or importance of said document.

14. The method of claim 1, wherein the similarity graph is constructed with a method which avoids calculating zero or low values of similarity.

15. A computer readable medium including stored thereon a computer program product containing instructions configured to cause a computing device to execute the method recited in one of claims 1-14.

16. The method of claim 1, wherein at lest one of the at least a portion of the hyperlink matrix and the at least a portion of the similarity matrix are multiplied with a weight factor prior to combination into a single, hybrid graph.