Automatic stop word identification and compensation

• US 20060224572A1
• Filed: 02/07/2006
• Published: 10/05/2006
• Est. Priority Date: 04/05/2005
• Status: Active Grant

• Current Assignee: Relativity ODA LLC
• Original Assignee: Content Analyst Company, LLC (Relativity ODA LLC)
• Inventors: Price, Robert Jenson
• Granted Patent: US 7,720,792 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/3335 Syntactic pre-processing, e.g. stopword elimination, stemming

Abstract

Computer-based methods for automatically identifying and compensating for stop words contained in documents are described. The method for compensating for stop words includes: generating an abstract mathematical space based on documents included in a collection of documents, wherein each document has a representation in the abstract mathematical space; receiving a user query; generating a representation of the user query in the abstract mathematical; computing a similarity between the representation of the user query and the representation of each document, wherein computing a similarity between the representation of the user query and the representation of a first document in the collection of documents comprises applying a weighting function to a value associated with a frequently occurring word contained in the first document, thereby automatically compensating for the frequently occurring word contained in the first document; and displaying a result based on the similarity computations.

Claims

1. A computer-based method for automatically compensating for stop words contained in documents during a query of the documents, the method comprising:

(a) generating an abstract mathematical space based on documents included in a collection of documents, wherein each document has a representation in the abstract mathematical space;

(b) receiving a user query;

(c) generating a representation of the user query in the abstract mathematical space;

(d) computing a similarity between the representation of the user query and the representation of each document, wherein computing a similarity between the representation of the user query and the representation of a first document in the collection of documents comprises applying a weighting function to a value associated with a frequently occurring word contained in the first document, thereby automatically compensating for the frequently occurring word contained in the first document; and

(e) displaying a result based on the similarity computations.

2. The method of claim 1, wherein steps (a) and (c) comprise:

(a) generating an abstract mathematical space based on documents included in a collection of documents, wherein each document has a multi-dimensional representation in the abstract mathematical space; and

(c) generating a multi-dimensional representation of the user query in the abstract mathematical space.

3. The method of claim 2, wherein step (d) comprises:

computing a similarity between the multi-dimensional representation of the user query and the multi-dimensional representation of each document, wherein computing a similarity between the multi-dimensional representation of the user query and the multi-dimensional representation of a first document in the collection of documents comprises applying a weighting function to a predetermined dimension of the multi-dimensional representation of the first document, wherein the predetermined dimension is associated with a frequently occurring word contained in the first document.

4. The method of claim 3, wherein step (d) comprises:

computing a similarity between the multi-dimensional representation of the user query and the multi-dimensional representation of each document, wherein computing a similarity between the multi-dimensional representation of the user query and the multi-dimensional representation of a first document in the collection of documents comprises applying a weighting function to a first computed dimension of the multi-dimensional representation of the first document, wherein the first computed dimension is associated with a frequently occurring word contained in the first document.

5. The method of claim 2, wherein step (d) comprises:

computing a similarity between the multi-dimensional representation of the user query and the multi-dimensional representation of each document, wherein computing a similarity between the multi-dimensional representation of the user query and the multi-dimensional representation of a first document in the collection of documents comprises applying a weighting function to a plurality of dimensions of the multi-dimensional representation of the first document, wherein the plurality of dimensions are associated with a frequently occurring word contained in the first document.

6. The method of claim 2, wherein step (d) comprises:

computing a similarity between the multi-dimensional representation of the user query and the multi-dimensional representation of each document, wherein computing a similarity between the multi-dimensional representation of the user query and the multi-dimensional representation of a first document in the collection of documents comprises decreasing a predetermined dimension of the multi-dimensional representation of the first document by a factor of two, wherein the predetermined dimension is associated with a frequently occurring word contained in the first document.

7. The method of claim 2, wherein steps (a) and (c) comprise:

(a) generating a Latent Semantic Indexing (LSI) space based on documents included in a collection of documents, wherein each document has a multi-dimensional representation in the LSI space; and

(c) generating a multi-dimensional representation of the user query in the LSI space.

8. The method of claim 2, wherein step (d) comprises:

computing a cosine similarity between the representation of the user query and the representation of each document, wherein each cosine similarity computation comprises a plurality of multiplication computations and wherein a predetermined multiplication computation of each cosine similarity computation is decreased by a weighting function.

9. The method of claim 7, wherein step (d) comprises:

computing a cosine similarity between the representation of the user query and the representation of each document, wherein each cosine similarity computation comprises a plurality of multiplication computations corresponding to a plurality of dimensions of the LSI space, wherein a first multiplication computation of each cosine similarity computation, corresponding to a first dimension of the LSI space, is decreased by a weighting function.

10. The method of claim 7, wherein step (d) comprises:

computing a cosine similarity between the representation of the user query and the representation of each document, wherein each cosine similarity computation comprises a plurality of multiplication computations, wherein a predetermined multiplication computation of each cosine similarity computation is decreased by a factor of two.

11. A computer program product for automatically compensating for stop words contained in documents during a query of the documents, the computer program product comprising:

a computer usable medium having computer readable program code means embodied in the medium for causing an application program to execute on an operating system of a computer, the computer readable program code means comprising;

a computer readable first program code means for generating an abstract mathematical space based on documents in a collection of documents, wherein each document has a representation in the abstract mathematical space;

a computer readable second program code means for receiving a user query;

a computer readable third program code means for generating a representation of the user query in the abstract mathematical space;

