Method and apparatus for using histograms to produce data summaries

• US 7,965,643 B1
• Filed: 07/10/2008
• Issued: 06/21/2011
• Est. Priority Date: 07/10/2008
• Status: Expired due to Fees

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Strauss, Martin J., Kotidis, Ioannis, Gilbert, Anna C., Muthukrishnan, Shanmugavelayutham, Indyk, Piotr, Guha, Sudipto
• Primary Examiner(s): Tran; Phuc
• Application Number:
  US12/217,958
• Time in Patent Office: 1,076 Days
• Field of Search: 370241-253, 707/102
• US Class Current: 370/241
• CPC Class Codes: H04L 43/045 for graphical visualisation of monitoring data
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00

Abstract

A system and method are provided for summarizing dynamic data from distributed sources through the use of histograms. In particular, the method comprises receiving a first data signal at a first location, determining a first array sketch of the first data signal, and constructing a first output histogram from the first array sketch and a first robust histogram via a first hybrid histogram. Array sketches of a number of data signals may be calculated, and added to yield a single vector sum. The histogram is constructed from the vector sum. In that way, the vector sum may be analyzed without revealing the individual data signals that form the basis of the sum.

Claims

1. A method for providing an output histogram corresponding to a plurality of data signals without revealing individual data signals forming the plurality, the method comprising:

receiving a plurality of array sketches, each array sketch being determined from a different one of the plurality of data signals;

adding the plurality of array sketches to yield an array sketch of the vector sum of the array sketches;

constructing a robust histogram from the array sketch of the vector sum,

constructing the output histogram from the array sketch and the robust histogram via a hybrid histogram;

wherein the output histogram is used for observing a traffic pattern in a network without revealing individual data signals.

2. The method of claim 1, where the plurality of array sketches are determined at routers in a network and the constructing of the output histogram occurs at a data warehouse.

3. The method of claim 1, where all the steps are performed in at least one network router.

4. The method of claim 1, wherein the plurality of array sketches are compact synopsis data structures.

5. The method of claim 1, wherein at least one of the plurality of data signals is dynamic.

6. An apparatus for providing an output histogram corresponding to a plurality of data signals without revealing individual data signals forming the plurality, comprising:

means for receiving a plurality of array sketches, each array sketch being determined from a different one of the plurality of data signals;

means for adding the plurality of array sketches to yield an array sketch of the vector sum of the array sketches;

means for constructing a robust histogram from the array sketch of the vector sum,

means for constructing the output histogram from the array sketch and the robust histogram via a hybrid histogram;

wherein the output histogram is used for observing a traffic pattern in a network without revealing individual data signals.

7. The apparatus of claim 6, where the plurality of array sketches are determined at routers in a network and the means for constructing the output histogram is in a data warehouse.

8. The apparatus of claim 6, where means for performing all the steps are in at least one network router.

9. The apparatus of claim 6, wherein the plurality of array sketches are compact synopsis data structures.

10. The apparatus of claim 6, wherein at least one of the plurality of data signals is dynamic.