Techniques for localizing a vehicle include obtaining an image from a camera, identifying a set of image feature points in the image, obtaining an approximate location of the vehicle, determining a set of sub-volumes (SVs) of a map to access based on the approximate location, obtaining map feature points and associated map feature descriptors associated with the set of SVs, determining a set of candidate matches between the set of image feature points and the obtained map feature points, determining a set of potential poses of the camera from candidate matches from the set of candidate matches and an associated reprojection error estimated for remaining points to select a first pose of the set of potential poses having a lowest associated reprojection error, determining the first pose is within a threshold value of an expected vehicle location, and outputting a vehicle location based on the first pose.