Document importance calculation apparatus and method

• US 8,260,788 B2
• Filed: 08/20/2009
• Issued: 09/04/2012
• Est. Priority Date: 03/16/2007
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Saito, Fumio
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US12/544,445
• Publication Number:
  US 20090313246A1
• Time in Patent Office: 1,111 Days
• Field of Search: 707/748, 707/999.005, 707/999.007
• US Class Current: 707/748
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A computer readable storage medium stores a program that allows a computer to execute a process comprising: acquiring information related to N documents; determining elements of an N×N square matrix D based on the acquired information, in order that D, a positive real number e, and a column vector u having N elements satisfy e u=D u according to the Perron-Frobenius theorem, each of the elements of D being a positive real number; initializing a column vector v having N elements, each of the elements of v corresponding to each of the elements of u; calculating a column vector w=(D v)/|D v|; updating v in the memory to w; iterating the calculating and the updating, until the v satisfies a predetermined condition; and assigning each of elements of the v to the importance of the document.

Claims

1. A non-transitory computer readable storage medium storing a document importance calculation program that allows a computer to execute a process comprising:

acquiring information related to N documents;

determining elements of an N×

N square matrix D based on the acquired information, in order that D, a positive real number e, and a column vector u having N elements satisfy e u=D u according to the Perron-Frobenius theorem, each of the elements of D being a positive real number, each of the elements of u corresponding to an importance of each of the N documents;

initializing a column vector v having N elements so as to store v in a memory, each of the elements of v corresponding to each of the elements of u;

calculating a column vector w=(D v)/|D v|;

updating v in the memory to w;

iterating the calculating of w and the updating of v, until the updated v satisfies a predetermined condition, so as to obtain the updated v being an approximation of u; and

assigning each of elements of the updated v to the importance of a corresponding document.

2. The non-transitory computer readable storage medium according to claim 1, wherein

the information includes any of a link relationship among the N documents, a creation date of each of the N documents, an evaluation result for each of the N documents by a referrer, and a frequency of references to each of the N documents.

3. The non-transitory computer readable storage medium according to claim 1, wherein

the determining calculates a value of an element of D in the m-th row and n-th column, according to the information related to an m-th document in the N documents or the information related to the m-th and n-th documents in the N documents.

4. The non-transitory computer readable storage medium according to claim 1, wherein

the predetermined condition is that a norm of a difference between v before the updating and v after the updating is smaller than a predetermined threshold value.

5. The non-transitory computer readable storage medium according to claim 1, wherein

the acquiring receives the information from a storage via a network.

6. The non-transitory computer readable storage medium according to claim 1, wherein

the information includes a creation date of an m-th document of the N documents, and

the determining determines a value of an element of D in the m-th row and n-th column according to a predetermined relationship that the determined value increases with increasing the creation date of the m-th document.

7. The non-transitory computer readable storage medium according to claim 1, wherein

the information includes evaluation results for an m-th document of the N documents,

the determining selects from the evaluation results specific evaluation results satisfying a predetermined criterion, counts the number of the specific evaluation results, and determines a value of an element of D in the m-th row and n-th column in D according to a predetermined relationship that the determined value increases with increasing the counted number.

8. The non-transitory computer readable storage medium according to claim 1, wherein

the information includes a frequency of references to an m-th document of the N documents, and

the determining determines a value of an element of D in the m-th row and n-th column according to a predetermined relationship that the determined value increases with increasing the frequency.

9. The non-transitory computer readable storage medium according to claim 1, wherein

the information includes a link relationship of an m-th document to another document, and

when the link relationship indicates a link from an n-th document to the m-th document, the determining increases a value of an element of D in the m-th row and n-th column.

10. A document importance calculation apparatus comprising:

a processor coupled to a memory, wherein the processor is programmed to execute a process comprising;

acquiring information related to N documents;

determining elements of an N×

N square matrix D based on the acquired information, in order that D, a positive real number e, and a column vector u having N elements satisfy e u=D u according to the Perron-Frobenius theorem, each of the elements of D being a positive real number, each of the elements of u corresponding to an importance of each of the N documents;

initializing a column vector v having N elements so as to store v in the memory, each of the elements of v corresponding to each of the elements of u,

calculating a column vector w=(D v)/|D v|,

updating v in the memory to w,

iterating the calculating of w and the updating of v, until the updated v satisfies a predetermined condition, so as to obtain the updated v being an approximation of u, and

assigning each of elements of the updated v to the importance of a corresponding document.

11. The document importance calculation apparatus according to claim 10, wherein

the information includes any of a link relationship among the N documents, a creation date of each of the N documents, an evaluation result for each of the N documents by a referrer, and a frequency of references to each of the N documents.

12. The document importance calculation apparatus according to claim 10, wherein

a matrix determination section calculates a value of an element of D in the m-th row and n-th column, according to the information related to an m-th document in the N documents or the information related to the m-th and n-th documents in the N documents.

13. The document importance calculation apparatus according to claim 10, wherein

the predetermined condition is that a norm of a difference between v before the updating and v after the updating is smaller than a predetermined threshold value.

14. The document importance calculation apparatus according to claim 10, wherein

an acquiring section receives the information from a storage via a network.

15. The document importance calculation apparatus according to claim 10, wherein

the information includes a creation date of an m-th document of the N documents, and

a matrix determination section determines a value of an element of D in the m-th row and n-th column according to a predetermined relationship that the determined value increases with increasing the creation date of the m-th document.

16. The document importance calculation apparatus according to claim 10, wherein

the information includes evaluation results for an m-th document of the N documents,

a matrix determination section selects from the evaluation results specific evaluation results satisfying a predetermined criterion, counts the number of the specific evaluation results, and determines a value of an element of D in the m-th row and n-th column in D according to a predetermined relationship that the determined value increases with increasing the counted number.

17. The document importance calculation apparatus according to claim 10, wherein

the information includes frequency of references to an m-th document of the N documents, and

a matrix determination section determines a value of an element of D in the m-th row and n-th column according to a predetermined relationship that the determined value increases with increasing the frequency.

18. The document importance calculation apparatus according to claim 10, wherein

the information includes a link relationship of an m-th document to another document, and

when the link relationship indicates a link from an n-th document to the m-th document, the matrix determination section increases a value of an element of D in the m-th row and n-th column.

19. A document importance calculation method comprising:

acquiring information related to N documents;

determining elements of an N×

n square matrix D based on the acquired information, in order that D, a positive real number e, and a column vector u having N elements satisfy e u=D u according to the Perron-Frobenius theorem, each of the elements of D being a positive real number, each of the elements of u corresponding to an importance of each of the N documents;

initializing a column vector v having N elements so as to store v in a memory, each of the elements of v corresponding to each of the elements of u;

calculating a column vector w=(D v)/|D v|;

updating v in the memory to w;

iterating the calculating of w and the updating of v, until the updated v satisfies a predetermined condition, so as to obtain the updated v being an approximation of u; and

assigning each of elements of the updated v to the importance of a corresponding document.

20. The document importance calculation method according to claim 19, wherein

the information includes any of a link relationship among the N documents, a creation date of each of the N documents, an evaluation result for each of the N documents by a referrer, and a frequency of references to each of the N documents.