# Data Compression with a Time Limit
## 2 Data Compression with a Time Limit
### A Data Compression Algorithm with a Time Limit  
Generally speaking, the framework proposed in [1] is a specialization of the more general approach with respect to the basic mechanism of compression algorithms related to the configuration of effort levels. It is not necessary to specify the compression algorithms to be used, since the approach is agnostic with respect to them. The simplified idea is to use a set of configurations of a specific algorithm, each on a partition of the data to be compressed. The percentage of data to be compressed with each algorithm is chosen to maximize the use of the available time, provided as input budget, in order to maximize the degree of compressibility obtained. In the case of single documents, this set of configurations can specify the use of a single algorithm or a pair of algorithms. For multiple documents, instead, combinations of algorithms will be used where each will be executed on a specific document. Each element of these combinations can be a single algorithm or a pair of algorithms, but it can be experimentally shown that in all cases it is sufficient to use a pair of algorithms, at most only for one document, using a single algorithm for the remaining documents. Therefore, in this paper we are not considering the possibility of compressing a single document in parts, with more than one data compression algorithm, because doing so would only bring a low gain that does not justify the increase in complexity due to the decoding. Assuming a function that compresses a given set of data, a time optimization activity would allow us to reduce the economic costs of our system without sacrificing more than necessary the reductions in data size. When we normally apply data compression, all the data we want to compress are input into a single compression tool which will try to reduce the size of the input data (while keeping the same information content) in a certain time \(t\), and the tool will return as its output the compressed data. The focus is frequently placed on the algorithm's compression efficiency, while the time required for compression is often overlooked, provided it remains within a reasonable limit. This way of doing may not be convenient in situations where you want to specify a time \(t^{\prime}\) that could also be less than \(t\), within which you want to complete the compression process: that is, when you are trying to optimize compression performance while respecting specified time limits. Recall that a convex surface, or convex hull, of a set of points \(S\) is the intersection of all convex sets that contain \(S\) and that the lower polygon chain contains all points that minimize the second coordinate (\(y\), which in our case will be the size of the compressed document) for each \(x\) (in our case, time) of the convex surface. If we consider the optimization of the compression of a single document, with the notions of a convex surface and lower polygon chain it is possible to obtain the set of optimal mixes of algorithms for any time budget. The basic idea is to obtain the lower polygon chain of the best algorithms for each time budget, representing them on a two-dimensional plane by choosing as coordinates the time required (\(x\)) and the resulting dimension from the execution of the algorithm (\(y\)). By best algorithms, we mean the input algorithms sorted by the time required, filtered by taking only those that lead to an improvement in terms of compression compared to the previous algorithm. This filtering activity removes two classes of algorithms. The algorithms that would cause a worse resulting dimension for the same time budget compared to another mix are excluded. In case two algorithms require the same amount of time, the one with the smaller resulting dimension is preferred. By building the convex surface of the remaining algorithms, we can obtain the lower polygon chain composed of the algorithms involved in each possible optimal mix.