  Order dependencies (ODs) capture relationships between ordered domains of
attributes. Approximate ODs (AODs) capture such relationships even when there
exist exceptions in the data. During automated discovery of ODs, validation is
the process of verifying whether an OD holds. We present an algorithm for
validating approximate ODs with significantly improved runtime performance over
existing methods for AODs, and prove that it is correct and has optimal
runtime. By replacing the validation step in a leading algorithm for
approximate OD discovery with ours, we achieve orders-of-magnitude improvements
in performance.
