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 method for summarizing attributes of data elements of a data set for computing correlated aggregates, comprising:
receiving a stream of data elements at a device, each data element having at least one numerical attribute;
maintaining 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, 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, 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, using 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 method 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 method 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 method 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 method of claim 4 , wherein nodes of said plurality of tree structures are organized into levels of probabilistic counters.
6. The method of claim 5 , wherein each level of nodes provides a more refined interval for counting said numerical attributes of said data elements.
7. The method 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 method of claim 1 , wherein each node implements a sketch function suitable for a statistical inquiry specified in said correlated aggregation query.
9. The method of claim 8 , wherein said statistical inquiry is computation of a frequency moment F k of said data stream.
10. The method 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.