System and method for identifying relationships between database records

• US 20060123036A1
• Filed: 01/13/2006
• Published: 06/08/2006
• Est. Priority Date: 02/20/2002
• Status: Active Grant

• Current Assignee: Syngence Corp.
• Original Assignee: Lawrence Technologies LLC
• Inventors: Loafman, Kenneth W., Benno, Stephen A., Lawrence, P. Nick
• Granted Patent: US 7,349,928 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing

Abstract

A system for identifying relationships between database records includes a memory operable to store a plurality of records comprising a first record and at least one second record. Each record comprises at least one of a plurality of tokens. The system also includes one or more processors collectively operable to determine a weight associated with each of the tokens, compare at least one second record to the first record, and determine at least one relationship indicator based on the comparison and at least one of the weights. The at least one relationship indicator identifies a level of relationship between the first record and at least one second record.

Claims

1. A system for identifying relationships between database records, comprising:

a memory operable to store a plurality of records, each record comprising at least one of a plurality of tokens; and

one or more processors collectively operable to;

determine a number of times that each token appears in the plurality of records;

determine a number of times that all tokens appear in the plurality of records;

determine a weight associated with each of the tokens, each weight based at least partially on the number of times that one of the tokens appears in the plurality of records and the number of times that all tokens appear in the plurality of records;

generate a token table containing each of the tokens, a token representation associated with each token, and the weight associated with each token;

generate a records table containing one or more token representations associated with the one or more tokens contained in each record, the records table also identifying a number of times that the one or more tokens appear in each record; and

generate a records table index containing a location in the records table associated with each record and a record score associated with each record.

2. The system of claim 1, wherein the weight associated with one of the tokens is determined using a formula of:

$\mathrm{Weight}=-\log <br><br>\left(\frac{{\mathrm{Count}}_{\mathrm{Token}}}{{\mathrm{Total}}_{\mathrm{Token}}}\right)$

where Count_Token represents the number of times that the token appears in the plurality of records, and Total_Tokens represents the number of times that all tokens appear in the plurality of records.

3. The system of claim 1, wherein the record score associated with one of the records is determined using a formula of:

$\mathrm{Record}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Score}=\underset{i=1}{\overset{k}{\sum <br><br>}}<br><br>\left({\mathrm{Weight}}_{\mathrm{Token}<br><br>\text{\hspace{1em}<br><br>}<br><br>k}*{\mathrm{Count}}_{\mathrm{Token}<br><br>\text{\hspace{1em}<br><br>}<br><br>k}\right)$

where k represents a number of unique tokens associated with the record, Weight_{Token k} represents the weight associated with the kth unique token, and Count_{Token k} represents a number of times that the kth unique token appears in the record.

4. The system of claim 1, wherein:

each record is associated with at least one document; and

the one or more processors are collectively operable to;

generate a plurality of text files, each text file associated with one of the documents and comprising the tokens contained in the associated document; and

generate the plurality of records, each record associated with one of the text files and comprising the tokens contained in the associated text file.

5. The system of claim 4, wherein the one or more processors are collectively operable to generate one of the records by:

identifying one-word tokens in one of the text files, the one-word tokens comprising individual words in the text file;

inserting the one-word tokens in the record;

selecting pairs of one-word tokens in the record, each pair of one-word tokens comprising consecutive one-word tokens in the record;

combining the pairs of one-word tokens to produce two-word tokens; and

inserting the two-word tokens in the record.

6. The system of claim 1, wherein the token representations comprise correlithm objects, each correlithm object comprising a plurality of values defining a first point in a particular space, the particular space defined by a plurality of dimensions and including a plurality of points.

7. The system of claim 6, wherein:

a distance between the first point and each of the plurality of points in the particular space defines a distribution having a standard deviation; and

a number of values in the correlithm object associated with one of the tokens may be determined using a formula of;

Number of Values=[Weight_Token*Standard Deviation]

where Weight_Token represents the weight associated with the token, and Standard Deviation represents the standard deviation of the distribution.

8. The system of claim 6, wherein each token representation further comprises a significance vector.

