Profiling data with location information

• US 9,990,362 B2
• Filed: 09/21/2015
• Issued: 06/05/2018
• Est. Priority Date: 10/22/2012
• Status: Active Grant

• Current Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Original Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Inventors: Anderson, Arlen
• Primary Examiner(s): Hu, Jensen
• Application Number:
  US14/859,502
• Publication Number:
  US 20160012100A1
• Time in Patent Office: 988 Days
• Field of Search: 707687
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• 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/2228 Indexing structures
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database

Abstract

Profiling data includes processing an accessed collection of records, including: generating, for a first set of distinct values appearing in a first set of one or more fields, corresponding location information; generating, for the first set of fields, a corresponding list of entries identifying a distinct value from the first set of distinct values and the location information for the distinct value; generating, for a second set of one or more fields, a corresponding list of entries, with each entry identifying a distinct value from a second set of distinct values appearing in the second set of fields; and generating result information, based at least in part on: locating at least one record of the collection using the location information for at least one value appearing in the first set of fields, and determining at least one value appearing in the second set of fields of the located record.

Claims

1. A method for profiling data stored in at least one data storage system, the method including:

accessing at least one collection of records stored in the data storage system over an interface coupled to the data storage system; and

processing the collection of records to generate result information characterizing values appearing in one or more specified fields of the collection of records, the processing including;

generating, for a first set of distinct values appearing in a first set of one or more fields of the records in the collection, corresponding location information that identifies, for each distinct value in the first set of distinct values, every record in which the distinct value appears,

identifying, for a second set of one or more fields of the records in the collection different from the first set of one or more fields, a second set of distinct values appearing in the second set of one or more fields, and

generating the result information characterizing values appearing in the one or more specified fields of the collection of records, based at least in part on;

locating at least one record of the collection of records using the location information for at least one value appearing in the first set of one or more fields, and determining at least one value appearing in the second set of one or more fields of the located record.

2. The method of claim 1, wherein the processing further includes:

generating, for the second set of distinct values, corresponding location information that identifies, for each distinct value in the second set of distinct values, every record in which the distinct value appears.

3. The method of claim 2, wherein the processing further includes generating, for a set of distinct pairs of values, with a first value in each pair appearing in the first set of one or more fields of the records and a second value in each pair appearing in the second set of one or more fields of the records, corresponding location information that identifies, for each distinct pair of values, every record in which the distinct pair of values appears.

4. The method of claim 3, wherein generating location information for a distinct pair of values from the set of distinct pairs of values includes determining an intersection between location information for a first distinct value from the first set of distinct values and location information for a second distinct value from the second set of distinct values.

5. The method of claim 4, wherein determining the intersection includes using the location information for the first distinct value to locate a record in the collection, and using the located record to determine the second distinct value.

6. The method of claim 1, wherein the processing further includes:

generating, for a set of distinct pairs of values, with a first value in each pair appearing in the first set of one or more fields of the records and a second value in each pair appearing in a second set of one or more fields of the records different from the first set of one or more fields, corresponding location information that identifies, for each distinct pair of values, every record in which the distinct pair of values appears, and

generating, for the set of distinct pairs of values, a corresponding list of entries, with each entry identifying a distinct pair of values from the set of distinct pairs of values, and the location information for the distinct pair of values.

7. The method of claim 1, wherein the location information identifies a unique index value for every record in which the distinct value appears.

8. The method of claim 7, wherein the location information identifies a particular unique index value by storing that particular unique index value.

9. The method of claim 7, wherein the location information identifies a unique index value by encoding the unique index value within the location information.

10. The method of claim 9, wherein encoding the unique index value includes storing a bit at a position within a vector corresponding to the unique index value.

11. The method of claim 1, wherein the collection includes a first subset of records with fields including the first set of one or more fields, and a second subset of records with fields including the second set of one or more fields.

12. The method of claim 11, wherein the processing further includes generating information that provides a mapping between:

(1) index values of a field of the first subset of records that associates a unique index value with every record in the first subset, and (2) key values of a field of the second subset of records that associates a key value with every record in the second subset of values;

wherein the key value links records in the second subset with records in the first subset.

13. The method of claim 12, wherein the location information identifies the unique index values for every record in which the distinct value appears.

14. A computer program, stored on a computer-readable storage medium, for profiling data stored in at least one data storage system, the computer program including instructions for causing a computing system to:

access at least one collection of records stored in the data storage system over an interface coupled to the data storage system; and

process the collection of records to generate result information characterizing values appearing in one or more specified fields of the collection of records, the processing including;

generating, for a first set of distinct values appearing in a first set of one or more fields of the records in the collection, corresponding location information that identifies, for each distinct value in the first set of distinct values, every record in which the distinct value appears,

identifying, for a second set of one or more fields of the records in the collection different from the first set of one or more fields, a second set of distinct values appearing in the second set of one or more fields, and

generating the result information characterizing values appearing in the one or more specified fields of the collection of records, based at least in part on;

locating at least one record of the collection of records using the location information for at least one value appearing in the first set of one or more fields, and determining at least one value appearing in the second set of one or more fields of the located record.

17. The computer program of claim 14, wherein the processing further includes:

generating, for the second set of distinct values, corresponding location information that identifies, for each distinct value in the second set of distinct values, every record in which the distinct value appears.

18. The computer program of claim 17, wherein the processing further includes generating, for a set of distinct pairs of values, with a first value in each pair appearing in the first set of one or more fields of the records and a second value in each pair appearing in the second set of one or more fields of the records, corresponding location information that identifies, for each distinct pair of values, every record in which the distinct pair of values appears.

19. The computer program of claim 18, wherein generating location information for a distinct pair of values from the set of distinct pairs of values includes determining an intersection between location information for a first distinct value from the first set of distinct values and location information for a second distinct value from the second set of distinct values.

