Towards a Knowledge Base for Performance Data: A Formal Model for Performance Comparison

This paper has been motivated by two observations. First, empirical comparison of algorithms is often carried out in an ad hoc manner. Second, performance data is abundantly generated, yet often not efficiently used. This second observation is particularly valid in the presence of evolutionary computing and other metaheuristic techniques. Inspired by these observations, a formal model for performance is introduced wherein the space of possible performances is modelled as a total order. On top of the total order, a quantification of the difference between performances is defined. The model is illustrated by formally defining the "penalised runtime" criterion for data from the 2014 SAT competition. Finally, the idea of defining questions in terms of a formal performance model is introduced, thereby taking the first step towards a knowledge base for performance data. Regardless of problem domain, the same questions can be answered by the knowledge base, provided performance is measured in a manner compliant with the formal model.status: publishe