9. The system of claim 8, wherein each significance vector comprises a plurality of significance values, each significance value determined using a formula of:

$\mathrm{Significance}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Value}=\frac{{\mathrm{Weight}}_{\mathrm{Token}}*\mathrm{Standard}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Deviation}}{\mathrm{Number}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{of}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Values}}$

where Weight_Token represents the weight associated with the token, Standard Deviation represents the standard deviation of the distribution, and Number of Values represents a number of values defining the first point in the correlithm object.

10. The system of claim 6, wherein:

the correlithm objects comprises first correlithm objects, each first correlithm object associated with a first significance vector; and

the one or more processors are further collectively operable to generate a second correlithm object and a second significance vector associated with each record, each second correlithm object comprising at least one of the first correlithm objects.

11. The system of claim 10, wherein:

the second correlithm object comprises one or more first entries and the second significance vector comprises one or more second entries, at least one first entry comprising one of the first correlithm objects; and

a number of first entries in the second correlithm object and a number of second entries in the second significance vector are determined using a formula of;

$\mathrm{Number}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{of}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Entries}=\underset{i=1}{\overset{j}{\sum <br><br>}}<br><br>\left(\mathrm{Maximum}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{Instances}}_{{\mathrm{Token}}_i}\right)$

where j represents a number of unique tokens contained in the plurality of records, and Maximum Instances_{Token i} represents a maximum number of times that the ith unique token appears in a single record in the plurality of records.

12. The system of claim 11, wherein:

each first entry in the second correlithm object is associated with an instance of one of the tokens;

each first entry in the second correlithm object is also associated with one second entry in the second significance vector; and

the one or more processors are collectively operable to generate the second significance vector by;

determining whether the instance of the token associated with one of the first entries appears in the first record;

inserting one or more non-zero significance values into the second entry associated with the first entry when the instance of the token associated with the first entry appears in the first record; and

inserting one or more zero significance values into the second entry associated with the first entry when the instance of the token associated with the first entry does not appear in the first record.

13. The system of claim 10, wherein:

the second correlithm object comprises a plurality of first entries and the second significance vector comprises a plurality of second entries, at least one first entry comprising one of the first correlithm objects; and

a number of first entries in the second correlithm object and a number of second entries in the second significance vector equal a number of unique tokens in the plurality of records.

14. The system of claim 13, wherein:

each first entry in the second correlithm object is associated with one of the unique tokens;

each first entry in the second correlithm object is also associated with one second entry in the second significance vector; and

the one or more processors are collectively operable to generate the second significance vector by;

determining a number of times that the unique token associated with the first entry appears in the first record;

determining a maximum number of times that the unique token associated with the first entry appears in a single record in the plurality of records;

inserting one or more significance values from the first significance vector associated with the unique token into the second entry associated with the first entry when the unique token associated with the first entry appears the maximum number of times in the first record;

inserting one or more scaled significance values from the first significance vector associated with the unique token into the second entry associated with the first entry when the unique token associated with the first entry appears at least once but less than the maximum number of times in the first record; and

inserting one or more zero significance values into the second entry associated with the first entry when the unique token associated with the first entry does not appear in the first record.

15. The system of claim 1, wherein:

at least one token comprises a first correlithm object; and

at least one of the records comprises a second correlithm object, the second correlithm object comprising at least one of the first correlithm objects.

16. A method for identifying relationships between database records, comprising:

determining a number of times that each of a plurality of tokens appears in a plurality of records, each record comprising at least one of the plurality of tokens;

determining a number of times that all tokens appear in the plurality of records;

determining a weight associated with each of the tokens, each weight based at least partially on the number of times that one of the tokens appears in the plurality of records and the number of times that all tokens appear in the plurality of records;

generating a token table containing each of the tokens, a token representation associated with each token, and the weight associated with each token;

generating a records table containing one or more token representations associated with the one or more tokens contained in each record, the records table also identifying a number of times that the one or more tokens appear in each record; and

generating a records table index containing a location in the records table associated with each record and a record score associated with each record.

17. The method of claim 16, wherein the weight associated with one of the tokens is determined using a formula of:

