Computing correlated aggregates over a data stream
View Patent ↗Described herein are approaches for computing correlated aggregates. An aspect provides for receiving a stream of data elements at a device, each data element having at least one numerical attribute; maintaining in memory plurality of tree structures comprising a plurality of separate nodes for summarizing numerical attributes of the data elements with respect to a predicate value of a correlated aggregation query, said maintaining comprising: creating the plurality of tree structures in which each node implements one of: a probabilistic counter and a sketch, wherein said probabilistic counter and said sketch each act to estimate aggregated data element numerical attributes to form a summary of said numerical attributes; and responsive to a correlated aggregation query specifying said predicate value, using said plurality of tree structures as a summary of said data element numerical attributes to compute a response to said correlated aggregate query.
1. A computer program product for summarizing attributes of data elements of a data set for computing correlated aggregates, comprising:
a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising:
computer readable program code configured to receive a stream of data elements at a device, each data element having at least one numerical attribute;
computer readable program code configured to maintain in memory a plurality of tree structures comprising a plurality of separate nodes for summarizing numerical attributes of the data elements with respect to a predicate value of a correlated aggregation query, wherein to maintain further comprises:
computer readable program code configured to create the plurality of tree structures in which each node implements one of: a probabilistic counter and a sketch, wherein said probabilistic counter and said sketch each act to estimate aggregated data element numerical attributes to form a summary of said numerical attributes, said probabilistic counter providing an estimated count via incrementing by a predetermined weight in response to an increment operation; and
computer readable program code configured to, responsive to a correlated aggregation query specifying said predicate value, use said plurality of tree structures as a summary of said data element numerical attributes to compute a response to said correlated aggregate query.
2. The computer program product of claim 1 , wherein estimation of aggregated data element numerical attributes to form said summary of said data element numerical attributes is within a predetermined relative error.
3. The computer program product of claim 2 , wherein a memory size requirement for maintaining the summary of said data element numerical attributes is a function of the predetermined relative error.
4. The computer program product of claim 1 , wherein each node implements a probabilistic counter, and further wherein said correlated aggregation query is a count query with respect to said predicate value.
5. The computer program product of claim 4 , wherein nodes of said plurality of tree structures are organized into levels of probabilistic counters.
6. The computer program product of claim 5 , wherein each level of nodes provides a more refined interval for counting said numerical attributes of said data elements.
7. The computer program product of claim 6 , wherein each node is capped to a predetermined size, and further wherein, responsive to the predetermined size being reached, two child nodes are formed for a parent node.
8. The computer program product of claim 1 , wherein each node implements a sketch function suitable for a statistical inquiry specified in said correlated aggregation query.
9. The computer program product of claim 8 , wherein said statistical inquiry is computation of a frequency moment F k of said data stream.
10. The computer program product of claim 1 , wherein said stream of data elements comprises a stream of IP packets, wherein said data elements comprise IP packets, and further wherein said numerical attributes comprise sizes of said IP packets.
11. A system for summarizing attributes of data elements of a data set for computing correlated aggregates, comprising:
at least one processor; and
a memory device operatively connected to the at least one processor;
wherein, responsive to execution of program instructions accessible to the at least one processor, the at least one processor is configured to:
receive a stream of data elements at a device, each data element having at least one numerical attribute;
maintain in memory a plurality of tree structures comprising a plurality of separate nodes for summarizing numerical attributes of the data elements with respect to a predicate value of a correlated aggregation query, wherein to maintain further comprises:
create the plurality of tree structures in which each node implements one of: a probabilistic counter and a sketch, wherein said probabilistic counter and said sketch each act to estimate aggregated data element numerical attributes to form a summary of said numerical attributes, said probabilistic counter providing an estimated count via incrementing by a predetermined weight in response to an increment operation; and
responsive to a correlated aggregation query specifying said predicate value, use said plurality of tree structures as a summary of said data element numerical attributes to compute a response to said correlated aggregate query.
12. The system of claim 11 , wherein said stream of data elements comprises a stream of IP packets, wherein said data elements comprise IP packets, and further wherein said numerical attributes comprise sizes of said IP packets.