Algorithm for fast disk based text mining

• US 7,246,117 B2
• Filed: 03/31/2004
• Issued: 07/17/2007
• Est. Priority Date: 03/31/2004
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Peh, Thomas
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): ADAMS, CHARLES D
• Application Number:
  US10/815,253
• Publication Number:
  US 20050222997A1
• Time in Patent Office: 1,203 Days
• Field of Search: 707/1, 707/3, 707 4- 6, 709/203
• US Class Current: 1/1
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• 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

Methods and apparatus, including computer systems and program products, for executing a query, for example, a query for a document similar to another document. In one general aspect, the techniques feature a method of executing a query for at least one document similar to a specified document. That method includes receiving the query; forming a reduced query document based on ranks of terms in the specified document; generating a modified query based on the query and the reduced query document; executing the modified query on a data repository to generate a set of results; and, providing a result to a user interface.

Claims

1. A method of executing a query on a computer for at least one document similar to a specified document, the method comprising:

receiving the query;

forming a reduced query document based on ranks of terms in the specified document, the forming comprising;

calculating a rank of at least one term in the specified query document,

calculating a square of each rank,

calculating a normalized rank for each square,

sorting a list of said normalized ranks,

calculating a partial sum for each normalized rank in the list of normalized ranks, and

including, in the reduced query document, terms corresponding to a partial sum above a threshold value;

generating a modified query based on the query and the reduced query document;

executing the modified query on a data repository to generate a set of results; and

providing a result from said generated set of results to a user interface.

2. The method in accordance with claim 1, wherein the result comprises a document that is similar to the specified document.

3. The method in accordance with claim 1, wherein the result comprises a list of references to documents that are similar to the specified document.

4. The method in accordance with claim 1, wherein the result indicates that no similar document was found in the data repository.

5. The method in accordance with claim 1, wherein forming the reduced query document based on ranks of terms in the specified document excludes terms that are less selective.

6. The method in accordance with claim 1, wherein the data repository is modeled in accordance with a vector space model and executing the modified query comprises calculating the similarity of the reduced query document with a comparison document in the data repository in accordance with a function Q·

D/|Q|*|D| where Q is the reduced query document, D is the comparison document, Q·

D is a scalar product of column vectors corresponding to each document such that each column is a vector including ranks of terms in the documents, and |Q|*|D|is a normalization factor.

7. The method in accordance with claim 6, wherein the normalization factor is the product of the norms of the column vectors corresponding to each document calculated in accordance with an equation sqrt(q1^2+ . . . +qT^2) *sqrt (d1^2+. . . +dT^2) where sqrt signifies square root, q1 through qT are ranks of terms in the reduced query document, d1 through dT are ranks of terms in the comparison document, and T is the number of terms in an index of document vectors generated in accordance with the vector space model of the data repository.

8. The method in accordance with claim 6, wherein the scalar product of the column vectors is calculated in accordance with an equation (q1.d1+q2.d2+. . . +qT.dT) where q1 through qT are ranks of terms in the reduced query document, d1 through dT are ranks of terms in the comparison document, and T is the number of terms in an index of document vectors generated in accordance with the vector space model of the data repository.

9. A computer-readable storage media embodying instructions to cause data processor to perform operations comprising:

receiving a query for at least one document similar to a specified document;

forming a reduced query document based on ranks of terms in the specified document, the forming comprising;

calculating a rank of at least one term in the specified query document,

calculating a square of each rank,

calculating a normalized rank for each square,

sorting a list of said normalized ranks,

calculating a partial sum for each normalized rank in the list of normalized ranks, and

including, in the reduced query document, terms corresponding to a partial sum above a threshold value;

generating a modified query based on the query and the reduced query document;

executing the modified query on a data repository to generate a set of results; and

providing a result from said generated set of results to a user interface.

10. The computer-readable media in accordance with claim 9, wherein the result comprises a document that is similar to the specified document.

11. The computer-readable media in accordance with claim 9, wherein the result comprises a list of references to documents that are similar to the specified document.

12. The computer-readable media in accordance with claim 9, wherein the result indicates that no similar document was found in the data repository.

13. The computer-readable media in accordance with claim 9, wherein forming the reduced query document based on ranks of terms in the specified document excludes terms that are less selective.

14. The computer-readable media in accordance with claim 9, wherein the data repository is modeled in accordance with a vector space model and executing the modified query comprises calculating the similarity of the reduced query document with a comparison document in the data repository in accordance with a function Q·

D/|Q |*|D| where Q is the reduced query document, D is the comparison document, Q·

D is a scalar product of column vectors corresponding to each document such that each column is a vector including ranks of terms in the documents, and |Q|*|D| is a normalization factor.

15. The computer-readable media in accordance with claim 14, wherein the normalization factor is the product of the norms of the column vectors corresponding to each document calculated in accordance with an equation sqrt(q1^2+. . . +qT^2)* sqrt(d1^2+. . . +dT^2) where sqrt signifies square root, q1 through qT are ranks of terms in the reduced query document, d1 through dT are ranks of terms in the comparison document, and T is the number of terms in an index of document vectors generated in accordance with the vector space model of the data repository.

16. The computer-readable media in accordance with claim 14, wherein the scalar product of the column vectors is calculated in accordance with an equation (q1.d1+q2.d2+. . . +qT.dT) where q1 through qT are ranks of terms in the reduced query document, d1 through dT are ranks of terms in the comparison document, and T is the number of terms in an index of document vectors generated in accordance with the vector space model of the data repository.