20. The computer program of claim 19, wherein determining the intersection includes using the location information for the first distinct value to locate a record in the collection, and using the located record to determine the second distinct value.

21. The computer program of claim 14, wherein the processing further includes:

generating, for a set of distinct pairs of values, with a first value in each pair appearing in the first set of one or more fields of the records and a second value in each pair appearing in a second set of one or more fields of the records different from the first set of one or more fields, corresponding location information that identifies, for each distinct pair of values, every record in which the distinct pair of values appears, and

generating, for the set of distinct pairs of values, a corresponding list of entries, with each entry identifying a distinct pair of values from the set of distinct pairs of values, and the location information for the distinct pair of values.

22. The computer program of claim 14, wherein the location information identifies a unique index value for every record in which the distinct value appears.

23. The computer program of claim 22, wherein the location information identifies a particular unique index value by storing that particular unique index value.

24. The computer program of claim 22, wherein the location information identifies a unique index value by encoding the unique index value within the location information.

25. The computer program of claim 24, wherein encoding the unique index value includes storing a bit at a position within a vector corresponding to the unique index value.

26. The computer program of claim 14, wherein the collection includes a first subset of records with fields including the first set of one or more fields, and a second subset of records with fields including the second set of one or more fields.

27. The computer program of claim 26, wherein the processing further includes generating information that provides a mapping between:

(1) index values of a field of the first subset of records that associates a unique index value with every record in the first subset, and (2) key values of a field of the second subset of records that associates a key value with every record in the second subset of values;

wherein the key value links records in the second subset with records in the first subset.

28. The computer program of claim 27, wherein the location information identifies the unique index values for every record in which the distinct value appears.

15. A computing system for profiling data stored in at least one data storage system, the computing system including:

an interface coupled to the data storage system configured to access at least one collection of records stored in the data storage system; and

at least one processor configured to process the collection of records to generate result information characterizing values appearing in one or more specified fields of the collection of records, the processing including;

generating, for a first set of distinct values appearing in a first set of one or more fields of the records in the collection, corresponding location information that identifies, for each distinct value in the first set of distinct values, every record in which the distinct value appears,

identifying, for a second set of one or more fields of the records in the collection different from the first set of one or more fields, a second set of distinct values appearing in the second set of one or more fields, and

generating the result information characterizing values appearing in the one or more specified fields of the collection of records, based at least in part on;

locating at least one record of the collection of records using the location information for at least one value appearing in the first set of one or more fields, and determining at least one value appearing in the second set of one or more fields of the located record.

29. The computing system of claim 15, wherein the processing further includes:

generating, for the second set of distinct values, corresponding location information that identifies, for each distinct value in the second set of distinct values, every record in which the distinct value appears.

30. The computing system of claim 29, wherein the processing further includes generating, for a set of distinct pairs of values, with a first value in each pair appearing in the first set of one or more fields of the records and a second value in each pair appearing in the second set of one or more fields of the records, corresponding location information that identifies, for each distinct pair of values, every record in which the distinct pair of values appears.

31. The computing system of claim 30, wherein generating location information for a distinct pair of values from the set of distinct pairs of values includes determining an intersection between location information for a first distinct value from the first set of distinct values and location information for a second distinct value from the second set of distinct values.

32. The computing system of claim 31, wherein determining the intersection includes using the location information for the first distinct value to locate a record in the collection, and using the located record to determine the second distinct value.

33. The computing system of claim 15, wherein the processing further includes:

generating, for a set of distinct pairs of values, with a first value in each pair appearing in the first set of one or more fields of the records and a second value in each pair appearing in a second set of one or more fields of the records different from the first set of one or more fields, corresponding location information that identifies, for each distinct pair of values, every record in which the distinct pair of values appears, and

generating, for the set of distinct pairs of values, a corresponding list of entries, with each entry identifying a distinct pair of values from the set of distinct pairs of values, and the location information for the distinct pair of values.

34. The computing system of claim 15, wherein the location information identifies a unique index value for every record in which the distinct value appears.

35. The computing system of claim 34, wherein the location information identifies a particular unique index value by storing that particular unique index value.

36. The computing system of claim 34, wherein the location information identifies a unique index value by encoding the unique index value within the location information.

37. The computing system of claim 36, wherein encoding the unique index value includes storing a bit at a position within a vector corresponding to the unique index value.

38. The computing system of claim 15, wherein the collection includes a first subset of records with fields including the first set of one or more fields, and a second subset of records with fields including the second set of one or more fields.

39. The computing system of claim 38, wherein the processing further includes generating information that provides a mapping between:

(1) index values of a field of the first subset of records that associates a unique index value with every record in the first subset, and (2) key values of a field of the second subset of records that associates a key value with every record in the second subset of values;

wherein the key value links records in the second subset with records in the first subset.

40. The computing system of claim 39, wherein the location information identifies the unique index values for every record in which the distinct value appears.

16. A computing system for profiling data stored in at least one data storage system, the computing system including:

means for accessing at least one collection of records stored in the data storage system; and

means for processing the collection of records to generate result information characterizing values appearing in one or more specified fields of the collection of records, the processing including;

generating, for a first set of distinct values appearing in a first set of one or more fields of the records in the collection, corresponding location information that identifies, for each distinct value in the first set of distinct values, every record in which the distinct value appears,

identifying, for a second set of one or more fields of the records in the collection different from the first set of one or more fields, a second set of distinct values appearing in the second set of one or more fields, and

generating the result information characterizing values appearing in the one or more specified fields of the collection of records, based at least in part on;

locating at least one record of the collection of records using the location information for at least one value appearing in the first set of one or more fields, and determining at least one value appearing in the second set of one or more fields of the located record.