Method and apparatus for efficient aggregate computation over data streams

• US 9,116,956 B2
• Filed: 03/18/2014
• Issued: 08/25/2015
• Est. Priority Date: 06/29/2007
• Status: Active Grant

• Current Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Rastogi, Rajeev, Satkin, Scott, Nagarai, Kanthi Chikguntakal, Marayya, Naidu Kundrapu Venkata
• Primary Examiner(s): ALAM, SHAHID AL
• Application Number:
  US14/217,907
• Publication Number:
  US 20140201222A1
• Time in Patent Office: 525 Days
• Field of Search: 707/754, 707/713, 707/722
• US Class Current: 1/1
• CPC Class Codes: G06F 16/244 Grouping and aggregation
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/2474 Sequence data queries, e.g. querying versioned data
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A method includes determining, using a processor, a set of aggregate queries to be executed on a data stream, the set of aggregate queries comprising queries that perform respective sets of aggregation operations on respective sets of attribute values over respective time intervals. The method also includes generating, using the processor, at least one intermediate aggregate query for a subset of the set of aggregate queries, the at least one intermediate aggregate query combining a subset of aggregation operations for the subset of aggregate queries and a subset of attribute values. The method further includes executing, using the processor, the at least one intermediate aggregate query to generate pre-aggregated data from the data stream for the subset of aggregate queries and executing, using the processor, the subset of aggregate queries subsequent to executing the at least one intermediate aggregate query on the pre-aggregated data.

Claims

1. A method comprising:

determining, using a processor, a set of aggregate queries to be executed on a data stream, the set of aggregate queries comprising queries that perform respective sets of aggregation operations on respective sets of attribute values over respective time intervals;

generating, using the processor, at least one intermediate aggregate query for a subset of the set of aggregate queries, said at least one intermediate aggregate query combining a subset of aggregation operations for the subset of aggregate queries and a subset of attribute values;

executing, using the processor, said at least one intermediate aggregate query to generate pre-aggregated data from the data stream for the subset of aggregate queries; and

executing, using the processor, the subset of aggregate queries on the pre-aggregated data subsequent to executing said at least one intermediate aggregate query;

wherein each of at least two aggregate queries in the subset of aggregate queries comprises;

a number of group-by attributes on which aggregation is performed; and

a time interval over which aggregation is performed.

2. The method of claim 1, wherein generating said at least one intermediate aggregate query further comprises determining that said at least one intermediate aggregate query reduces a computational cost of executing the set of aggregate queries to be executed on the data stream.

3. The method of claim 1, wherein said at least one intermediate aggregate query comprises a number of group-by attributes, the number of group-by attributes in said at least one intermediate aggregate query being less than a sum of the numbers of group-by attributes in the subset of aggregate queries.

4. The method of claim 3, wherein generating said at least one intermediate aggregate query further comprises determining that

5. The method of claim 1, further comprising subjecting at least one of the aggregate queries in the subset of aggregate queries to a respective set of attribute filters specifying respective attribute range conditions for respective sets of attribute values associated with the at least one of the aggregate queries.

6. The method of claim 5, wherein said at least one intermediate aggregate query is generated by combining respective attribute filters of two or more of the subset of aggregate queries to form a single attribute filter usable to pre-filter pre-aggregated data input to the two or more aggregate queries.

7. The method of claim 1, wherein the data stream comprises network traffic records.

8. The method of claim 1, wherein the data stream comprises Internet Protocol flow records.

9. The method of claim 1, wherein the data stream comprises at least one of:

sensor node readings;

call detail records in a telecommunications network;

retail transaction records; and

one or more financial tickers.

10. An article of manufacture comprising a processor-readable non-transitory storage medium storing one or more instructions which, when executed by a processor, configure the processor to:

determine a set of aggregate queries to be executed on a data stream, the set of aggregate queries comprising queries that perform respective sets of aggregation operations on respective sets of attribute values over respective time intervals;

generate at least one intermediate aggregate query for a subset of the set of aggregate queries, said at least one intermediate aggregate query combining a subset of aggregation operations for the subset of aggregate queries and a subset of attribute values;

execute said at least one intermediate aggregate query to generate pre-aggregated data from the data stream for the subset of queries; and

execute the subset of aggregate queries on the pre-aggregated data subsequent to executing said at least one intermediate aggregate query;

wherein each of at least two aggregate queries in the subset of aggregate queries comprises;

a number of group-by attributes on which aggregation is performed; and

a time interval over which aggregation is performed.

11. The article of manufacture of claim 10, wherein generating said at least one intermediate aggregate query further comprises determining that said at least one intermediate aggregate query reduces a computational cost of executing the set of aggregate queries to be executed on the data stream.

12. The article of manufacture of claim 10, wherein said at least one intermediate aggregate query comprises a number of group-by attributes, the number of group-by attributes in said at least one intermediate aggregate query being less than a sum of the numbers of group-by attributes in the subset of aggregate queries.

13. The article of manufacture of claim 10, wherein the one or more instructions, when executed by a processor, further configure the processor to subject at least one of the aggregate queries in the subset of aggregate queries to a respective set of attribute filters specifying respective attribute range conditions for respective sets of attribute values associated with the at least one of the aggregate queries.

14. The article of manufacture of claim 13, wherein said at least one intermediate aggregate query is generated by combining respective attribute filters of two or more of the subset of aggregate queries to form a single attribute filter usable to pre-filter pre-aggregated data input to the two or more aggregate queries.

15. Apparatus, comprising:

a memory; and

a processor coupled to the memory and configured to;

determine a set of aggregate queries to be executed on a data stream, the set of aggregate queries comprising queries that perform respective sets of aggregation operations on respective sets of attribute values over respective time intervals;

generate at least one intermediate aggregate query for a subset of the set of aggregate queries, said at least one intermediate aggregate query combining a subset of aggregation operations for the subset of aggregate queries and a subset of attribute values;

execute said at least one intermediate aggregate query to generate pre-aggregated data from the data stream for the subset of queries; and

execute the subset of aggregate queries on the pre-aggregated data subsequent to executing said at least one intermediate aggregate query;

wherein each of at least two aggregate queries in the subset of aggregate queries comprises;

a number of group-by attributes on which aggregation is performed; and

a time interval over which aggregation is performed.

16. The apparatus of claim 15, wherein the processor is configured to generate said at least one intermediate aggregate query by determining that said at least one intermediate aggregate query reduces a computational cost of executing the set of aggregate queries to be executed on the data stream.

17. The apparatus of claim 15, wherein said at least one intermediate aggregate query comprises a number of group-by attributes, the number of group-by attributes in said at least one intermediate aggregate query being less than a sum of the numbers of group-by attributes in the subset of aggregate queries.

18. The apparatus of claim 15, wherein the processor is further configured to subject at least one of the aggregate queries in the subset of aggregate queries to a respective set of attribute filters specifying respective attribute range conditions for respective sets of attribute values associated with the at least one of the aggregate queries.

19. The apparatus of claim 18, wherein said at least one intermediate aggregate query is generated by combining respective attribute filters of two or more of the subset of aggregate queries to form a single attribute filter usable to pre-filter pre-aggregated data input to the two or more aggregate queries.

20. The apparatus of claim 15, wherein the data stream comprises at least one of:

network traffic records;

sensor node readings;

call detail records in a telecommunications network;

retail transaction records; and

one or more financial tickers.