Data coreset compression
AssigneeMassachusetts Institute of Technology
InventorsDaniela Rus, Dan Feldman
Life of this patent
Estimating the term…
Abstract
An approach to compression of a large (n point or samples) data set has a combination of one or more desirable technical properties: for a desired level of accuracy (ε), the number of compressed points (a “coreset”) representing the original data is O(log n); the level of accuracy comprises a guaranteed bound expressed as multiple of error of an associated line simplification of the data set; for a desired level of accuracy and a complexity (e.g., number k of optimal line segments) of the associated line simplification, the computation time is O(n); and for a desired level of accuracy (c) and a complexity of the associated line simplification, the storage required for the computation is O(log n).
Claims21
A computer-implemented method comprising:
- accepting first data representing a first plurality of data samples acquired from a set of one or more sensor, the first plurality of data samples having a first number of points in a data space;
- applying a computer-implemented compression procedure to the first data to form second data representing a second plurality of points having a second number of points substantially smaller than the first number of points, and to provide a bound on an error associated with representing the first plurality of data samples by the second plurality of data samples, wherein applying the compression procedure includes
- determining a first plurality of line segments in the data space according to a procedure with a property that the number of line segments in the first plurality of line segments grows at most as a logarithm of the first number of points,
- partitioning the first plurality of data samples into a plurality of parts each part being associated with a corresponding different line segment of the first plurality of line segments in the data space,
- for each part of the plurality of parts, selecting a subset of data samples of the part, and
- combining the selected subsets of data samples to form the second plurality of points;
- providing the second data representing the second plurality of points as a compressed representation of the acquired first plurality of data samples.
Dependencies are inferred from the claim text.