For example, if the majority of encoding profiles in trial encoding profiles 155 correspond to numerous different values for encoding parameters with little impact on quality, bit rate, and encoding runtime, the encoding outputs will result in a tight cluster in data space 175. One example of an encoding parameter with low priority is the number of b frames. In turn, the estimated performance boundary curve derived from the tight cluster may not be an accurate representation of the true performance boundary curve that would be obtained through an exhaustive search. In contrast, if trial encoding profiles 155 results in encoding outputs in data space 175 that correspond to a wide range of quality, bit rate, and encoding runtimes, the estimated performance boundary curve may be a more accurate representation of the true performance boundary curve. Examples of encoding parameters with high priority include but are not limited to adaptive-quantization mode, adaptive-quantization strength, constant rate factor, inter noise reduction level, or quantization group size.