System and Method for Identifying Hierarchical Heavy Hitters in Multi-Dimensional Data

Abstract

A method including receiving a plurality of elements of a data stream, storing a multi-dimensional data structure in a memory, said multi-dimensional data structure storing the plurality of elements as a hierarchy of nodes, each node having a frequency count corresponding to the number of elements stored therein, comparing the frequency count of each node to a threshold value based on a total number of the elements stored in the nodes and identifying each node for which the frequency count is at least as great as the threshold value as a hierarchical heavy hitter (HHH) node and propagating the frequency count of each non-HHH nodes to its corresponding parent nodes.

1 - 23 . (canceled) 
   
   
       24 . A method, comprising:
 receiving a plurality of elements of a data stream;   storing a multi-dimensional data structure in a memory, said multi-dimensional data structure storing the plurality of elements as a hierarchy of nodes, each node having a frequency count corresponding to the number of elements stored therein;   determining, as a function of the frequency count, which nodes correspond to a hierarchical heavy hitter (HHH) node;   propagating the frequency count of each non-HHH nodes to its corresponding parent nodes   identifying each node without a descendant as a fringe node; and   deleting each fringe node for which the frequency count is less than a product of an error factor and the total number of the elements stored in the plurality of nodes.   
   
   
       25 . The method of  claim 24 , wherein the frequency count of each HHH node is not propagated to its corresponding parent nodes. 
   
   
       26 . The method of  claim 24 , wherein the multi-dimensional data structure is one of a two-dimensional data structure, a three-dimensional data structure, a four-dimensional data structure and a five-dimensional data structure. 
   
   
       27 . The method of  claim 24 , wherein the frequency count of each node differs from an actual frequency count by less than a specified error factor. 
   
   
       28 . A method, comprising:
 receiving a plurality of elements of a data stream;   storing a multi-dimensional data structure in a memory, said multi-dimensional data structure storing the plurality of elements as a hierarchy of nodes, each node having a frequency count corresponding to the number of elements stored therein;   determining, as a function of the frequency count, which nodes correspond to a hierarchical heavy hitter (HHH) node;   propagating the frequency count of each non-HHH nodes to its corresponding parent nodes;   determining whether one of the nodes corresponds to one of the received elements;   when a node is determined to correspond to the one of the received elements, inserting the one of the received elements into the corresponding node; and   incrementing the frequency count of the corresponding node by an amount equal to the frequency count of the one of the received elements.   
   
   
       29 . The method of  claim 28 , further comprising:
 creating a new node corresponding to each received element for which there is no corresponding node.   
   
   
       30 . The method of  claim 24 , further comprising:
 storing, for each element, auxiliary information including data for propagating the frequency counts.   
   
   
       31 . The method of  claim 24 , wherein a total frequency count of each of the non-HHH nodes is propagated to its corresponding parent node. 
   
   
       32 . The method of  claim 24 , wherein a total frequency count of each of the non-HHH nodes is propagated by splitting the total frequency count and propagating a split portion of the total frequency count to its corresponding parent nodes. 
   
   
       33 . The method of  claim 24 , further comprising:
 propagating the frequency counts of each of the non-HHH parent nodes to a corresponding common grandparent node.   
   
   
       34 . The method of  claim 33 , wherein the common grandparent node includes a compensating count to prevent overcounting of the frequency counts from the parent frequency counts. 
   
   
       35 . A system, comprising:
 a receiving element receiving a plurality of elements of a data stream;   a storage element storing a multi-dimensional data structure in a memory, said multi-dimensional data structure storing the plurality of elements as a hierarchy of nodes, each node having a frequency count corresponding to a number of elements stored therein;   a determination element determining, as a function of the frequency count, which nodes correspond to a hierarchical heavy hitter (HHH) node; and   a propagation element propagating the frequency count of each non-HHH node to its corresponding parent nodes and propagating the frequency counts of parent nodes to a common grandparent node, wherein the common grandparent node includes a compensating count to prevent overcounting of the frequency counts from the parent nodes.   
   
   
       36 . The system of  claim 35 , wherein the compensating counts include a positive compensating count and a negative compensating count. 
   
   
       37 . The system of  claim 35 , wherein the frequency count of each node differs from an actual frequency count by less than a specified error factor. 
   
   
       38 . The system of  claim 35 , wherein the HHH nodes are identified from one of streaming data and static data. 
   
   
       39 . A computer readable storage medium including a set of instructions executable by a processor, the set of instructions configured to:
 receive a plurality of elements of a data stream;   store a multi-dimensional data structure in a memory, said multi-dimensional data structure storing the plurality of elements as a hierarchy of nodes, each node having a frequency count corresponding to a number of elements stored therein;   determining, as a function of the frequency count, which nodes correspond to a hierarchical heavy hitter (HHH) node; and   propagate the frequency count of each non-HHH node to its corresponding parent nodes, wherein the frequency count of each non-HHH node is propagated by splitting the total frequency count and propagating a split portion of the total frequency count to its parent nodes.