A method, apparatus and computer program product are provided for visually searching feature sets that are organized in a grid-like manner. As such, a feature set associated with a location-based grid area may be received. The location-based grid area may also be associated with the location of a device. After receiving query image features, a visual search may be performed by comparing the query image features with the feature set. The search results are then returned. By conducting the visual search within a feature set that is selected based upon the location of the device, the efficiency of the search can be enhanced and the search may potentially be performed by the device, such as a mobile device, itself.