Retrieving, detecting and identifying major and outlier clusters in a very large database

• US 20040010485A1
• Filed: 07/08/2002
• Published: 01/15/2004
• Est. Priority Date: 07/05/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kobayashi, Mei, Takeuchi, Hironori, Aono, Masaki, Samukawa, Hikaru
• Granted Patent: US 6,920,450 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

The present invention discloses a method, a computer system, a computer readable medium and a sever. The method of the present invention comprises steps of; creating said document matrix from said documents using at least one attribute; creating a scaled residual matrix based on said document matrix using a predetermined function; executing singular value decomposition to obtain a basis vector corresponding to the largest singular value; re-constructing said residual matrix and scaling dynamically said re-constructed residual matrix to obtain another basis vector; repeating said singular value decomposition step to said re-constructing step to create a predetermined set of basis vector; and executing reduction of said document matrix to perform detection, retrieval and identification of said documents in said database.

Claims

1. A method for retrieving, detecting and identifying documents in a database, said documents in said database being constructed as a document matrix from attributes included in said documents, said method comprising steps of;

creating said document matrix from said documents using at least one attribute;

creating a scaled residual matrix based on said document matrix from a predetermined function;

executing singular value decomposition to obtain a basis vector corresponding to the largest singular value;

re-constructing said residual matrix and scaling dynamically said re-constructed residual matrix to obtain another basis vector;

repeating said singular value decomposition step to said re-constructing step to create a predetermined set of basis vectors; and

executing dimension reduction of said document matrix to perform detection, retrieval and identification of said documents in said database.

2. The method according to the claim 1, wherein said scaled residual matrix is created according to the following equation:

R_s=[|r₁|^qr₁, . . . , |r_M|^qr_M]^T

wherein R_s is the scaled residual matrix, r_i is a residual vector, i is a whole number mot more than a document munber M, |r_i| is a norm of said residual vector, T represents the transpose operation performed on vectors and q is a scaling factor dynamically determined according to said predetermined function.

3. The method according to the claim 1, wherein said singular value decomposition is alternatively selected by a user between a latent semantic indexing method and a covariance matrix method.

4. The method according to the claim 1, wherein said predetermined function is a function of the largest norm of said residual vector provided by the following equation:

5. The method according to the claim 1, wherein the method further comprising a step for orthogonalizing said basis vector (with respect to the other, heretofore computed basis vectors) prior to said step for re-constructing said residual matrix.

6. The method according to the claim 1, wherein said scaling step uses a different scaling factor for each step for obtaining said basis vectors.

7. The method according to the claim 1, wherein said document matrix comprises a plurality of clusters with respect to said attributes and said clusters is at least categorized into a major cluster, a medium cluster and an outlier cluster.

8. A computer system for retrieving, detecting, and identifying documents in a database, said documents in said database being constructed as a document matrix from attributes included in said documents, said computer system comprises;

means for creating said document matrix from said documents using at least one attribute;

means for scaling said residual matrix based on said document matrix from a predetermined function;

means for executing singular value decomposition to obtain a basis vector corresponding to the largest singular value;

means for re-constructing said residual matrix and scaling dynamically said re-constructed residual matrix to obtain another basis vectors;

means for repeating said singular value decomposition step to said re-constructing step to create a predetermined set of basis vector; and

means for executing dimension reduction of said document matrix to perform detection, retrieval, and identification of said documents in said database.

9. The computer system according to the claim 8, wherein said means for scaling said residual matrix scales said residual matrix according to the following equation:

R_s=[|r₁|^qr₁, . . . , |r_M|^qr_M]^T

wherein R_s is the scaled residual matrix, r_i is a residual vector, i is a whole number mot more than a document munber M, |r_i| is a norm of said residual vector, T represents the transpose operation on performed on vectors, and q is a scaling factor dynamically determined according to said predetermined function.

10. The computer system according to the claim 8, wherein said means for executing singular value decomposition is alternatively selected by a user between a latent semantic indexing method and a covariance matrix method.

11. The computer system according to the claim 8, wherein said predetermined function is a function of the largest norm of said residual vector provided by the following equation:

12. The computer system according to the claim 8, wherein the computer system further comprises means for orthogonalizing said basis vector (with respect to the other previously computed basis vectors) prior to said step for re-constructing said residual matrix.

13. The computer system according to the claim 8, wherein said means for scaling said residual vector uses a different scaling factor for each step for obtaining said basis vectors.

14. The computer system according to the claim 8, wherein said document matrix comprises a plurality of clusters with respect to said attributes and said clusters is at least categorized into a major cluster, a medium cluster and an outlier cluster.

15. A computer readable medium storing a computer program for retrieving, detecting, and identifying documents in a database, said documents in said database being constructed as a document matrix from attributes included in said documents, said program executing steps of;

creating said document matrix from said documents using at least one attribute;

creating a scaled residual matrix based on said document matrix from a predetermined function;

executing singular value decomposition to obtain a basis vector corresponding to the largest singular value;

re-constructing said residual matrix and scaling dynamically said re-constructed residual matrix to obtain another basis vector;

repeating said singular value decomposition step to said re-constructing step to create a predetermined set of basis vectors; and

executing dimension reduction of said document matrix to perform detection, retrieval and identification of said documents in said database.

16. The computer readable medium according to the claim 15, wherein said scaled residual matrix is created according to the following equation:

R_s=[|r₁|^qr₁, . . . , |r_M|^qr_M]^R

wherein R_S is the scaled residual matrix, r_i is a residual vector, i is a whole number mot more than a document munber M, |r_i| is a norm of said residual vector, T represents the transpose operation performed on vectors, and q is a scaling factor dynamically determined according to said predetermined function.

17. The computer readable medium according to the claim 15, wherein said singular value decomposition is alternatively selected by a user between a latent semantic indexing method and a covariance matrix method.

18. The computer readable medium according to the claim 15, wherein said predetermined function is a function of the largest norm of said residual vector provided by the following equation:

19. The computer readable medium according to the claim 15, wherein the program further executes a step for orthogonalizing said basis vector (with respect to the other, heretofore computed basis vectors) prior to said step for re-constructing said residual matrix.

20. The computer readable medium according to the claim 15, wherein said dynamic scaling step uses a different scaling factor for each step for obtaining said basis vectors.

21. The method according to the claim 15, wherein said document matrix comprises a plurality of clusters with respect to said attributes and said clusters is at least categorized into a major cluster, a medium cluster and an outlier cluster.

22. A server for retrieving, detecting, and identifying documents in a database, said documents in said database being constructed as a document matrix from attributes included in said documents, said server communicating to a client through a network, said server comprising;

means for receiving a request for retrieving and detecting said document though said network;

means for receiving another request for selecting a method for singular value decomposition from said client;

means for creating said document matrix from said documents using at least one attribute;

means for scaling said residual matrix based on said document matrix from a predetermined function;

means for executing singular value decomposition to obtain a basis vector corresponding to the largest singular value in response to said another request;

means for re-constructing said residual matrix and scaling dynamically said re-constructed residual matrix to obtain another basis vector;

means for repeating said singular value decomposition step to said re-constructing step to create a predetermined set of basis vectors; and

means for executing dimension reduction of said document matrix to perform detection, retrieval and identification of said documents in said database; and

means for returning at least one result of said detection, said retrieval and said identification to said client.

23. The server according to the claim 22, wherein said means for scaling said residual matrix uses a different scaling factor for each step for obtaining said basis vectors.