Retrieving and ranking of documents from database description

• US 6,678,690 B2
• Filed: 06/12/2001
• Issued: 01/13/2004
• Est. Priority Date: 06/12/2000
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Samukawa, Hikaru, Malassis, Loic, Kobayashi, Mei
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): FILIPCZYK, MARCIN R
• Application Number:
  US09/879,756
• Publication Number:
  US 20020032682A1
• Time in Patent Office: 945 Days
• Field of Search: 707/1-10, 707/100, 707/101, 715/500
• US Class Current: 1/1
• 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 a covariance matrix from said document matrix;

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

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 predetermined numbers are 15-25% of a total or the eigenvectors of said covariance matrix.

4. The method according to claim 1, further comprising switching from dimension reduction using said document matrix directly to dimension reduction using said covariance matrix depending on a 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.

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

6. 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;

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

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

9. The computer system according to claim 6, further comprising apparatus for switching from dimension reduction using said document matrix directly to dimension reduction using said covariance matrix, depending on a predetermined computation time, so that saw 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.

10. The computer according to claim 6, further comprising apparatus for adding documents to said database.

11. 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 a covariance matrix from said document matrix;

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

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

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

14. The program product according to claim 11, wherein said steps further comprise a switching step from dimension reduction using said document matrix directly to dimension reduction using said covariance matrix depending on a 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.

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