Methods and apparatus for space efficient adaptive detection of multidimensional hierarchical heavy hitters

Abstract

The present invention develops an efficient streaming method for detecting multidimensional hierarchical heavy hitters from massive data streams and enables near real time detection of anomaly behavior in networks.

1 . A method for detecting at least one hierarchical heavy hitter from a stream of packets, comprising:
 receiving at least one packet from said stream of packets;   associating at least two keys with at least two fields of said at least one packet;   applying an adaptive trie data structure, where each node of said adaptive trie data structure is associated with said at least two keys; and   using said adaptive trie data structure to determine said at least one hierarchical heavy hitter.   
   
   
       2 . The method of  claim 1 , wherein said stream of packets are received from a packet network. 
   
   
       3 . The method of  claim 2 , wherein said packet network is a Voice over Internet Protocol (VoIP) network. 
   
   
       4 . The method of  claim 1 , wherein said applying said adaptive trie data structure comprises:
 updating said adaptive trie data structure for each received packet.   
   
   
       5 . The method of  claim 4 , wherein said updating comprises:
 updating a volume of at least one node in said adaptive trie data structure.   
   
   
       6 . The method of  claim 4 , wherein said updating comprises:
 determining whether an additional node is to be added into said adaptive trie data structure in accordance with a threshold.   
   
   
       7 . The method of  claim 1 , further comprising:
 applying said at least one detected hierarchical heavy hitter to perform change detection.   
   
   
       8 . A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to perform the steps of a method for detecting at least one hierarchical heavy hitter from a stream of packets, comprising:
 receiving at least one packet from said stream of packets;   associating at least two keys with at least two fields of said at least one packet;   applying an adaptive trie data structure, where each node of said adaptive trie data structure is associated with said at least two keys; and   using said adaptive trie data structure to determine said at least one hierarchical heavy hitter.   
   
   
       9 . The computer-readable medium of  claim 8 , wherein said stream of packets are received from a packet-switch network. 
   
   
       10 . The computer-readable medium of  claim 9 , wherein said packet-switch network is a Voice over Internet Protocol (VoIP) network. 
   
   
       11 . The computer-readable medium of  claim 8 , wherein said applying said adaptive trie data structure comprises:
 updating said adaptive trie data structure for each received packet.   
   
   
       12 . The computer-readable medium of  claim 11 , wherein said updating comprises:
 updating a volume of at least one node in said adaptive trie data structure.   
   
   
       13 . The computer-readable medium of  claim 11 , wherein said updating comprises:
 determining whether an additional node is to be added into said adaptive trie data structure in accordance with a threshold.   
   
   
       14 . The computer-readable medium of  claim 8 , further comprising:
 applying said at least one detected hierarchical heavy hitter to perform change detection.   
   
   
       15 . An apparatus for detecting at least one hierarchical heavy hitter from a stream of packets, comprising:
 means for receiving at least one packet from said stream of packets;   means for associating at least two keys with at least two fields of said at least one packet;   means for applying an adaptive trie data structure, where each node of said adaptive trie data structure is associated with said at least two keys; and   means for using said adaptive trie data structure to determine said at least one hierarchical heavy hitter.   
   
   
       16 . The apparatus of  claim 15 , wherein said stream of packets are received from a packet network. 
   
   
       17 . The apparatus of  claim 15 , wherein said means for applying said adaptive trie data structure comprises:
 means for updating said adaptive trie data structure for each received packet.   
   
   
       18 . The apparatus of  claim 17 , wherein said means for updating comprises:
 means for updating a volume of at least one node in said adaptive trie data structure.   
   
   
       19 . The apparatus of  claim 17 , wherein said means for updating comprises:
 means for determining whether an additional node is to be added into said adaptive trie data structure in accordance with a threshold.   
   
   
       20 . The apparatus of  claim 15 , further comprising:
 means for applying said at least one detected hierarchical heavy hitter to perform change detection.