Performing data mining operations within a columnar database management system

• US 9,798,783 B2
• Filed: 06/12/2014
• Issued: 10/24/2017
• Est. Priority Date: 06/14/2013
• Status: Active Grant

• Current Assignee: Open Text Holdings, Inc. (Open Text Corporation)
• Original Assignee: Actuate Corporation (Open Text Corporation)
• Inventors: Martin, Carles Bays, Poyatos, Jess Malo, Sierra, Marc Rodrguez, Prez, Alejandro Sualdea
• Primary Examiner(s): Morrison, Jay
• Assistant Examiner(s): Hoang, Ken
• Application Number:
  US14/303,581
• Publication Number:
  US 20140372482A1
• Time in Patent Office: 1,230 Days
• Field of Search: 705 2, 705 11, 705 36 R, 705 711, 705 725, 705 1449, 705 1458, 705304, 705305, 705310, 705322, 705348, 705 35, 705 37, 705 4, 705 736, 700 83, 700 17, 700259, 700 11, 700253, 700275, 700 49, 700 66, 707718, 707E17014, 707E17005, 707722, 707776, 707999002, 707E17001, 707E17017, 707E17032, 707E17082, 707E17108, 707603, 707707, 707723, 707827, 703 1, 703 13, 703 6, 706 52, 706 11, 706 12, 706 16, 706 20, 706 25, 706 27, 706 44, 706 45, 706 46, 706 47, 706 54
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases

Abstract

Data mining operations are performed within a columnar database management system. The columnar database management system stores input sets of data for a data mining operation. An input set of data is represented as a column of data in the columnar database management system. The columnar database management system stores instructions to perform one or more data mining operations for processing the input sets of data. The columnar database management system receives requests for performing data mining operations and performs the processing of the data mining operation within the columnar database management system. As a result, the processing of data mining operations is performed without requiring multiple data transfers between an application implementing the data mining operations and the columnar database management system.

Claims

1. A computer-implemented method for performing data mining operations using a columnar database management system, the method comprising:

storing one or more input sets of data for analysis by a data mining operation within a columnar database management system;

storing, in the columnar database management system, instructions to perform one or more data mining operations for processing the input sets of data that at least discovers patterns in the input sets of data, the input sets of data represented as columns of data in the columnar database management system;

receiving, over a network from a client device, a request to perform a data mining operation on the one or more input sets of data; and

responsive to receiving the request, obtaining by the columnar database management system, a set of data mining results, the obtaining comprising;

parsing the data mining request within the columnar database management system, the parsing identifying a data mining operation and specifying data items,

determining various steps for processing the requested data mining operation, the determining performed by the columnar database management system based at least in part on the data items specified by the data mining request, the data mining operation identified by the data mining request, or a combination thereof,

the various steps comprising;

identifying, based on an internal table or data structure of the columnar database management system, additional data mining operations necessary to complete processing of the data mining request,

acquiring one or more resources necessary for processing the data items indicated by the data mining request,

performing at least one pre-allocation procedure on the one or more resources thus acquired, and

determining an order of execution for the additional data mining operations thus identified,

generating a data mining processing plan comprising the various steps for processing the requested data mining operation, and

executing the data mining processing plan to obtain the set of data mining results of the requested data mining operation; and

sending the set of data mining results obtained by the columnar database management system to the client device from which the request is received over the network.

2. The computer-implemented method of claim 1, wherein the data mining operation comprises one of:

clustering, classification, regression analysis, summarization, association mining, or anomaly detection.

3. The computer-implemented method of claim 1, wherein the data mining operation is a first data mining operation and the data mining processing plan comprises at least a step executing a second data mining operation, wherein an output of the second data mining operation is provided as input to a subsequent step of the data mining processing plan, the output of the second data mining operation transferred to a subsequent step of the data mining processing plan, the transfer performed within the columnar database management system.

4. The computer-implemented method of claim 3, wherein the first data mining operation is a decision tree operation and the second data mining operation is a cross tabulation operation.

5. The computer-implemented method of claim 1, further comprising:

estimating an amount of memory needed for the data mining operation based on an amount of memory used by a previous execution of the corresponding data mining operation; and

using the estimated amount of memory for memory pre-allocation for the data mining operation.

6. The computer-implemented method of claim 1, further comprising:

estimating a duration of execution of the data mining operation based on a duration of execution of a previous execution of the corresponding data mining operation; and

using the estimated duration of execution for optimizing the execution of the data mining operation.

7. The computer-implemented method of claim 1, wherein the data mining processing plan includes a first step processing a first set of input sets and a second step processing a second set of input sets, the method further comprising:

determining an order of execution of the steps of the data mining processing plan such that the second step is executed after the first step responsive to the first set of input sets being included in the second set of input sets.

8. The computer-implemented method of claim 1, wherein the data mining operations comprise a cross tabulation operation and processing the cross tabulation operation comprises:

for each row combination of result, wherein the row combination has one or more attribute values of input columns;

identifying data of input sets having the attribute values;

determining an intersection set of the identified data; and

determining the output value for the combination of result based on the intersection set.

9. The computer-implemented method of claim 1, wherein the data mining operation comprises generation of a Venn diagram.

10. The computer-implemented method of claim 1, wherein the data mining operations comprise a decision tree operation to classify a set of data items into various groups.

