Abstract Pattern Matching is a fundamental problem in computer vision, and image and video processing. Exhaustive-Search equivalent algorithms yield the same results as exhaustively searching all patterns in the image but significantly faster. Though much work have been done over the L1 and L2 distances, only small amount of work has been dedicated to the Chebyshev distance though its importance in many applications. In this paper, we provide an evaluation of available state-of-art exhaustive-search equivalent algorithm that targets the Chebyshev distance; we also provide detailed analysis of the performance characteristics of evaluated algorithms.