$\mathrm{Weight}=-\log <br><br>\left(\frac{{\mathrm{Count}}_{\mathrm{Token}}}{{\mathrm{Total}}_{\mathrm{Token}}}\right)$

where Count_Token represents the number of times that the token appears in the plurality of records, and Total_Tokens represents the number of times that all tokens appear in the plurality of records.

18. The method of claim 16, wherein the record score associated with one of the records is determined using a formula of:

$\mathrm{Record}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Score}=\underset{i=1}{\overset{k}{\sum <br><br>}}<br><br>\left({\mathrm{Weight}}_{\mathrm{Token}<br><br>\text{\hspace{1em}<br><br>}<br><br>k}*{\mathrm{Count}}_{\mathrm{Token}<br><br>\text{\hspace{1em}<br><br>}<br><br>k}\right)$

where k represents a number of unique tokens associated with the record, Weight_{Token k} represents the weight associated with the kth unique token, and Count_{Token k} represents a number of times that the kth unique token appears in the record.

19. The method of claim 16, wherein each record is associated with at least one document;

and

further comprising;

generating a plurality of text files, each text file associated with one of the documents and comprising the tokens contained in the associated document; and

generating the plurality of records, each record associated with one of the text files and comprising the tokens contained in the associated text file.

20. The method of claim 19, wherein generating one of the records comprises:

identifying one-word tokens in one of the text files, the one-word tokens comprising individual words in the text file;

inserting the one-word tokens in the record;

selecting pairs of one-word tokens in the record, each pair of one-word tokens comprising consecutive one-word tokens in the record;

combining the pairs of one-word tokens to produce two-word tokens; and

inserting the two-word tokens in the record.

21. The method of claim 16, wherein the token representations comprise correlithm objects, each correlithm object comprising a plurality of values defining a first point in a particular space, the particular space defined by a plurality of dimensions and including a plurality of points.

22. The method of claim 21, wherein:

a distance between the first point and each of the plurality of points in the particular space defines a distribution having a standard deviation; and

a number of values in the correlithm object associated with one of the tokens may be determined using a formula of;

Number of Values=[Weight_Token*Standard Deviation]

where Weight_Token represents the weight associated with the token, and Standard Deviation represents the standard deviation of the distribution.

23. The method of claim 21, wherein each token representation further comprises a significance vector.

24. The method of claim 23, wherein each significance vector comprises a plurality of significance values, each significance value determined using a formula of:

$\mathrm{Significance}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Value}=\frac{{\mathrm{Weight}}_{\mathrm{Token}}*\mathrm{Standard}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Deviation}}{\mathrm{Number}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{of}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Values}}$

where Weight_Token represents the weight associated with the token, Standard Deviation represents the standard deviation of the distribution, and Number of Values represents a number of values defining the first point in the correlithm object.

25. The method of claim 21, wherein the correlithm objects comprises first correlithm objects, each first correlithm object associated with a first significance vector;

and

further comprising generating a second correlithm object and a second significance vector associated with each record, each second correlithm object comprising at least one of the first correlithm objects.

26. The method of claim 25, wherein:

the second correlithm object comprises one or more first entries and the second significance vector comprises one or more second entries, at least one first entry comprising one of the first correlithm objects; and

a number of first entries in the second correlithm object and a number of second entries in the second significance vector are determined using a formula of;

$\mathrm{Number}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{of}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Entries}=\underset{i=1}{\overset{j}{\sum <br><br>}}<br><br>\left(\mathrm{Maximum}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{Instances}}_{{\mathrm{Token}}_i}\right)$

where j represents a number of unique tokens contained in the plurality of records, and Maximum Instances_{Token i} represents a maximum number of times that the ith unique token appears in a single record in the plurality of records.

27. The method of claim 26, wherein:

each first entry in the second correlithm object is associated with an instance of one of the tokens;

each first entry in the second correlithm object is also associated with one second entry in the second significance vector; and

generating the second significance vector comprises;

determining whether the instance of the token associated with one of the first entries appears in the first record;

