SQI-based automated, adaptive, histogram bin data description assist

• US 6,549,910 B1
• Filed: 10/01/1999
• Issued: 04/15/2003
• Est. Priority Date: 10/02/1998
• Status: Expired due to Term

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation (NCR Voyix Corporation)
• Inventors: Tate, Brian Don
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US09/410,534
• Time in Patent Office: 1,292 Days
• Field of Search: 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/3346 using probabilistic model
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/961 Associative
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• 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/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method, apparatus, and article of manufacture for performing data mining applications in a massively parallel relational database management system. A scalable data mining function comprising an automated, adaptive, histogram bin data description assist function is instantiated and parameterized via an analytic application programming interface (API). The automated, adaptive, histogram bin data description assist function comprises a query that is performed directly within the relational database management system, wherein the automated, adaptive, histogram bin data description assist function counts a number of occurrences of values in value ranges for a numeric data element in a column of a table stored in the relational database.

Claims

1. A computer-implemented system for performing data mining applications, comprising:

(a) a computer having one or more data storage devices connected thereto, wherein a relational database is stored on one or more of the data storage devices;

(b) a relational database management system, executed by the computer, for accessing the relational database stored on the data storage devices; and

(c) an analytic application programming interface (API), executed by the computer, that generates an automated, adaptive, histogram bin data description assist function performed directly within the relational database management system,

(d) wherein the automated, adaptive, histogram bin data description assist function counts a number of occurrences of values in value ranges for a numeric data element in a column of a table stored in the relational database,

(e) wherein the automated, adaptive, histogram bin data description assist function creates a plurality of bins, and each of the bins stores a selected range of values for the numeric data element; and

(e) wherein the automated, adaptive, histogram bin data description assist function accepts one or more parameters selected from a group comprising;

a table name, a name of a numeric column in the table, a desired number of equal sized bins, a frequency percentage above which a value of the numeric data element should be treated as a spike, a percentage above which a bin should be further subdivided into sub-bins, a WHERE clause that reduces a beginning and ending range of the bins, and a WHERE clause that filters rows.

2. The system of claim 1, wherein the automated, adaptive, histogram bin data description assist function returns counts of numeric data elements in each of the bins.

3. The system of claim 1, wherein the automated, adaptive, histogram bin data description assist function returns starting and ending boundary values for each bin.

4. The system of claim 1, wherein the automated, adaptive, histogram bin data description assist function creates a separate bin for each spike value of the numeric data element found therein.

5. The system of claim 1, wherein the automated, adaptive, histogram bin data description assist function subdivides a bin that is overpopulated into a plurality of sub-bins, each of the sub-bins storing a selected range of values for the numeric data element.

6. The system of claim 5, wherein the automated, adaptive, histogram bin data description assist function returns counts of numeric data elements in each of the sub-bin.

7. The system of claim 5, wherein the automated, adaptive, histogram bin data description assist function returns beginning and ending boundary values for each sub-bin.

8. The system of claim 5, wherein the bins are comprised of a type selected from a group comprising individual value bins, range bins, or sub-range bins.

9. The system of claim 5, wherein a selected range of values for the numeric data element is identified by a beginning range value and an ending range value.

10. The system of claim 9, wherein the beginning range values are inclusive and the ending range values are exclusive.

11. The system of claim 9, wherein a last one of the ending range values is inclusive.

12. The system of claim 9, wherein the ending range value of a spike value is inclusive.

13. The system of claim 9, wherein the beginning range value of a bin that follows and adjoins a spike value is exclusive.

14. The system of claim 1, wherein the counts are selected from a group comprising counts of individual frequently occurring values, counts of ranges of values, and counts of sub-ranges of heavily populated ranges.

15. The system of claim 1, wherein a select of the relational database is repeated for each column if multiple columns are requested.

16. The system of claim 15, wherein a create table function for a result table occurs only once with the repeated select.

18. The system of claim 1, wherein the computer comprises a parallel processing computer comprised of a plurality of nodes, and each node executes one or more threads of the relational database management system to provide parallelism in the automated histogram bin data description assist function.

