Patent ID: 7249136
Filing Date: 2007-07-24
Classification: G06F,Y10S

Abstract:
1. A computer implemented method of maintaining a multidimensional histogram for a data array having a data array size, the method having a processing time substantially less than proportional to the data array size, the method comprising: receiving a data update that indicates a change to data in the data array; with the data update, updating an intermediate data structure having a size substantially smaller than the data array size, so that the updated intermediate data structure remains an at-least-approximate representation of the data in the data array as changed by the data update; collecting a number of substantially-largest-coefficient linear combinations of then-current data, the number being small compared with the data array size; and forming the multidimensional histogram as a histogram to an intermediate data array re-synthesized from the collected linear combinations; wherein the intermediate data structure constitutes a histogram sketch of the data that includes one or both of: