Patent ID: 8310922

Claim:
A computer-implemented method of monitoring network traffic by estimating an L 1 difference, said method comprising: receiving a first sketch s(x) from a first network device and a second sketch from a second network device, wherein said first sketch describes a first set of pairs of data (x, f t (x)), wherein x indicates a source and a destination of a first plurality of data packets that include input x, transmitted via said first network device, wherein f t (x) indicates a first amount of information in said first plurality of data packets transmitted via said first network device from said source to said destination in a time period t, wherein said second sketch s(y) describes a second set of pairs of data (y, f t′ (y)), wherein y indicates said source and said destination of a second plurality of data packets that include input y transmitted via said second network device, wherein f t′ (y) indicates a second amount of information in said second plurality of data packets transmitted via said second network device from said source to said destination in a time period t′; a processor of a computer system estimating an L 1 difference ∥f t (x)−f t′ (y)∥ 1 , wherein said estimating said L 1 difference includes determining an L 0 value of a data stream resulting from said first network device inserting elements of a first set of distinct items as insertions into said data stream and from said second network device inserting elements of a second set as deletions from said data stream, wherein said first set includes distinct items derived from x i , wherein said second set of distinct items includes distinct items derived from y i , and wherein said determining said L 0 value includes processing updates to ranges of said data stream; and determining a pattern of said network traffic based on said L 1 difference.