inserting one or more non-zero significance values into the second entry associated with the first entry when the instance of the token associated with the first entry appears in the first record; and

inserting one or more zero significance values into the second entry associated with the first entry when the instance of the token associated with the first entry does not appear in the first record.

28. The method of claim 25, wherein:

the second correlithm object comprises a plurality of first entries and the second significance vector comprises a plurality of second entries, at least one first entry comprising one of the first correlithm objects; and

a number of first entries in the second correlithm object and a number of second entries in the second significance vector equal a number of unique tokens in the plurality of records.

29. The method of claim 28, wherein:

each first entry in the second correlithm object is associated with one of the unique tokens;

each first entry in the second correlithm object is also associated with one second entry in the second significance vector; and

generating the second significance vector comprises;

determining a number of times that the unique token associated with the first entry appears in the first record;

determining a maximum number of times that the unique token associated with the first entry appears in a single record in the plurality of records;

inserting one or more significance values from the first significance vector associated with the unique token into the second entry associated with the first entry when the unique token associated with the first entry appears the maximum number of times in the first record;

inserting one or more scaled significance values from the first significance vector associated with the unique token into the second entry associated with the first entry when the unique token associated with the first entry appears at least once but less than the maximum number of times in the first record; and

inserting one or more zero significance values into the second entry associated with the first entry when the unique token associated with the first entry does not appear in the first record.

30. The method of claim 16, wherein:

at least one token comprises a first correlithm object; and

at least one of the records comprises a second correlithm object, the second correlithm object comprising at least one of the first correlithm objects.

31. Software for identifying relationships between database records, the software embodied on at least one computer readable medium and operable when executed to:

determine a number of times that each of a plurality of tokens appears in a plurality of records, each record comprising at least one of the plurality of tokens;

determine a number of times that all tokens appear in the plurality of records;

determine a weight associated with each of the tokens, each weight based at least partially on the number of times that one of the tokens appears in the plurality of records and the number of times that all tokens appear in the plurality of records;

generate a token table containing each of the tokens, a token representation associated with each token, and the weight associated with each token;

generate a records table containing one or more token representations associated with the one or more tokens contained in each record, the records table also identifying a number of times that the one or more tokens appear in each record; and

generate a records table index containing a location in the records table associated with each record and a record score associated with each record.

32. A system for identifying relationships between database records, comprising:

means for storing a plurality of records, each record comprising at least one of a plurality of tokens;

means for determining a number of times that each token appears in the plurality of records;

means for determining a number of times that all tokens appear in the plurality of records;

means for determining a weight associated with each of the tokens, each weight based at least partially on the number of times that one of the tokens appears in the plurality of records and the number of times that all tokens appear in the plurality of records;

means for generating a token table containing each of the tokens, a token representation associated with each token, and the weight associated with each token;

means for generating a records table containing one or more token representations associated with the one or more tokens contained in each record, the records table also identifying a number of times that the one or more tokens appear in each record; and

means for generating a records table index containing a location in the records table associated with each record and a record score associated with each record.

33. A method for identifying relationships between database records, comprising:

communicating at least one of one or more documents, one or more text files, and one or more records to an indexing engine, each of the at least one of the documents, the text files, and the records comprising at least one of a plurality of tokens; and

wherein the indexing engine is operable to;

determine a number of times that each token appears in the at least one of the documents, the text files, and the records;

determine a number of times that all tokens appear in the at least one of the documents, the text files, and the records;

determine a weight associated with each of the tokens, each weight based at least partially on the number of times that one of the tokens appears in the at least one of the documents, the text files, and the records and the number of times that all tokens appear in the at least one of the documents, the text files, and the records;

generate a token table containing each of the tokens, a token representation associated with each token, and the weight associated with each token;

generate a records table containing one or more token representations associated with the one or more tokens contained in each of the at least one of the documents, the text files, and the records, the records table also identifying a number of times that the one or more tokens appear in each of the at least one of the documents, the text files, and the records; and

generate a records table index containing a location in the records table associated with each of the at least one of the documents, the text files, and the records and a score associated with each of the at least one of the documents, the text files, and the records.