# Data Compression with a Time Limit
## 2 Data Compression with a Time Limit
### A Data Compression Algorithm with a Time Limit
The proposed algorithm searches for an _optimal-mix_, i.e., an optimal setup configuration (among many considered) that can be used to compress a file \(f\), given a time budget. As we will see, the search is not a trivial process, as it adopts a technique that builds a function that will consider potential setups that could be part of the mixing, and subsequently, among all the candidates, two or more are chosen. The algorithm that is described next allows you to obtain all the _useful-setups_ for a certain file \(f\) to be compressed. Subsequently, it will be possible to obtain the optimal mix once the time budget \(t^{\prime}\) has been set. The inputs of the algorithm are pairs (\(b_{i}\), \(t_{i}\)), where each pair represents a setup: \(t_{i}\) represents the time taken by the setup to compress the file \(f\), while \(b_{i}\) is the resulting size, as in [1]. The algorithm for finding the optimal mix consists of four main steps, listed below:  
1. Determination of the pairs (\(b_{i}\), \(t_{i}\)) for each setup; these pairs are obtained by running each compression tool individually on the file \(f\) or by simply estimating its performance. 2. Sorting the setups in an ascending manner by \(t_{i}\), with \(b_{i}\) used as the second index in descending order. 3. Removal of the worst setups and construction of the convex hull of the remaining points:Between two setups that take the same time to execute, the one that gives the largest output size is discarded. 2. All setups that give an output size that is too large compared to others that take less time are discarded. 4. Acquisition of the _optimal-mix_ given a time budget \(t^{\prime}\). Phase 3 will build what in computational geometry is called the convex hull, that is, given a set of points, the determination of the smallest convex set that can contain them all. As proved in [1], the setups located at the vertices of the lower part of the convex hull are the only _useful-setups_. _Useful-mixes_ will always be two setups connected by an arc on the bottom edge of the polygon. Given \(m\) useful setups arranged in ascending order of running time and a time budget \(t^{\prime}\), the goal is to identify the optimal combination of setups, \(a\) and \(b\), along with the fractions of files, \(r_{a}\) and \(r_{b}\), that each setup will handle. In the non-trivial case where \(t_{1}<t^{\prime}<t_{2}\), the chosen combination consists of the two adjacent setups, a and b, such that \(t_{b}<t^{\prime}<t_{a}\). After finding the optimal mix, the percentage of data \(D\) that must be compressed with the chosen compression tools is calculated as in [1]. Assuming we have two setups \(s_{a}\) and \(s_{b}\) with times \(t_{a}\) and \(t_{b}\), respectively, choosing \(t^{\prime}\) as the time budget such that \(t_{b}<t^{\prime}<t_{a}\), the fraction of the file \(f\) to compress with \(s_{a}\) will be:  
\[r_{a}=(t^{\prime}-t_{b})/(t_{a}-t_{b})\]  
The fraction of \(D\) compressed by the \(s_{b}\) setup will be:  
\[r_{b}=1-r_{a}.\]  
In a multi-document context, each document typically possesses its own unique convex hull. Consequently, optimizing compression requires addressing multiple convex hulls simultaneously. Since the effectiveness of a particular tool or configuration depends on the document's specific information characteristics, the set of optimal configurations will vary across documents. A critical part of the solution involves an algorithm that consolidates the individual convex hulls into a unified convex hull. This unified structure allows the system to determine the best configuration for a given computational time constraint with ease, as explained in [1]. To illustrate how the merged sequence facilitates finding the optimal configuration for any compute-time limit, as outlined in [1], the process begins by calculating the compute time required when the least resource-intensive configurations are applied across all documents. The algorithm then iterates through successive configuration vectors in the merged sequence, recalculating the compute time at each step.