Method, system, and computer program product for computing histogram aggregations

• US 5,960,435 A
• Filed: 03/11/1997
• Issued: 09/28/1999
• Est. Priority Date: 03/11/1997
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Haber, Eben M., Rathmann, Peter K.
• Primary Examiner(s): Von Buhr, Maria N.
• Application Number:
  US08/815,473
• Time in Patent Office: 931 Days
• Field of Search: 707/1-4, 707/7, 707/101, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• 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 data record transformation that computes histograms and aggregations quickly for an incoming record stream. The data record transformation computes histograms and aggregations in one-step, thereby, avoiding the creation of a large intermediate result. The data record transformation operates in a streaming fashion on each record in an incoming record stream. Little memory is required to operate on one record or a few records at a time. According to a first embodiment, a method, system, and computer program product for transforming sorted data records is provided. A data transformation unit includes a binning module and a histogram aggregation module. The histogram aggregation module processes each binned and sorted record to form an aggregate record in a histogram format in one step. Data received in each incoming binned and sorted record is expanded and accumulated in an aggregate record for matching group-by fields. According to a second embodiment, a method, system, and computer program product for transforming unsorted data records is provided. An associative data structure holds a collection of partially aggregated histogram records. A histogram aggregation module processes each binned record to form an aggregate record in a histogram format in one step. Input records from the unordered record stream are matched against the collection of partially aggregated histogram records and expanded and accumulated into the aggregate histogram record having matching group-by fields.

Claims

1. A system for transforming a stream of sorted input data records into an aggregate record, each input data record including at least one group-by field, at least one field to be binned, and at least one value field, and each aggregate record including at least one group-by field and an aggregation result field, wherein the input data record group-by field stores data to be matched against data stored in the aggregate record group-by field, wherein the input data records are sorted by the data in the group-by field, wherein the value field stores data to be aggregated, and wherein the aggregation result field includes at least one location and stores aggregated data in a histogram format, the system comprising:

a binning module that, for each input data record in the stream, evaluates data in the input data record field to be binned to determine a bin-index value, wherein the bin-index value identifies locations of the aggregation result field the value field data should be aggregated into; and

a histogram aggregation module that, for each input data record in the stream, aggregates the value field data into the aggregation result field location identified by the bin-index value, when data in the input data record group-by field matches data in the aggregate record group-by field.

2. The system of claim 1, further comprising:

an output module that outputs the aggregated data in the histogram format stored in the aggregation result field of the aggregate record once data in the input data record group-by field does not match data in the aggregate record group-by field.

3. A method for transforming a stream of sorted input data records into an aggregate record, each input data record including at least one group-by field, at least one field to be binned, and at least one value field, and each aggregate record including at least one group-by field and an aggregation result field, wherein the input data record group-by field stores data to be matched against data stored in the aggregate record group-by field, wherein the input data records are sorted by the data in the group-by field, wherein the value field stores data to be aggregated, and wherein the aggregation result field includes at least one location and stores aggregated data in a histogram format, the method comprising the steps of:

evaluating, for each input data record in the stream, data in the input data record field to be binned to determine a bin-index value, wherein the bin-index value identifies locations of the aggregation result field the value field data should be aggregated into; and

for each input data record in the stream, aggregating the value field data into the aggregation result field location identified by the bin-index value, when data in the input data record group-by field matches data in the aggregate record group-by field.

4. The method of claim 3, further comprising the steps of:

outputting the aggregated data in the histogram format stored in the aggregation result field of the aggregate record once data in the input data record group-by field does not match data in the aggregate record group-by field; and

re-initializing the aggregate record, wherein the data in the aggregate record group-by field is set equal to the data in the input data record group-by field and data in each location of the aggregation result field is set to null.

5. A computer program product comprising a computer useable medium having computer program logic recorded thereon for enabling a processor in a computer system to transform a stream of sorted input data records into an aggregate record, each input data record including at least one group-by field, at least one field to be binned, and at least one value field, and each aggregate record including at least one group-by field and an aggregation result field, wherein the input data record group-by field stores data to be matched against data stored in the aggregate record group-by field, wherein the input data records are sorted by the data in the group-by field, wherein the value field stores data to be aggregated, and wherein the aggregation result field includes at least one location and stores aggregated data in a histogram format, the computer program logic comprising:

