1. A computer-implemented method for generating a bounding box for a map label, the method comprising: receiving, from a map search system and in response to a map search query, map data that describes a geographic region, the map data including a collection of map labels that each describe a respective feature that is located in the geographic region, each map label comprising one or more text characters, and wherein each map label is associated with a respective popularity score; generating, for each map label in the collection of map labels, a respective bounding box having a width and a height, and wherein an area for the bounding box is the same as an area for the map label, wherein each bounding box is associated with a respective initial buffer space that includes the respective bounding box and some additional area beyond the respective bounding box, the initial buffer space defining an area within which other maps labels cannot be placed; determining that a first map label and a second map label, from the collection of map labels, were displayed in a previously presented frame for a map representing the geographic region; receiving a request to display a new frame for the map; determining, for the first map label, a first reduced buffer space, the first reduced buffer space being determined by reducing an initial buffer space of a first bounding box for the first map label by a first predetermined amount, the initial buffer space of the first bounding box including both the first bounding box and a first additional area beyond the first bounding box, the first reduced buffer space including both the first bounding box and a second additional area beyond the first bounding box, the second additional area being less than the first additional area; determining, for the second map label, a second reduced buffer space, the second reduced buffer space being determined by reducing an initial buffer space of a second bounding box for the second label by a second predetermined amount, the initial buffer space of the second bounding box including both the second bounding box and a third additional area beyond the second bounding box, the second reduced buffer space including both the second bounding box and a fourth additional area beyond the second bounding box, the fourth additional area being less than the third additional area; and generating, using the map data and the first and the second map labels, the new frame for the map, the new frame including the first and the second map labels, wherein the first map label is disposed within an area defined by the first bounding box, wherein the first bounding box lies within the first reduced buffer space, and wherein the second map label is disposed within an area defined by the second bounding box, wherein the second bounding box lies within the second reduced buffer space.