Hierarchical update scheme for extremum location
First Claim
Patent Images
1. A method for generating data comprising:
- partitioning, by a processing device, data values of a base level into first partitions wherein the data values are stored in memory;
generating, by the processing device, a first level including second partitions, each of the second partitions including a respective extreme data value from each of the first partitions;
generating, by the processing device, an apex including at least one extreme data value from the second partitions of the first level that also corresponds to an extremum of the base level; and
updating, by the processing device, the first level if at least one partition of the first partitions receives a new extreme data value,wherein the new extreme data value is stored in the apex if the new extreme data value comprises a new extremum of the base level.
2 Assignments
0 Petitions
Accused Products
Abstract
A system and method for determining an extreme value of data in various applications including audio, video and image encoding schemes. The system and method are used to build a hierarchical data structure by partitioning the data values and then constructing a hierarchy using these data values, with the apex containing the extreme value. The system and method allow for changes in the data values in the base level of the hierarchy to ripple through to the apex in an efficient manner.
-
Citations
59 Claims
-
1. A method for generating data comprising:
-
partitioning, by a processing device, data values of a base level into first partitions wherein the data values are stored in memory; generating, by the processing device, a first level including second partitions, each of the second partitions including a respective extreme data value from each of the first partitions; generating, by the processing device, an apex including at least one extreme data value from the second partitions of the first level that also corresponds to an extremum of the base level; and updating, by the processing device, the first level if at least one partition of the first partitions receives a new extreme data value, wherein the new extreme data value is stored in the apex if the new extreme data value comprises a new extremum of the base level. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A method for generating data, comprising:
-
partitioning, by a computing device, a base level data set into one or more partitions in memory; generating, by the computing device, a coarse representation of extrema of each of the one or more partitions of the base level data by finding and storing the extrema of the partitions in memory; and updating, by the computing device, the coarse representation if one or more data values of the base level data are altered, wherein the updating the coarse representation comprises finding and storing new extrema in memory from one of the one or more partitions of the base level data that includes altered data values. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27)
-
-
28. A method of encoding, comprising:
-
partitioning, by a computer-based device, a set of data values into a plurality of first partitions wherein the set of data values are stored in memory; storing, by the computer-based device, a set of first extrema corresponding to extreme data values of the first partitions; altering, by the computer-based device, one or more data values to produce one or more altered first partitions; and updating, by the computer-based device, extreme data values of the set of first extrema corresponding to the one or more altered first partitions. - View Dependent Claims (29, 30, 31, 32, 33, 34, 35, 36, 37, 38)
-
-
39. An apparatus, comprising:
an encoder, including a digital device, configured to use a hierarchical data structure to identify an extremum of a data set, wherein the hierarchical data structure comprises; a base level including data values of the data set partitioned into first partitions; a first level including second partitions, corresponding ones of the second partitions including respective extreme data values of the first partitions; an apex including an extreme data value of the first level corresponding to an extremum of the base level; and wherein the encoder is further configured to update the hierarchical data structure in response to a new extremum being saved in the base level. - View Dependent Claims (40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52)
-
53. A tangible computer-readable medium having stored thereon, computer-executable instructions that, if executed by a machine, cause the machine to perform a method comprising:
-
partitioning data values of a base level into first partitions; generating a first level including second partitions, each of the second partitions including a respective extreme data value of corresponding ones of the first partitions; generating an apex including an extreme data value of the first level corresponding to an extremum of the base level; and modifying the first level in response to at least one of the first partitions receiving a new extreme data value, wherein the new extreme data value is stored in the apex if the new extreme data value comprises a new extremum of the base level. - View Dependent Claims (54, 55, 56, 57, 58, 59)
-
Specification