19. The system of claim 1, wherein the automated, adaptive, histogram bin data description assist function processes data stored in the relational database and produces results that are stored in the relational database.

20. The system of claim 1, wherein the automated, adaptive, histogram bin data description assist function does not extract the data elements from the relational database.

21. The system of claim 1, wherein results from the automated, adaptive, histogram bin data description assist function are saved in a table in an analytic logical data model in the relational database.

22. The system of claim 1, wherein the automated, adaptive, histogram bin data description assist function is created by parameterizing and instantiating the analytic API.

23. The system of claim 1, wherein the automated, adaptive, histogram bin data description assist function comprises at least one statement for execution by the relational database management system.

24. The system of claim 1, wherein the automated, adaptive, histogram bin data description assist function is a dynamically generated statement comprised of combined phrases with substituting values therein based on parameters supplied to the analytic API.

17. A computer-implemented system for performing data mining applications, comprising:

(a) a computer having one or more data storage devices connected thereto, wherein a relational database is stored on one or more of the data storage devices;

(b) a relational database management system, executed by the computer, for accessing the relational database stored on the data storage devices; and

(c) an analytic application programming interface (API), executed by the computer, that generates an automated, adaptive, histogram bin data description assist function performed directly within the relational database management system,

(d) wherein the automated, adaptive, histogram bin data description assist function counts a number of occurrences of values in value ranges for a numeric data element in a column of a table stored in the relational database,

(e) wherein the function makes three logical passes of the data in the relational database, and each pass uses information gathered in a previous pass, and the three logical passes comprise;

(1) a first pass that determines a count of specific values occurring above a threshold frequency by percentage,

(2) a second pass that counts values in a plurality of ranges of values based on dividing an overall range of values for the numeric data element into a specified number of bins, and then combining counts for these bins with the count of frequently occurring values found in the first pass,

(3) a third pass that sub-divides the bins from the second pass that contain greater than a threshold frequency by percentage of the counts and adds these counts to the counts obtained in the first and second passes,

wherein the result is an ordered list of counts and ranges for each bin with an indication of a type for each bin.

25. A method for performing data mining applications, comprising:

(a) storing a relational database on one or more data storage devices connected to a computer;

(b) accessing the relational database stored on the data storage devices using a relational database management system; and

(c) executing an analytic application programming interface (API) in the computer to generate an automated, adaptive, histogram bin data description assist function performed directly within the relational database management system,

(d) wherein the automated, adaptive, histogram bin data description assist function counts a number of occurrences of values in value ranges for a numeric data element in a column of a table stored in the relational database;

(e) wherein the automated, adaptive, histogram bin data description assist function creates a plurality of bins, and each of the bins stores a selected range of values for the numeric data element; and

(e) wherein the automated, adaptive, histogram bin data description assist function accepts one or more parameters selected from a group comprising;

a table name, a name of a numeric column in the table, a desired number of equal sized bins, a frequency percentage above which a value of the numeric data element should be treated as a spike, a percentage above which a bin should be further subdivided into sub-bins, a WHERE clause that reduces a beginning and ending range of the bins, and a WHERE clause that filters rows.

26. The method of claim 25, wherein the automated, adaptive, histogram bin data description assist function returns counts of numeric data elements in each of the bins.

27. The method of claim 25, wherein the automated, adaptive, histogram bin data description assist function returns starting and ending boundary values for each bin.

28. The method of claim 25, wherein the automated, adaptive, histogram bin data description assist function creates a separate bin for each spike value of the numeric data element found therein.

29. The method of claim 25, wherein the automated, adaptive, histogram bin data description assist function subdivides a bin that is overpopulated into a plurality of sub-bins, each of the sub-bins storing a selected range of values for the numeric data element.

30. The method of claim 29, wherein the automated, adaptive, histogram bin data description assist function returns counts of numeric data elements in each of the sub-bin.

31. The method of claim 29, wherein the automated, adaptive, histogram bin data description assist function returns beginning and ending boundary values for each sub-bin.

32. The method of claim 29, wherein the bins are comprised of a type selected from a group comprising individual value bins, range bins, or sub-range bins.

33. The method of claim 29, wherein a selected range of values for the numeric data element is identified by a beginning range value and an ending range value.