a computer readable fourth program code means for computing a similarity between the representation of the user query and the representation of each document, wherein computing a similarity between the representation of the user query and the representation of a first document in the collection of documents comprises applying a weighting function to a value associated with a frequently occurring word contained in the first document, thereby automatically compensating for the frequently occurring word contained in the first document; and

a computer readable fifth program code means for displaying a result based on the similarity computations.

12. The computer program product of claim 11, wherein:

the first computer readable program code means comprises means for generating an abstract mathematical space based on the documents in the collection of documents, wherein each document has a multi-dimensional representation in the abstract mathematical space; and

the third computer readable program code means comprises means for generating a multi-dimensional representation of the user query in the abstract mathematical space.

13. The computer program product of claim 12, wherein the fourth computer readable program code means comprises:

means for computing a similarity between the multi-dimensional representation of the user query and the multi-dimensional representation of each document, wherein computing a similarity between the multi-dimensional representation of the user query and the multi-dimensional representation of a first document in the collection of documents comprises applying a weighting function to a predetermined dimension of the multi-dimensional representation of the first document, wherein the predetermined dimension is associated with a frequently occurring word contained in the first document.

14. The computer program product of claim 13, wherein the fourth computer readable program code means comprises:

means for computing a similarity between the multi-dimensional representation of the user query and the multi-dimensional representation of each document, wherein computing a similarity between the multi-dimensional representation of the user query and the multi-dimensional representation of a first document in the collection of documents comprises applying a weighting function to a first computed dimension of the multi-dimensional representation of the first document, wherein the first computed dimension is associated with a frequently occurring word contained in the first document.

15. The computer program product of claim 12, wherein the fourth computer readable program code means comprises:

means for computing a similarity between the multi-dimensional representation of the user query and the multi-dimensional representation of each document, wherein computing a similarity between the multi-dimensional representation of the user query and the multi-dimensional representation of a first document in the collection of documents comprises applying a weighting function to a plurality of dimensions of the multi-dimensional representation of the first document, wherein the plurality of dimensions are associated with a frequently occurring word contained in the first document.

16. The computer program product of claim 12, wherein the fourth computer readable program code means comprises:

means for computing a similarity between the multi-dimensional representation of the user query and the multi-dimensional representation of each document, wherein computing a similarity between the multi-dimensional representation of the user query and the multi-dimensional representation of a first document in the collection of documents comprises decreasing a predetermined dimension of the multi-dimensional representation of the first document by a factor of two, wherein the predetermined dimension is associated with a frequently occurring word contained in the first document.

17. The computer program product of claim 12, wherein:

the first computer readable program code means comprises means for generating a Latent Semantic Indexing (LSI) space based on documents in a collection of documents, wherein each document has a representation of the LSI space; and

the third computer readable program code means comprises means for generating a multi-dimensional representation of the user query in the LSI space.

18. The computer program product of claim 12, wherein the fourth computer readable program code means comprises:

means for computing a cosine similarity between the representation of the user query and the representation of each document, wherein each cosine similarity computation comprises a plurality of multiplication computations, wherein a predetermined multiplication computation of each cosine similarity computation is decreased by a weighting function.

19. The computer program product of claim 17, wherein the fourth computer readable program code means comprises:

means for computing a cosine similarity between the representation of the user query and the representation of each document, wherein each cosine similarity computation comprises a plurality of multiplication computations corresponding to a plurality of dimensions of the LSI space, wherein a first multiplication computation of each cosine similarity computation, corresponding to a first dimension of the LSI space, is decreased by a weighting function.

20. The computer program product of claim 17, wherein the fourth computer readable program code means comprises:

means for computing a cosine similarity between the representation of the user query and the representation of each document, wherein each cosine similarity computation comprises a plurality of multiplication computations, wherein a predetermined multiplication computation of each cosine similarity computation is decreased by a factor of two.

21. A computer-based method for automatically identifying stop words contained in a document collection, the method comprising:

(a) generating an abstract mathematical space based on documents included in a collection of documents, wherein each unique term contained in the documents has a multi-dimensional representation in the abstract mathematical space; and

(b) identifying stop words contained in the documents based on a magnitude of a predetermined dimension of each multi-dimensional representation in the abstract mathematical space.

22. The method of claim 21, wherein step (a) comprises:

(a) generating a Latent Semantic Indexing (LSD) space based on documents included in a collection of documents, wherein each unique term contained in the documents has a multi-dimensional representation in the LSI space.

23. The method of claim 21, wherein step (b) comprises:

(b) identifying stop words contained in the documents based on a magnitude of a first computed dimension of each multi-dimensional representation in the abstract mathematical space.

24. A computer program product for automatically identifying stop words contained in a document collection, the computer program product comprising:

a computer usable medium having computer readable program code means embodied in the medium for causing an application program to execute on an operating system of a computer, the computer readable program code means comprising;

a computer readable first program code means for generating an abstract mathematical space based on documents included in a collection of documents, wherein each unique term contained in the documents has a multi-dimensional representation in the abstract mathematical space; and

a computer readable second program code means for identifying stop words contained in the documents based on a magnitude of a predetermined dimension of each multi-dimensional representation in the abstract mathematical space.

25. The computer program product of claim 24, wherein the computer readable first program code means comprises means for generating a Latent Semantic Indexing (LSI) space based on documents included in a collection of documents, wherein each unique term contained in the documents has a multi-dimensional representation in the LSI space.

26. The computer program product of claim 24, wherein the computer readable second program code means comprises means for identifying stop words contained in the documents based on a magnitude of a first computed dimension of each multi-dimensional representation in the abstract mathematical space.