Method and apparatus for using histograms to product data summaries

• US 7,417,954 B1
• Filed: 12/28/2006
• Issued: 08/26/2008
• Est. Priority Date: 04/03/2001
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Muthukrishnan, Shanmugavelayutham, Indyk, Piotr, Strauss, Martin J., Kotidis, Ioannis, Gilbert, Anna C., Cuha, Sudipto
• Primary Examiner(s): Pham; Chi H.
• Assistant Examiner(s): TRAN, PHUC H
• Application Number:
  US11/647,085
• Time in Patent Office: 607 Days
• Field of Search: 370230-235, 370/241, 707/1, 707/4, 707/102
• US Class Current: 370/241
• CPC Class Codes: H04L 43/045 for graphical visualisation of monitoring data
• CPC Class Codes: H04L 43/06 Generation of reports
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

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 the steps of:

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; and

wherein the step of constructing a robust histogram comprises;

identifying resolution levels of dyadic intervals of a representation of the array sketch of the vector sum,

identifying a single dyadic interval that decreases the differences between the representation and the robust histogram, and

iterating the identifying a single dyadic interval step with subsequent dyadic intervals until the representation is substantially equivalent to the robust histogram.

2. The method of claim 1, wherein the robust histogram, Hr, is defined as a (Br, ε

r) robust approximation of the data signal A if, given any collection of X, of |X|≦

Br non-overlapping intervals, any histogram H′

which can be expressed as

$H^{\mathrm{\prime <br><br>}}=\{\begin{array}{c}{H}_r,\left[0,N\right)-{\bigcup <br><br>}_{I\in <br><br>X}<br><br>I\\ c_I<br><br>{\mathrm{\chi <br><br>}}_I,I\in <br><br>X\end{array}$

satisfies (1−

ε

_r)∥

A−

H_r∥

≦

∥

A−

H′

∥

, where B_r is a number of buckets in the robust histogram, ε

_r is a user-defined error parameter, c is a user-defined parameter, and H′

is a current state of the robust approximation.

3. The method of claim 2, wherein the number of buckets Br is reduced to produce the output histogram H from the robust histogram Hr and the array sketch.

4. 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 step occurs at a data warehouse.

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

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

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

8. 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 the steps of:

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;

wherein in constructing the output histogram, workspace, memory space, and computation time are polynomial in data signal length N.

9. 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 the steps of:

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;

wherein the hybrid histogram, H*, equals the output histogram, H, on an interval I and the robust histogram, Hr, elsewhere.

10. 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; and

wherein the means for of constructing a robust histogram comprises;

means for identifying resolution levels of dyadic intervals of a representation of the array sketch of the vector sum,

means for identifying a single dyadic interval that decreases the differences between the representation and the robust histogram, and

means for iterating the identifying a single dyadic interval step with subsequent dyadic intervals until the representation is substantially equivalent to the robust histogram.

11. The apparatus of claim 10, wherein the robust histogram, Hr, is defined as a (Br, ε

r) robust approximation of the data signal A if, given any collection of X, of |X|≦

Br non-overlapping intervals, any histogram H′

which can be expressed as

$H^{\mathrm{\prime <br><br>}}=\{\begin{array}{c}{H}_r,\left[0,N\right)-{\bigcup <br><br>}_{I\in <br><br>X}<br><br>I\\ c_I<br><br>{\mathrm{\chi <br><br>}}_I,I\in <br><br>X\end{array}$

satisfies (1−

ε

_r)∥

A−

H_r∥

≦

∥

A−

H′

∥

, where B_r is a number of buckets in the robust histogram, ε

_r is a user-defined error parameter, c is a user-defined parameter, and H′

is a current state of the robust approximation.

12. The apparatus of claim 11, wherein the number of buckets Br is reduced to produce the output histogram H from the robust histogram Hr and the array sketch.

13. The method of claim 10, 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.

14. The method of claim 10, where means for performing all the steps are in at least one network router.

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

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

17. 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; and

wherein in constructing the output histogram, workspace, memory space, and computation time are polynomial in data signal length N.

18. 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; and

wherein the hybrid histogram, H*, equals the output histogram, H, on an interval I and the robust histogram, Hr, elsewhere.