Ranking of documents in a very large database

• US 20030023570A1
• Filed: 05/24/2002
• Published: 01/30/2003
• Est. Priority Date: 05/25/2001
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kobayashi, Mei, Piperakis, Romanos
• Application Number:
  US10/155,516
• Publication Number:
  US 20030023570A1
• Time in Patent Office: Days
• US Class Current: 706/15
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 3/02 Neural networks

Abstract

The present invention discloses a method, a computer system, a program product which provide a useful interface to rank the documents in a very large database using neural network(s). The method comprising the steps of: providing a document matrix from said documents, said matrix including numerical elements derived from said attribute data; providing the covariance matrix from said document matrix; computing the eigenvectors of said covariance matrix using neural network algorithm(s); computing inner products of said eigenvectors to create sum S $S=\sum _{i<j}e_i·e_j$

and examining convergence of said sum S such that difference between the sums becomes not more than a predetermined threshold to determine a final set of said eigenvectors; providing said set of eigenvectors to the singular value decom position of said covariance matrix.

Claims

1. A method for retrieving and/or ranking documents in a database, said method comprising 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;

computing eigenvectors of said covariance matrix using neural network algorithm(s);

computing inner products of said eigenvectors to create the said sum S

$S=\underset{i<<br><br>j}{\sum <br><br>}<br><br>e_i·<br><br>e_j$

and examining convergence of said sum S such that difference between the sums becomes not more than a predetermined threshold to determine the final set of said eigenvectors;

providing said set of eigenvectors to the 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 the transpose of the matrix V;

reducing the 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; and

reducing the dimension of said document matrix using said dimension reduced matrix V.

2. The method according to the claim 1, said method further comprises the step of;

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

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

K=B−

X_bar·

X_bar^T,

wherein K represents a covariance matrix in 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 the claim 1, wherein said sum are created from 15-25% of the total of the eigenvectors of said covariance matrix.

5. A computer system for executing a method for retrieving and/or ranking documents in a database comprising:

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

means for providing the covariance matrix from said document matrix;

means for computing eigenvectors of said covariance matrix using neural network algorithm(s);

means for computing inner products of said eigenvectors to create sum S

$S=\underset{i<<br><br>j}{\sum <br><br>}<br><br>e_i·<br><br>e_j$

and examining convergence of said sum S such that difference between the sums becomes not more than a predetermined threshold to determine a final set of said eigenvectors;

means for providing said set of eigenvectors to the 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 the transpose of the matrix V;

means for reducing the 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; and

means for reducing the dimension of said document matrix using said dimension reduced matrix V.

6. The computer system according to the claim 5, wherein said computer system further comprises:

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

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

K=B−

X_bar·

X_bar^T,

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

8. The computer system according to the claim 6, wherein said sum are created from 15-25% of the total of the eigenvectors of said covariance matrix.

9. A program product including a computer readable computer program for executing a method for retrieving and/or ranking documents in a database, said method comprising the steps of;

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

providing the covariance matrix from said document matrix;

computing eigenvectors of said covariance matrix using neural network algorithm(s);

computing inner products of said eigenvectors to create the said sum S

$S=\underset{i<<br><br>j}{\sum <br><br>}<br><br>e_i·<br><br>e_j$

and examining the convergence of said sum S such that the difference between the sums becomes not more than a predetermined threshold to determine a final set of said eigenvectors;

providing said set of eigenvectors to the 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 the transpose of the matrix V;

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

reducing the dimension of said document matrix using said dimension reduced matrix V.

10. The program product according to the claim 9, wherein said method further comprising the step of;

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

12. The program product according to the claim 9, wherein said sum are created from 15-25% of the total of the eigenvectors of said covariance matrix.

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

K=B−

X_bar·

X_bar^T,

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

13. A computer system comprising:

means for providing a matrix from including numerical elements;

providing covariance matrix from said matrix;

means for computing eigenvectors of said covariance matrix using neural network algorithm(s);

means for computing inner products of said eigenvectors to create the said sum S

$S=\underset{i<<br><br>j}{\sum <br><br>}<br><br>e_i·<br><br>e_j$

and examining convergence of said sum S such that difference between the sums becomes not more than a predetermined threshold to determine a final set of said eigenvectors;

means for providing said set of eigenvectors to the 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;

means for reducing the 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; and

means for reducing the dimension of said matrix using said dimension reduced matrix V.

14. The computer system according to the claim 13, wherein said sum are created from 15-25% of the total of the eigenvectors of said covariance matrix.