Location of an autonomous driving vehicle (ADV) is determined with respect to a high definition map. On-boards sensors of the ADV obtain a 3D point cloud of objects surrounding the ADV. The 3D point cloud is organized into an ADV feature space of cells. Each cell has a median intensity value and a variance in elevation. To determine the ADV location, a coarse search of a subset of cells in the ADV feature space performed with respect to the high definition map, using a similarity metric that is based on the median intensity and variance in elevation of the candidate cell. When similarity of the first candidate cell is determined, a lookup table of similarity scores is generated and used for determining the similarity score for subsequent candidate cells. Then a fine search is performed on a small subset of candidate cells surrounding the highest similarity score cell.