Computer information retrieval using latent semantic structure via sketches

• US 8,255,401 B2
• Filed: 04/28/2010
• Issued: 08/28/2012
• Est. Priority Date: 04/28/2010
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Clarkson, Kenneth L., Woodruff, David P.
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US12/769,358
• Publication Number:
  US 20110270835A1
• Time in Patent Office: 853 Days
• Field of Search: 707/705, 707/708, 707/736, 707/737, 707/739, 708/250, 708/520
• US Class Current: 707/737
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

A method, system and program product for computer information retrieval is disclosed. A matrix A is received. Random sign matrices S and R are generated. Matrix products of S^T*A, A*R, and S^T*A*R are computed. A Moore-Penrose pseudoinverse C of S^T*A*R is computed. A singular value decomposition is computed of the pseudoinverse C. Three matrices ARU, Sigma, and V^TS^TA are outputted as factorization in applications.

Claims

1. A method comprising:

computer information retrieval using latent semantic structure via sketches, the retrieval comprising;

receiving an input n×

d matrix A with a computer;

receiving an input parameter k;

receiving a small constant eps, where eps is greater than zero;

generating a random d×

(k/eps) sign matrix R;

generating a random n×

(k/eps^2) sign matrix S;

computing a matrix product A*R;

computing a matrix product S^T*A, where S^T is (k/eps^2)×

n matrix, and where S^T_{i,j}=S_{j,i});

computing S^T*A*R;

computing the Moore-Penrose pseudoinverse C of S^T*A*R;

computing the singular value decomposition U*Sigma*V^T of C, where U is (k/eps)×

(k/eps), Sigma is dimensional matrix (k/eps) by (k/eps), and V is (k/eps^2)×

(k/eps); and

outputting the three matrices ARU, Sigma, and V^TS^TA as factorization in applications.

2. The method of claim 1, wherein the factorization is used instead of singular value decomposition of A in latent semantic indexing applications.

3. The method of claim 1, wherein the entries in the sign matrices R and S are generated using a cryptographic random number generator.

4. The method of claim 1, wherein the entries in the sign matrices R and S are generated from a distribution with limited independence.

5. The method of claim 1, wherein the entries in the sign matrices R and S are generated from a family of degree-r polynomials for a low value of r that is determined in practice.

6. The method of claim 1, wherein the input n×

d matrix A is specified row by row, where one sees entries of A in an arbitrary order, and an entry undergoes multiple updates.

7. The method of claim 1, wherein the input n×

d matrix A is specified in a stream online, where one sees entries of A in an arbitrary order, and an entry undergoes multiple updates.

8. The method of claim 1, wherein matrices are multiplied in the subroutines using at least one of:

standard matrix multiplication, and Stassen'"'"'s algorithm.

9. The method of claim 1, wherein matrices are multiplied in the subroutines using the Coppersmith algorithm.

10. A computer program product for computer information retrieval using latent semantic structure via sketches, comprising:

a computer non-transitory readable storage medium having computer readable code embodied therewith, the computer readable program code including;

computer readable code performed on a computer that receives an input n×

d matrix A;

computer readable code that receives an input parameter k;

computer readable code that represents each row n as a term and each column d as a document;

computer readable code that replaces the matrix A with a function of the matrix A;

computer readable code that receives a small constant eps, where eps is greater than zero;

computer readable code that generates a random d×

(k/eps) sign matrix R;

computer readable code that generates a random n×

(k/eps^2) sign matrix S;

computer readable code that computes a matrix product A*R;

computer readable code that computes a matrix product S^T*A, where S^T is (k/eps^2)×

n matrix where S^T_{i,j}=S_{j,i});

computer readable code that computes S^T*A*R;

computer readable code that computes the Moore-Penrose pseudoinverse C of S^T*A*R;

computer readable code that computes the singular value decomposition U*Sigma*V^T of C, where U is (k/eps)×

(k/eps), Sigma is dimensional matrix (k/eps) by (k/eps), and V is (k/eps^2)×

(k/eps); and

outputting the three matrices ARU, Sigma, and V^TS^TA as factorization in applications.

11. The computer program product of claim 10, including:

computer readable code that clusters documents based on their cosine similarity in the concept space;

computer readable program code that computes Sigma^{−

1}*(ARU)^T*d_j, given a document d_j, which is a vector; and

computer readable program code that computes Sigma^{−

1}*(ARU)^T*d′

_j, given a document d′

_j; and

computer readable program code that compares the two computed vectors using the angle between them.

12. The computer program product of claim 10, wherein the documents are compared across different languages, after analyzing a base set of translated documents.