11. The computer-implemented method of claim 1, wherein the data mining operations comprise one or more of association rule algorithms, clustering algorithms, or time series algorithms.

12. A non-transitory computer readable storage medium storing instructions for:

storing one or more input sets of data for analysis by a data mining operation within a columnar database management system, an input set represented as a column of data;

storing, in the columnar database management system, instructions to perform one or more data mining operations for processing the input sets of data that at least discovers patterns in the input sets of data, the input sets of data represented as columns of data in the columnar database management system;

receiving, over a network from a client device, a request to perform a data mining operation on the one or more input sets of data; and

responsive to receiving the request, obtaining by the columnar database management system, a set of data mining results, the obtaining comprising;

parsing the data mining request within the columnar database management system, the parsing identifying a data mining operation and specifying data items,

determining various steps for processing the requested data mining operation, the determining performed by the columnar database management system based at least in part on the data items specified by the data mining request, the data mining operation identified by the data mining request, or a combination thereof,

the various steps comprising;

identifying, based on an internal table or data structure of the columnar database management system, additional data mining operations necessary to complete processing of the data mining request,

acquiring one or more resources necessary for processing the data items indicated by the data mining request,

performing at least one pre-allocation procedure on the one or more resources thus acquired, and

determining an order of execution for the additional data mining operations thus identified,

generating a data mining processing plan comprising the various steps for processing the requested data mining operation, and

executing the data mining processing plan to obtain the set of data mining results of the requested data mining operation; and

sending the set of data mining results obtained by the columnar database management system to the client device from which the request is received over the network.

13. The non-transitory computer readable storage medium of claim 12, wherein the data mining operation is a first data mining operation and the data mining processing plan comprises at least a step executing a second data mining operation, wherein an output of the second data mining operation is provided as input to a subsequent step of the data mining processing plan, the output of the second data mining operation transferred to a subsequent step of the data mining processing plan, the transfer performed within the columnar database management system.

14. The non-transitory computer readable storage medium of claim 12, further comprising instructions for:

estimating an amount of memory needed for the data mining operation based on an amount of memory used by a previous execution of the corresponding data mining operation; and

using the estimated amount of memory for memory pre-allocation for the data mining operation.

15. The non-transitory computer readable storage medium of claim 12, further comprising instructions for:

estimating a duration of execution of the data mining operation based on a duration of execution of a previous execution of the corresponding data mining operation; and

using the estimated duration of execution for optimizing the execution of the data mining operation.

16. The non-transitory computer readable storage medium of claim 12, wherein the data mining processing plan includes a first step processing a first set of input sets and a second step processing a second set of input sets, further comprising instructions for:

determining an order of execution of the steps of the data mining processing plan such that the second step is executed after the first step responsive to the first set of input sets being included in the second set of input sets.

17. The non-transitory computer readable storage medium of claim 12, wherein the data mining operation is a cross tabulation operation and processing the cross tabulation operation comprises:

for each row combination of result, wherein the row combination has one or more attribute values of input columns;

identifying data of input sets having the attribute values;

determining an intersection set of the identified data; and

determining the output value for the combination of result based on the intersection set.

18. A computer-implemented system comprising:

a computer processor; and

a non-transitory computer-readable storage medium storing instructions for;

storing one or more input sets of data for analysis by a data mining operation within a columnar database management system, an input set represented as a column of data;

storing, in the columnar database management system, instructions to perform one or more data mining operations for processing the input sets of data that at least discovers patterns in the input sets of data, the input sets of data represented as columns of data in the columnar database management system;

receiving, over a network from a client device, a request to perform a data mining operation on the one or more input sets of data; and

responsive to receiving the request, obtaining by the columnar database management system, a set of data mining results, the obtaining comprising;

parsing the data mining request within the columnar database management system, the parsing identifying a data mining operation and specifying data items,

determining various steps for processing the requested data mining operation, the determining performed by the columnar database management system based at least in part on the data mining request, the data mining operation identified by the data mining request, or a combination thereof,

the various steps comprising;

identifying, based on an internal table or data structure of the columnar database management system, additional data mining operations necessary to complete processing of the data mining request,

acquiring one or more resources necessary for processing the data items indicated by the data mining request,

performing at least one pre-allocation procedure on the one or more resources thus acquired, and

determining an order of execution for the additional data mining operations thus identified,

generating a data mining processing plan comprising the various steps for processing the requested data mining operation, and

executing the data mining processing plan to obtain the set of data mining results of the requested data mining operation; and

sending the set of data mining results obtained by the columnar database management system to the client device from which the request is received over the network.

19. The computer-implemented system of claim 18, wherein the data mining operation is a first data mining operation and the data mining processing plan comprises at least a step executing a second data mining operation, wherein an output of the second data mining operation is provided as input to a subsequent step of the data mining processing plan, the output of the second data mining operation transferred to a subsequent step of the data mining processing plan, the transfer performed within the columnar database management system.

20. The computer-implemented system of claim 18, wherein the non-transitory computer-readable storage medium further stores instructions for:

estimating an amount of memory needed for the data mining operation based on an amount of memory used by a previous execution of the corresponding data mining operation; and

using the estimated amount of memory for memory pre-allocation for the data mining operation.