means for enabling the processor, for each input data record in the stream, to evaluate data in the input data record field to be binned to determine a bin-index value, wherein the bin-index value identifies locations of the aggregation result field the value field data should be aggregated into; and

means for enabling the processor, for each input data record in the stream, to aggregate the value field data into the aggregation result field location identified by the bin-index value, when data in the input data record group-by field matches data in the aggregate record group-by field.

6. The computer program product of claim 5, wherein the computer program logic further comprises:

means for enabling the processor to output the aggregated data in the histogram format stored in the aggregation result field of the aggregate record once data in the input data record group-by field does not match data in the aggregate record group-by field; and

means for enabling a processor to re-initialize the aggregate record, wherein the data in the aggregate record group-by field is set equal to the data in the input data record group-by field and data in each location of the aggregation result field is set to null.

7. A system for transforming a stream of input data records into a partially aggregated record, each input data record including at least one group-by field, at least one field to be binned, and at least one value field, and each partially aggregated record including at least one group-by field and an aggregation result field, wherein the input data record group-by field stores data to be matched against data stored in the partially aggregated record group-by field, wherein the value field stores data to be aggregated, and wherein the aggregation result field includes at least one location and stores aggregated data in a histogram format, the system comprising:

a binning module that, for each input data record in the stream, evaluates data in the input data record field to be binned to determine a bin-index value, wherein the bin-index value identifies locations of the aggregation result field the value field data should be aggregated into; and

a histogram aggregation module that, for each input data record in the stream, aggregates the value field data into the aggregation result field location identified by the bin-index value, when data in the input data record group-by field matches data in the partially aggregated record group-by field.

8. A method for transforming a stream of input data records into a partially aggregated record, each input data record including at least one group-by field, at least one field to be binned, and at least one value field, and each partially aggregated record including at least one group-by field and an aggregation result field, wherein the input data record group-by field stores data to be matched against data stored in the partially aggregated record group-by field, wherein the value field stores data to be aggregated, and wherein the aggregation result field includes at least one location and stores aggregated data in a histogram format, the method comprising the steps of:

evaluating, for each input data record in the stream, data in the input data record field to be binned to determine a bin-index value, wherein the bin-index value identifies locations of the aggregation result field the value field data should be aggregated into; and

for each input data record in the stream, aggregating the value field data into the aggregation result field location identified by the bin-index value, when data in the input data record group-by field matches data in the partially aggregated record group-by field.

9. The method of claim 8, further comprising the steps of:

creating a partially aggregated record when the data in the input data record group-by field does not match with any of the data in the existing partially aggregated records group-by fields, wherein the data in the created partially aggregated record group-by field is set equal to the data in the input data record group-by field and data in each location of the aggregation result field of the created partially aggregated record is set to null; and

outputting the aggregated data in the histogram format stored in the aggregation result field of each partially aggregated record once all of the input data records have been processed.

10. A system for transforming a stream of sorted input data records into an aggregate record, each input data record including at least one group-by field, at least one field to be binned, and at least one value field, and each aggregate record including at least one group-by field and an aggregation result field, wherein the input data record group-by field stores data to be matched against data stored in the aggregate record group-by field, wherein the value field stores data to be aggregated, and wherein the aggregation result field includes at least one location and stores aggregated data in a histogram format, the system comprising:

evaluating means for evaluating each input data record in the stream, the evaluating means evaluates data in the input data record field to be binned to determine a bin-index value, wherein the bin-index value identifies locations of the aggregation result field the value field data should be aggregated into;

histogram aggregation means that, for each input data record in the stream, aggregates the value field data into the aggregation result field location identified by the bin-index value, when data in the input data record group-by field matches data in the aggregate record group-by field; and

a graphical user-interface means for providing parameters for the histogram aggregation means, the parameters identifying a selected histogram aggregation operation and selected group-by fields.

