"Locality is taken as the surrounding or nearby region of something in the world. Without the notion of spatial order that it brings, the world cannot be understood. This thesis is dedicated to exploring locality present in the world, and specifically the visual world, as captured by digital images and videos for the purpose of designing better visual recognition algorithms. We consider traditional computer vision challenges like image classification and segmentation, attribute classification, action recognition and object tracking, which are not fully aware of locality, and ask ourselves the question: How can visual recognition profit from locality? We start by decomposing objects locally for efficient image classification and segmentation, and continue with attribute classification by exploiting locality. Then we propose a video representation considering both spatial and temporal locality in a video for action recognition, and end by enriching object tracking by locality specified with natural language description. Findings of this thesis may lead to a better understanding of how to explore locality for a wide variety of other challenges in computer vision as well."--Samenvatting auteur.