A map searching system determines locations responsive to a search query. The map searching system parses the search query to generate a set of search tokens and searches a plurality of location category indices using the search tokens. The location category indicies specify indexes of locations according to various location categories, such as points of interest and cross streets. The resulting records selected from the search tokens are scored based on scoring weights specific to the location category index that a record was selected from. After scoring, a number of high-scoring records are selected as the responsive records to the location search.