Patent ID: 8175845
Filing Date: 2012-05-08
Classification: G06F,Y10S

Abstract:
1. A 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, at a computer, a data update that indicates a change to data in the data array; updating, at the computer, an intermediate data structure having a size substantially smaller than the data array size based on the data update to generate an updated intermediate data structure, 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 largest coefficient linear combinations of then-current data, the number being small compared with the data array size, each of the number of largest coefficient linear combinations being a tensor product of Haar wavelets of data in the data array; discarding, at the computer, one of the number of largest coefficient linear combinations based on comparing a square of the largest coefficient of the linear combination with at least one criterion; determining whether a multidimensional histogram should be formed in response to reception of the data update; and forming the multidimensional histogram as a histogram to an intermediate data array re-synthesized from the collected linear combinations, the forming in response to determining that the multidimensional histogram should be formed in response to the reception of the data update.