Finding a "Kneedle" in a Haystack: Detecting Knee Points in System Behavior

Computer systems often reach a point at which the relative cost to increase some tunable parameter is no longer worth the corresponding performance benefit. These "knees\´\´ typically represent beneficial points that system designers have long selected to best balance inherent trade-offs. While prior work largely uses ad hoc, system-specific approaches to detect knees, we present Kneedle, a general approach to on line and off line knee detection that is applicable to a wide range of systems. We define a knee formally for continuous functions using the mathematical concept of curvature and compare our definition against alternatives. We then evaluate Kneedle\´s accuracy against existing algorithms on both synthetic and real data sets, and evaluate its performance in two different applications.