Space- and time-efficient management and summarization of data using intermediate summary structure and hierarchical multidimensional histogram
First Claim
1. A method of maintaining a multidimensional histogram for a data array having a data array size, the method comprising:
- collecting, at a computer, a number of largest coefficient linear combinations of then-current data, the number being smaller than the data array size, each of the largest coefficient linear combinations being a tensor product of Haar wavelets of data in the data array;
discarding, at the computer, one of the largest coefficient linear combinations based on comparing a square of the one of the largest coefficient linear combinations with a criterion; and
forming, at the computer, a multidimensional histogram for an intermediate data structure, the forming based on the collecting and the discarding.
2 Assignments
0 Petitions
Accused Products
Abstract
A method maintains 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 involves 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.
-
Citations
20 Claims
-
1. A method of maintaining a multidimensional histogram for a data array having a data array size, the method comprising:
-
collecting, at a computer, a number of largest coefficient linear combinations of then-current data, the number being smaller than the data array size, each of the largest coefficient linear combinations being a tensor product of Haar wavelets of data in the data array; discarding, at the computer, one of the largest coefficient linear combinations based on comparing a square of the one of the largest coefficient linear combinations with a criterion; and forming, at the computer, a multidimensional histogram for an intermediate data structure, the forming based on the collecting and the discarding. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. An apparatus for maintaining a multidimensional histogram for a data array having a data array size, the apparatus comprising:
-
a processor; and a memory to store computer program instructions, the computer program instructions when executed on the processor cause the processor to perform operations comprising; collecting a number of largest coefficient linear combinations of then-current data, the number being smaller than the data array size, each of the largest coefficient linear combinations being a tensor product of Haar wavelets of data in the data array; discarding one of the largest coefficient linear combinations based on comparing a square of the one of the largest coefficient linear combinations with a criterion; and forming a multidimensional histogram for an intermediate data structure, the forming based on the collecting and the discarding. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. A non-transitory computer readable medium storing computer program instructions for maintaining a multidimensional histogram for a data array having a data array size, the computer program instructions, when executed on a processor, cause the processor to perform a operations comprising:
-
collecting a number of largest coefficient linear combinations of then-current data, the number being smaller than the data array size, each of the largest coefficient linear combinations being a tensor product of Haar wavelets of data in the data array; discarding one of the largest coefficient linear combinations based on comparing a square of the one of the largest coefficient linear combinations with a criterion; forming a multidimensional histogram for an intermediate data structure, the forming based on the collecting and the discarding. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification