Information retrieval system, an information retrieval method, a program for executing information retrieval, and a storage medium wherein a program for executing information retrieval is stored

• US 6,965,898 B2
• Filed: 10/23/2002
• Issued: 11/15/2005
• Est. Priority Date: 10/23/2001
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kobayashi, Mei, Takeuchi, Hironori, Aono, Masaki, Samukawa, Hikaru
• Primary Examiner(s): Corrielus, Jean M.
• Assistant Examiner(s): HWANG, JOON H
• Application Number:
  US10/278,675
• Publication Number:
  US 20030159106A1
• Time in Patent Office: 1,119 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206
• 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

To provide an information retrieval system, a method for information retrieval, a program for executing the information retrieval, and a storage medium comprising the program for executing the information retrieval

The information retrieval system according to the present invention comprises: means for generating and storing a predetermined type matrix from said document-attribute matrix, means for generating said document-attribute submatrix from documents being added to said database during a specific time period, means for updating said predetermined type matrix using knowledge with respect to said document-attribute submatrix and for executing the singular value decomposition on updated said predetermined type matrix to execute dimension reduction of all document-attribute matrices stored within said database, and means for retrieving information with respect to a user input query using said dimension reduced document-attribute matrix.

Claims

1. An information retrieval system for retrieving documents added to a database with respect to time, said documents being converted into a document-attribute matrix and stored within said information retrieval system, and said document-attribute matrix being constituted by document-attribute submatrices added in order with respect to time, said information retrieval system comprising:

means for generating and storing a predetermined type matrix from said document-attribute matrix,

means for executing QR decomposition of said document-attribute matrix and using only a matrix R as said predetermined matrix, wherein the matrix R is an upper triangular matrix obtained by said QR decomposition,

means for generating a document-attribute submatrix from said documents being added to said database during a specific time period,

means for updating said predetermined type matrix using knowledge with respect to said document-attribute submatrix and for executing a singular value decomposition on said updated predetermined type matrix to execute dimension reduction of all document-attribute matrices stored within said database, and

means for retrieving information with respect to a user input query using said dimension reduced document-attribute matrices.

2. The information retrieval system according to claim 1 comprising a means of updating said stored matrix R by a Householder transformation related to said document-attribute submatrices.

3. The information retrieval system according to claim 1 comprising means of:

generating a covariance matrix as said predetermined matrix from said document-attribute submatrices; and

retaining a product sum matrix of document vectors (SUM(M)₁), a mean value of document vectors (MEAN(M)₁), a mean product matrix of document vectors (SUM(M)₂) and a total number of documents (M).

4. The information retrieval system according to claim 3 comprising a means of generating a covariance matrix C′

of all document-attribute matrices including said added submatrices from the following formula;

$C^{\mathrm{\prime <br><br>}}=\frac{1}{\left(M+H\right)}<br><br>{\mathrm{SUM}<br><br>\left(M+H\right)}_1-{\mathrm{SUM}<br><br>\left(M+H\right)}_2$

(wherein, H represents a number of documents of added submatrices).

5. The information retrieval system according to claim 3 further comprising means of retrieving attributes contained in a document vector automatically and generating an attribute hash table for adding or deleting said attributes.

6. An information retrieval method for retrieving documents added to a database with respect to time, said documents being converted into a document-attribute matrix and stored within an information retrieval system, and said document-attribute matrix being constituted by document-attribute submatrices added in order with respect to time, said information retrieval method comprising the steps of:

generating and storing a predetermined type matrix from said document-attribute matrix,

executing QR decomposition of said document-attribute matrix and using only a matrix R as said predetermined matrix, wherein the matrix R is an upper triangular matrix obtained by said QR decomposition,

generating a document-attribute submatrix from said documents being added to said database during a specific time period,

updating said predetermined type matrix using knowledge with respect to said document-attribute submatrix and for executing a singular value decomposition on said updated predetermined type matrix to execute dimension reduction of all document-attribute matrices stored within said database, and

retrieving information with respect to a user input query using said dimension reduced document-attribute matrices.

7. The information retrieval method according to claim 6 comprising a step of updating said stored matrix R by a Householder transformation related to said document-attribute submatrices.

8. The information retrieval method according to claim 6 comprising the steps of:

generating a covariance matrix as said predetermined matrix from said document-attribute submatrices; and

retaining a product sum matrix of document vectors (SUM(M)₁), a mean value of document vectors (MEAN(M)₁), a mean product matrix of document vectors (SUM(M)₂) and a total number of documents (M).

