Dynamic reduction of dimensions of a document vector in a document search and retrieval system

• US 20090119343A1
• Filed: 02/28/2008
• Published: 05/07/2009
• Est. Priority Date: 11/01/2007
• Status: Active Grant

• Current Assignee: UT-Battelle LLC
• Original Assignee: UT-Battelle LLC
• Inventors: Jiao, Yu, Potok, Thomas E.
• Granted Patent: US 7,937,389 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3347 using vector based model

Abstract

The method and system of the invention involves processing each new document (20) coming into the system into a document vector (16), and creating a document vector with reduced dimensionality (17) for comparison with the data model (15) without recomputing the data model (15). These operations are carried out by a first computer (11) while a second computer (12) updates the data model (18), which can be comprised of an initial large group of documents (19) and is premised on the computing an initial data model (13, 14, 15) to provide a reference point for determining document vectors from documents processed from the data stream (20).

Claims

1. A method for reducing dimensions of a document vector used to determine the similarity of a first document to a plurality of other documents in a computer, the method comprising:

receiving a document that is input to the computer for determining the similarity of the document to the plurality of other documents;

preprocessing the document to generate a document vector;

reducing a number of dimensions in the document vector;

comparing the document vector to at least one document vector for the plurality of documents to determine a similarity of the document to the plurality of other documents; and

displaying a measure of similarity of the document to the other documents to a human observer.

2. The method of claim 1, further comprising:

preprocessing a plurality of initial documents;

computing a data model representing the plurality of initial documents; and

wherein the document vector for the document is compared to at least one document vector for the data model to determine the similarity of the document to the documents forming the data model.

3. The method of claim 2, wherein the document vector for the document is compared to a document vector for the data model without updating the data model until a second plurality of documents have been received and processed by the computer.

4. The method of claim 3, wherein a calculation of the document vector with reduced dimensions is performed by a first computer;

and

wherein the updating of the data model is performed by a second computer in communication with the first computer.

5. The method of claim 3, further comprising updating the data model when a document count reaches 20,000 documents.

6. The method of claim 2, wherein the data model is computed from a large corpus of at least 200,000 documents, wherein a global frequency of words in the corpus of documents is expressed in a first table;

wherein a term frequency of terms in the corpus of documents is expressed in a second table; and

wherein a document matrix of initial dimension, m, is generated; and

wherein a truncated singular value decomposition (SVD) is computed according to the expression;

SVD_k(M)=U_kΣ

_kV_k^T, where U_k is a m×

k matrix of initial dimension m; and

Σ

_k is a k×

k matrix of reduced dimension k used in the data model.

7. The method of claim 1, wherein a reduced number of dimensions, k, is preset to a specific number.

8. The method of claim 1, wherein the preprocessing of the document received by the computer further comprises:

removing punctuation marks and symbols;

removing stop words; and

parsing the document into a list of stemmed words.

9. The method of claim 1, wherein the dimensionality of a document vector d created by the previous process is m and is reduced to a predefined k with dimensions determined by the following equation:

$\hat{d}<br><br>\text{;<br><br>}<br><br><br><br>\hat{d}=d^T<br><br>U_k<br><br>\underset{k}{\overset{-1}{\sum <br><br>}},$

wherein d is an original document vector, U_k and Σ

_k are the matrices resulted from the truncated SVD process and {circumflex over (d)} is the document vector with reduced dimensionality {circumflex over (d)} with k dimensions.

10. A computer system for reducing dimensions of a document vector used to determine the similarity of a first document to a plurality of other documents in the computer system, the system comprising:

means for receiving a document that is input to the computer for determining the similarity of the document to the plurality of other documents;

means for preprocessing the document to generate a document vector; and

means for reducing a number of dimensions in the document vector;

means for comparing the document vector to at least one document vector for the plurality of documents to determine a similarity of the document to the plurality of other documents; and

means for displaying a measure of similarity of the document to the other documents to a human observer.

11. The system of claim 10, further comprising:

means for preprocessing a plurality of initial documents; and

means for computing a data model representing the plurality of initial documents; and

wherein the document vector for the document is compared to at least document vector for the data model to determine the similarity of the document to the documents forming the data model.

12. The system of claim 11, wherein the document vector for the document is compared to a document vector for the data model without updating the data model until a second plurality of documents have been received and processed by the computer.

13. The system of claim 12, wherein means for comparing the document vector to at least one document vector for the plurality of documents is incorporated in a first computer;

and

wherein an updating of the data model is performed in a second computer in communication with the first computer.

14. The system of claim 12, wherein the updating of the data model is performed when a document count reaches 20,000 documents.

15. The system of claim 11, wherein the data model is computed from a large corpus of at least 200,000 documents, wherein a global frequency of words in the corpus of documents is expressed in a first table;

wherein a term frequency of terms in the corpus of documents is expressed in a second table; and

wherein a document matrix of initial dimension, m, is generated; and

wherein a truncated singular value decomposition (SVD) is computed according to the expression;

SVD_k(M)=U_kΣ

_kV_k^T, where U_k is a m×

k matrix of initial dimension m; and

Σ

_k is a k×

k matrix of reduced dimension k used in the data model.

16. The system of claim 10, wherein a reduced number of dimensions, k, is preset to a specific number.

17. The system of claim 10, wherein the preprocessing of the document received by the computer further comprises:

removing punctuation marks and symbols;

removing stop words; and

parsing the document into a list of stemmed words.

18. The system of claim 10, wherein the dimensionality of a document vector d created by the previous process is m and is reduced to a predefined k with dimensions determined by the following equation:

$\hat{d}<br><br>\text{;<br><br>}<br><br><br><br>\hat{d}=d^T<br><br>U_k<br><br>\underset{k}{\overset{-1}{\sum <br><br>}},$

wherein d is the original document vector, U_k and Σ

_k are the matrices resulted from the truncated SVD process and {circumflex over (d)} is the document vector with reduced dimensionality {circumflex over (d)} with k dimensions.