Retrieving and ranking of documents from database description

• US 20020032682A1
• Filed: 06/12/2001
• Published: 03/14/2002
• Est. Priority Date: 06/12/2000
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Kobayashi, Mei, Samukawa, Hikaru, Malassis, Loic
• Granted Patent: US 6,678,690 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method, a computer system, and a program product for retrieving and/or ranking documents in a database. The method comprising steps of, providing a document matrix derived from the documents, the matrix including numerical elements derived from the attributes; providing a covariance matrix derived from the document matrix; executing singular value decomposition of the covariance matrix so as to obtain the following formula:K=V┘©┘V^T, wherein K represents the covariance matrix, V represents the matrix consisting of eigenvectors, © represents a diagonal matrix, and V^T represents a transpose of the matrix V; reducing a dimension of the matrix V using a predetermined number of eigenvectors included in the matrix V, the eigenvectors including an eigenvector corresponding to the largest singular value; reducing a dimension of the document matrix using the dimension reduced matrix V; and retrieving and/or ranking the documents in the database by computing the scalar product between the dimension reduced document matrix and a query vector.

Claims

1. A method for retrieving and/or ranking documents in a database, the documents including attribute data, said method comprising steps of,

providing a document matrix from said documents, said matrix including numerical elements derived from said attribute data;

providing covariance matrix from said document matrix;

executing singular value decomposition of said covariance matrix so as to obtain the following formula;

K−

v┘

©

┘

V^T,

wherein K represents said covariance matrix, V represents the matrix consisting of eigenvectors, ©

represents a diagonal matrix, and V^T represents a transpose of the matrix V;

reducing a dimension of said matrix V using predetermined numbers of eigenvectors included in said matrix V, said eigenvectors including an eigenvector corresponding to the largest singular value;

reducing a dimension of said document matrix using said dimension reduced matrix V; and

retrieving and/or ranking said documents in said database by computing a scalar product between said dimension reduced document matrix and a query vector.

2. The method according to claim 1, wherein said attributes include at least one keyword and/or a time stamp.

3. The method according to claim 1, wherein said covariance matrix is computed by the following formula;

K=B−

X_bar┘

X_bar^T,

wherein K represents said covariance matrix, B represents a momentum matrix, X_bar represents a mean vector and X_bar^T represents a transpose thereof.

4. The method according to claim 1, wherein said predetermined numbers are 15-25% of total of the eigenvectors of said covariance matrix.

5. The method according to claim 1, wherein said method further includes a switching step from dimension reduction using said document matrix directly to dimension reduction using said covariance matrix depending on predetermined computation time, so that said dimension reduction using said covariance matrix is executed when said dimension reduction of said document matrix using eigenvectors thereof computed from said document matrix is not completed within said predetermined computation time.

6. The method according to claim 1, further comprising adding documents to said database.

7. A computer system for executing a method for retrieving and/or ranking documents in a database, the documents including attribute data, said computer system having apparatus for:

providing a document matrix from said documents, said matrix including numerical elements derived from said attribute data;

providing a covariance matrix from said document matrix;

executing singular value decomposition of said covariance matrix so as to obtain the following formula;

K=V┘

©

┘

V^T,

wherein K represents said covariance matrix, V represents the matrix consisting of eigenvectors, ©

represents a diagonal matrix, and V^T represents a transpose of the matrix V;

reducing a dimension of said matrix V using predetermined numbers of eigenvectors included in said matrix V, said eigenvectors including an eigenvector corresponding to the largest singular value;

reducing a dimension of said document matrix using said dimension reduced matrix V; and

retrieving and/or ranking said documents in said database by computing a scalar product between said dimension reduced document matrix and a query vector.

8. The computer system according to the claim 7, wherein said attributes include at least one keyword and/or a time stamp.

9. The computer system according to the claim 7, wherein said covariance matrix is computed by the following formula;

K=B−

X_bar┘

X_bar^T

wherein K represents said covariance matrix, B represents a momentum matrix, X_bar represents a mean vector and X_bar^T represents a transpose thereof.

10. The computer system according to claim 7, wherein said predetermined numbers are 15-25 % of total of the eigenvectors of said covariance matrix.

11. The computer system according to claim 7, wherein said system further includes apparatus for switching from dimension reduction using said document matrix directly to dimension reduction using said covariance matrix depending on predetermined computation time, so that said dimension reduction using said covariance matrix is executed when said dimension reduction of said document matrix using eigenvectors thereof computed from said document matrix, is not completed within said predetermined computation time.

12. The computer according to claim 7, further comprising apparatus for adding documents to said database.

14. The program product according to the claim 13, wherein said attributes include at least one keyword and/or a time stamp.

15. The program product according to the claim 12, wherein said covariance matrix is computed by the following formula;

K=B−

X_bar┘

X_bar^T

wherein K represents said covariance matrix, B represents a momentum matrix, X_bar represents a mean vector and X_bar^T represents a transpose thereof

16. The program product according to claim 13, wherein said predetermined numbers are 15-25 % of total of the eigenvectors of said covariance matrix.

17. The program product according to claim 13, wherein said method further includes a switching step from dimension reduction using said document matrix directly to dimension reduction using said covariance matrix depending on predetermined computation time so that said dimension reduction using said covariance matrix is executed when said dimension reduction of said document matrix using eigenvectors thereof, computed from said document matrix is not completed within said predetermined computation time.

18. The program product according to claim 13, further comprising computer code for accepting additional documents for addition to said database.

13. A program product including a computer readable computer program for executing a method for retrieving and/or ranking documents in a database, the documents including attribute data, said computer program including computer readable code for causing said apparatus to execute the steps of:

providing a document matrix from said documents, said matrix including numerical elements derived from said attribute data;

providing covariance matrix from said document matrix;

executing singular value decomposition of said covariance matrix so as to obtain the following formula;

K=V┘

©

┘

V^T,

wherein K represents said covariance matrix, V represents the matrix consisting of eigenvectors, ©

represents a diagonal matrix, and V^T represents a transpose of the matrix V;

reducing a dimension of said matrix V using predetermined numbers of eigenvectors included in said matrix V said eigenvectors including an eigenvector corresponding to the largest singular value;

reducing a dimension of said document matrix using said dimension reduced matrix V; and

retrieving and/or ranking said documents in said database by computing scalar product between said dimension reduced document matrix and a query vector.