11. A system for transforming a stream of input data records into a partially aggregated record, each input data record including at least one group-by field, at least one field to be binned, and at least one value field, and each partially aggregated record including at least one group-by field and an aggregation result field, wherein the input data record group-by field stores data to be matched against data stored in the partially aggregated record group-by field, wherein the value field stores data to be aggregated, and wherein the aggregation result field includes at least one location and stores aggregated data in a histogram format, the system comprising:

an evaluating means that, for each input data record in the stream, evaluates data in the input data record field to be binned to determine a bin-index value, wherein the bin-index value identifies locations of the aggregation result field the value field data should be aggregated into; and

a histogram aggregation means that, for each input data record in the stream, aggregates the value field data into the aggregation result field location identified by the bin-index value, when data in the input data record group-by field matches data in the partially aggregated record group-by field.

12. The system of claim 11, further comprising a graphical user-interface means that provides parameters for the histogram aggregation means, the parameters identifying a selected histogram aggregation operation and selected group-by fields.

13. The system of claim 12, wherein the graphical user-interface means displays an aggregate panel, the aggregate panel including three windows for displaying columns to aggregate, group-by columns, and columns to remove, a first group of boxes for choosing at least one index for columns to aggregate and distribution columns, and a second group of boxes for selecting the histogram aggregation operation from a group of histogram aggregation operations.

14. The system of claim 13, wherein the group of histogram aggregation operations include at least one of determining a sum, maximum, minimum, count, and average.

15. A computer program product comprising a computer useable medium having computer program logic recorded thereon for enabling a processor in a computer system to transform a stream of input data records into a partially aggregated record, each input data record including at least one group-by field, at least one field to be binned, and at least one value field, and each partially aggregated record including at least one group-by field and an aggregation result field, wherein the input data record group-by field stores data to be matched against data stored in the partially aggregated record group-by field, wherein the value field stores data to be aggregated, and wherein the aggregation result field includes at least one location and stores aggregated data in a histogram format, the computer program logic comprising:

means for enabling the processor, for each input data record in the stream, to evaluate data in the input data record field to be binned to determine a bin-index value, wherein the bin-index value identifies locations of the aggregation result field the value field data should be aggregated into; and

means for enabling the processor, for each input data record in the stream, to aggregate the value field data into the aggregation result field location identified by the bin-index value, when data in the input data record group-by field matches data in the partially aggregated record group-by field.

16. The computer program product of claim 15, wherein the computer program logic further comprises:

means for creating a partially aggregated record when the data in the input data record group-by field does not match with any of the data in the existing partially aggregated records group-by fields, wherein the data in the created partially aggregated record group-by field is set equal to the data in the input data record group-by field and data in each location of the aggregation result field of the created partially aggregated record is set to null; and

means for outputting the aggregated data in the histogram format stored in the aggregation result field of each partially aggregated record once all of the input data records have been processed.

17. A system for transforming a stream of sorted input data records into an aggregate record, each input data record including at least one field to be binned and at least one value field, and each aggregate record including an aggregation result field, wherein the value field stores data to be aggregated, and wherein the aggregation result field includes at least one location and stores aggregated data in a histogram format, the system comprising:

a binning module that, for each input data record in the stream, evaluates data in the input data record field to be binned to determine a bin-index value, wherein the bin-index value identifies locations of the aggregation result field the value field data should be aggregated into; and

a histogram aggregation module that, for each input data record in the stream, aggregates the value field data into the aggregation result field location identified by the bin-index value.

18. A system for transforming a stream of input data records into a partially aggregated record, each input data record including at least one field to be binned and at least one value field, and each partially aggregated record including an aggregation result field, wherein the value field stores data to be aggregated, and wherein the aggregation result field includes at least one location and stores aggregated data in a histogram format, the system comprising:

a binning module that, for each input data record in the stream, evaluates data in the input data record field to be binned to determine a bin-index value, wherein the bin-index value identifies locations of the aggregation result field the value field data should be aggregated into; and

a histogram aggregation module that, for each input data record in the stream, aggregates the value field data into the aggregation result field location identified by the bin-index value.