34. The method of claim 33, wherein the beginning range values are inclusive and the ending range values are exclusive.

35. The method of claim 33, wherein a last one of the ending range values is inclusive.

36. The method of claim 33, wherein the ending range value of a spike value is inclusive.

37. The method of claim 33, wherein the beginning range value of a bin that follows and adjoins a spike value is exclusive.

38. The method of claim 25, wherein the counts are selected from a group comprising counts of individual frequently occurring values, counts of ranges of values, and counts of sub-ranges of heavily populated ranges.

39. The method of claim 25, wherein a select of the relational database is repeated for each column if multiple columns are requested.

40. The method of claim 25, wherein a create table function for a result table occurs only once with the repeated select.

41. The method of claim 25, wherein the computer comprises a parallel processing computer comprised of a plurality of nodes, and each node executes one or more threads of the relational database management system to provide parallelism in the automated histogram bin data description assist function.

42. The method of claim 25, wherein the automated, adaptive, histogram bin data description assist function processes data stored in the relational database and produces results that are stored in the relational database.

43. The method of claim 25, wherein the automated, adaptive, histogram bin data description assist function does not extract the data elements from the relational database.

44. The method of claim 25, wherein results from the automated, adaptive, histogram bin data description assist function are saved in a table in an analytic logical data model in the relational database.

45. The method of claim 25, wherein the automated, adaptive, histogram bin data description assist function is created by parameterizing and instantiating the analytic API.

46. The method of claim 25, wherein the automated, adaptive, histogram bin data description assist function comprises at least one statement for execution by the relational database management system.

47. The method of claim 25, wherein the automated, adaptive, histogram bin data description assist function is a dynamically generated statement comprised of combined phrases with substituting values therein based on parameters supplied to the analytic API.

48. An article of manufacture comprising logic embodying a method for performing data mining applications, comprising:

(a) storing a relational database on one or more data storage devices connected to a computer;

(b) accessing the relational database stored on the data storage devices using a relational database management system; and

(c) executing an analytic application programming interface (API) in the computer to generate an automated, adaptive, histogram bin data description assist function performed directly within the relational database management system,

(d) wherein the automated histogram bin data description assist function counts a number of occurrences of values in value ranges for a numeric data element in a column of a table stored in the rational database;

(e) wherein the automated, adaptive, histogram bin data description assist function creates a plurality of bins, and each of the bins stores a selected range of values for the numeric data element; and

(e) wherein the automated, adaptive, histogram bin data description assist function accepts one or more parameters selected from a group comprising;

a table name, a name of a numeric column in the table, a desired number of equal sized bins, a frequency percentage above which a value of the numeric data element should be treated as a spike, a percentage above which a bin should be further subdivided into sub-bins, a WHERE clause that reduces a beginning and ending range of the bins, and a WHERE clause that filters rows.

49. The article of manufacture of claim 48, wherein the automated, adaptive, histogram bin data description assist function returns counts of numeric data elements in each of the bins.

50. The article of manufacture of claim 48, wherein the automated, adaptive, histogram bin data description assist function returns starting and ending boundary values for each bin.

51. The article of manufacture of claim 48, wherein the automated, adaptive, histogram bin data description assist function creates a separate bin for each spike value of the numeric data element found therein.

52. The article of manufacture of claim 48, wherein the automated, adaptive, histogram bin data description assist function subdivides a bin that is overpopulated into a plurality of sub-bins, each of the sub-bins storing a selected range of values for the numeric data element.

53. The article of manufacture of claim 52, wherein the automated, adaptive, histogram bin data description assist function returns counts of numeric data elements in each of the sub-bin.

54. The article of manufacture of claim 52, wherein the automated, adaptive, histogram bin data description assist function returns beginning and ending boundary values for each sub-bin.

55. The article of manufacture of claim 52, wherein the bins are comprised of a type selected from a group comprising individual value bins, range bins, or sub-range bins.

56. The article of manufacture of claim 52, wherein a selected range of values for the numeric data element is identified by a beginning range value and an ending range value.

57. The article of manufacture of claim 56, wherein the beginning range values are inclusive and the ending range values are exclusive.

