Automated detection of null field values and effectively null field values

• US 8,489,617 B2
• Filed: 06/05/2012
• Issued: 07/16/2013
• Est. Priority Date: 04/24/2008
• Status: Active Grant

• Current Assignee: LexisNexis Risk Solutions, Inc. (RELX PLC)
• Original Assignee: LexisNexis Risk Solutions, Inc. (RELX PLC)
• Inventors: Bayliss, David Alan
• Primary Examiner(s): PYO, MONICA M
• Application Number:
  US13/489,236
• Publication Number:
  US 20120290585A1
• Time in Patent Office: 406 Days
• Field of Search: 707748-751
• US Class Current: 707/748
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Disclosed are systems for, and methods of, automatically detecting and treating field values of a particular field as null field values in records of a database. The system and method provide automatic treatment of these field values as null field values by calculating a critical frequency for the field. Based on the critical frequency of the field, the system and method treats field values that occur more than the critical frequency of the field as null field values and treats field values that occur less than the critical frequency as non-null field values.

Claims

1. A computer implemented method of detecting and treating one or more field values as null field values in records of an electronic database, the computer implemented method comprising:

selecting a field of the records;

determining, using a programmed computer, a frequency for each field value of the field, the frequency comprising an amount of the records in which the field value of the field appears;

calculating, using a programmed computer, a critical frequency for the field based on an ordered histogram of the frequency of each field value of the field, the critical frequency comprising a frequency at which a first point of a derivative of the ordered histogram decreases below a threshold; and

treating, using a programmed computer, each field value of the field with a_frequency that is greater than the critical frequency of the field as a null field value and each field value of the field with a frequency that is less than the critical frequency of the field as a non-null field value.

2. The computer implemented method of claim 1, wherein the calculating comprises ordering the frequencies of the field values of the field according to frequency along a horizontal axis of a histogram of the one or more field values of the field.

3. The computer implemented method of claim 2, wherein the calculating further comprises calculating a difference between adjacent frequencies in the histogram.

4. The computer implemented method of claim 1, wherein the calculating comprises calculating f(x)=g(x)−

g(x+1), wherein f is a function of the frequency differences based on a function g that is defined by the frequency of each field value of the field.

5. The computer implemented method of claim 4, wherein the critical frequency of the field is determined by determining the first point at which a derivative of the f function changes from a first sign to a second sign.

6. The computer implemented method of claim 4, wherein the critical frequency of the field is determined by determining the first point at which a derivative of the f function changes from a positive sign to a negative sign.

7. The computer implemented method of claim 4, wherein the critical frequency of the field is determined by determining the first point at which a derivative of the f function changes from a negative sign to a positive sign.

8. The computer implemented method of claim 4, wherein the critical frequency of the field is determined by determining the first point at which a derivative of the f function equals zero.

9. The computer implemented method of claim 4, wherein the critical frequency of the field is determined by determining the first point at which a derivative of the f function decreases below a threshold.

10. The computer implemented method of claim 1, wherein the treating further comprises treating each field value of the field with a frequency that is equal to the critical frequency of the field as a null field value.

11. The computer implemented method of claim 1, further comprising replacing one or more field values treated as null field values with a canonical null field value.

12. A computer implemented system of detecting and treating one or more field values as null field values in records of an electronic database, the computer implemented system comprising:

one or more computing apparatuses collectively configured to;

select a field of the records;

determine a frequency for each field value of the field, the frequency comprising an amount of the records in which the field value of the field appears;

calculate a critical frequency for the field based on an ordered histogram of the frequency of each field value of the field, the critical frequency comprising a frequency at which a first point of a derivative of the ordered histogram decreases below a threshold; and

treat each field value of the field with a frequency that is greater than the critical frequency of the field as a null field value and each field value of the field with a frequency that is less than the critical frequency of the field as a non-null field value.

13. The computer implemented system of claim 12, wherein the third computing apparatus is configured to calculate by ordering the frequencies of the field values of the field according to frequency along a horizontal axis of a histogram of the one or more field values of the field.

14. The computer implemented system of claim 13, wherein the third computing apparatus is further configured to calculate by calculating a difference between adjacent frequencies in the histogram.

15. The computer implemented system of claim 12, wherein the third computing apparatus is configured to calculate by calculating f(x)=g(x)−

g(x+1), wherein f is a function of the frequency differences based on a function g that is defined by the frequency of each field value of the field.

16. The computer implemented system of claim 15, wherein the critical frequency of the field is determined by determining the first point at which a derivative of the f function changes from a first sign to a second sign.

17. The computer implemented system of claim 15, wherein the critical frequency of the field is determined by determining the first point at which a derivative of the f function changes from a positive sign to a negative sign.

18. The computer implemented system of claim 15, wherein the critical frequency of the field is determined by determining the first point at which a derivative of the f function changes from a negative sign to a positive sign.

19. The computer implemented system of claim 15, wherein the critical frequency of the field is determined by determining the first point at which a derivative of the f function equals zero.

20. The computer implemented system of claim 15, wherein the critical frequency of the field is determined by determining the first point at which a derivative of the f function decreases below a threshold.

21. The computer implemented system of claim 12, wherein the fourth computing apparatus is further configured to treat each field value of the field with a frequency that is equal to the critical frequency of the field as a null field value.

22. The computer implemented system of claim 12, further comprising a fifth computing apparatus configured to replace one or more field values treated as null field values with a canonical null field value.