9. The information retrieval method according to claim 8 comprising a step of a generating covariance matrix C′

of all a document-attribute matrix including said added submatrices from the following formula;

$C^{\mathrm{\prime <br><br>}}=\frac{1}{\left(M+H\right)}<br><br>{\mathrm{SUM}<br><br>\left(M+H\right)}_1-{\mathrm{SUM}<br><br>\left(M+H\right)}_2$

(wherein, H represents a number of documents of added submatrices).

10. The information retrieval method according to claim 8 further comprising the steps of:

retrieving attributes contained in a document vector automatically and

generating an attribute hash table for adding or deleting said attributes.

11. A program stored in a storage medium for retrieving documents added to a database with respect to time, said documents being converted into a document-attribute matrix and stored within an information retrieval system, and said document-attribute matrix being constituted by document-attribute submatrices added in order with respect to time, said program making a computer execute the steps of:

generating and storing a predetermined type matrix from said document-attribute matrix,

executing QR decomposition of said document-attribute matrix and using only a matrix R as said predetermined matrix, wherein the matrix R is an upper triangular matrix obtained by said QR decomposition,

generating a document-attribute submatrix from said documents being added to said database during a specific time period,

updating said predetermined type matrix using knowledge with respect to said document-attribute submatrix and for executing a singular value decomposition on said updated predetermined type matrix to execute dimension reduction of all document-attribute matrices stored within said database, and

retrieving information with respect to a user input query using said dimension reduced document-attribute matrices.

12. The program according to claim 11 for making a computer execute a step of updating said stored matrix R by a Householder transformation related to said document-attribute submatrices.

13. The program according to claim 11 for making a computer execute the steps of:

generating a covariance matrix as said predetermined matrix from said document-attribute submatrices, and

retaining a product sum matrix of document vectors (SUM(M)₁), a mean value of document vectors (MEAN(M)₁), a mean product matrix of document vectors (SUM(M)₂) and a total number of documents (M).

14. The program according to claim 13 for making a computer execute a step of generating a covariance matrix C′

of all a document-attribute matrix including said added submatrices from the following formula;

$C\text{'}"\text{'}"\text{'}=\frac{1}{\left(M+H\right)}<br><br>{\mathrm{SUM}<br><br>\left(M+H\right)}_1-{\mathrm{SUM}<br><br>\left(M+H\right)}_2$

(wherein, H represents a number of documents of added submatrices).

15. The program according to claim 14 for further making a computer execute steps of

retrieving an attribute contained in a document vector automatically;

and

generating an attribute hash table to add or delete said attribute.

16. A storage medium readable by a computer wherein a program for making a computer execute an information retrieval method to retrieve documents added to a database with respect to time, said documents being converted into a document-attribute matrix and stored within an information retrieval system, and said document-attribute matrix being constituted by document-attribute submatrices added in order with respect to time, said program making a computer execute said information retrieval method comprising the steps of:

generating and storing a predetermined type matrix from said document-attribute matrix,

executing QR decomposition of said document-attribute matrix and using only a matrix R as said predetermined matrix, wherein the matrix R is an upper triangular matrix obtained by said OR decomposition,

generating a document-attribute submatrix from said documents being added to said database during a specific time period,

updating said predetermined type matrix using knowledge with respect to said document-attribute submatrix and for executing a singular value decomposition on said updated predetermined type matrix to execute dimension reduction of all document-attribute matrices stored within said database, and

retrieving information with respect to a user input query using said dimension reduced document-attribute matrices.

17. The storage medium according to claim 16 making a computer execute a step of updating said stored matrix R by a Householder transformation related to said document-attribute submatrices.

18. The storage medium according to claim 16 making a computer execute a step of generating a covariance matrix as said predetermined matrix from said document-attribute submatrices and retaining a product sum matrix of document vectors (SUM(M)₁) a mean value of document vectors (MEAN(M)₁), a mean product matrix of document vectors (SUM(M)₂) and a total number of documents (M).

19. The storage medium according to claim 18 making a computer execute a step of generating a covariance matrix C′

of all a document-attribute matrix including added said submatrices from the following formula;

$C\text{'}"\text{'}"\text{'}=\frac{1}{\left(M+H\right)}<br><br>{\mathrm{SUM}<br><br>\left(M+H\right)}_1-{\mathrm{SUM}<br><br>\left(M+H\right)}_2$

(wherein, H represents a number of documents of added submatrices).

20. The storage medium according to claim 18 further making a computer execute the steps of:

retrieving an attribute contained in a document vector, and

generating an attribute hash table to add or delete said attribute.