CORESET COMPRESSION OF DATA

摘要

An approach to compression of a data set having n samples has a combination of one or more desirable technical properties : for a desired level of accuracy, the number of compressed points representing the original data is order 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 of the associated line simplification, the computation time is order n; and for a desired level of accuracy and a complexity of the associated line simplification, the storage required for the computation is order log n.