58. The article of manufacture of claim 56, wherein a last one of the ending range values is inclusive.

59. The article of manufacture of claim 56, wherein the ending range value of a spike value is inclusive.

60. The article of manufacture of claim 56, wherein the beginning range value of a bin that follows and adjoins a spike value is exclusive.

61. The article of manufacture of claim 48, wherein the counts are selected from a group comprising counts of individual frequently occurring values, counts of ranges of values, and counts of sub-ranges of heavily populated ranges.

62. The article of manufacture of claim 48, wherein a select of the relational database is repeated for each column if multiple columns are requested.

63. The article of manufacture of claim 48, wherein a create table function for a result table occurs only once with the repeated select.

64. The article of manufacture of claim 48, wherein the computer comprises a parallel processing computer comprised of a plurality of nodes, and each node executes one or more threads of the relational database management system to provide parallelism in the automated histogram bin data description assist function.

65. The article of manufacture of claim 48, wherein the automated, adaptive, histogram bin data description assist function processes data stored in the relational database and produces results that are stored in the relational database.

66. The article of manufacture of claim 48, wherein the automated, adaptive, histogram bin data description assist function does not extract the data elements from the relational database.

67. The article of manufacture of claim 48, wherein results from the automated, adaptive, histogram bin data description assist function are saved in a table in an analytic logical data model in the relational database.

68. The article of manufacture of claim 48, wherein the automated, adaptive, histogram bin data description assist function is created by parameterizing and instantiating the analytic API.

69. The article of manufacture of claim 48, wherein the automated, adaptive, histogram bin data description assist function comprises at least one statement for execution by the relational database management system.

70. The article of manufacture of claim 48, wherein the automated, adaptive, histogram bin data description assist function is a dynamically generated statement comprised of combined phrases with substituting values therein based on parameters supplied to the analytic API.

71. A method for performing data mining applications, comprising:

(a) storing a relational database on one or more data storage devices connected to a computer;

(b) accessing the relational database stored on the data storage devices using a relational database management system; and

(c) executing an analytic application programming interface (API) in the computer to generate an automated, adaptive, histogram bin data description assist function performed directly within the relational database management system,

(d) wherein the automated, adaptive, histogram bin data description assist function counts a number of occurrences of values in value ranges for a numeric data element in a column of a table stored in the relational database;

(e) wherein the function makes three logical passes of the data in the relational database, and each pass uses information gathered in a previous pass, and the three logical passes comprise;

(1) a first pass that determines a count of specific values occurring above a threshold frequency by percentage,

(2) a second pass that counts values in a plurality of ranges of values based on dividing an overall range of values for the numeric data element into a specified number of bins, and then combining counts for these bins with the count of frequently occurring values found in the first pass,

(3) a third pass that sub-divides the bins from the second pass that contain greater than a threshold frequency by percentage of the counts and adds these counts to the counts obtained in the first and second passes,

wherein the result is an ordered list of counts and ranges for each bin with an indication of a type for each bin.

72. An article of manufacture comprising logic embodying a method for performing data mining applications, comprising:

(a) storing a relational database on one or more data storage devices connected to a computer;

(b) accessing the relational database stored on the data storage devices using a relational database management system; and

(c) executing an analytic application programming interface (API) in the computer to generate an automated, adaptive, histogram bin data description assist function performed directly within the relational database management system,

(d) wherein the automated, adaptive, histogram bin data description assist function counts a number of occurrences of values in value ranges for a numeric data element in a column of a table stored in the relational database;

(e) wherein the function makes three logical passes of the data in the relational database, and each pass uses information gathered in a previous pass, and the three logical passes comprise;

(1) a first pass that determines a count of specific values occurring above a threshold frequency by percentage,

(2) a second pass that counts values in a plurality of ranges of values based on dividing an overall range of values for the numeric data element into a specified number of bins, and then combining counts for these bins with the count of frequently occurring values found in the first pass,

(3) a third pass that sub-divides the bins from the second pass that contain greater than a threshold frequency by percentage of the counts and adds these counts to the counts obtained in the first and second passes,

wherein the result is an ordered list of counts and ranges for each bin with an indication of a type for each bin.