Polygon-based indexing of places

One or more computer-readable non-transitory storage media embodying software for identifying places associated with a user of a computing device, wherein the software is operable when executed by the computing device to:

• receive a query from the user for a specified place or a type of place;
• receive an identification of a location of the computing device of the user, wherein the location is within a first map tile;
• identify one or more first places that are located at least partially within the first map tile and correspond to the query, wherein the one or more first places are identified in an index by one or more records that correspond to the first map tile;
• when the one or more first places comprise less than a threshold number of places, identify one or more second places that are each located at least partially within one or more second map tiles and correspond to the query,
• wherein the second map tiles include a parent map tile associated with the first map tile, and the second places are identified in the index by one or more records that correspond to the second map tiles;
• calculate a distance from each of a plurality of places including the first and second places to the user based at least in part on a forward index, the location of the user, and one or more sample points associated with that place;
• determine scores for the plurality of places including the first and second places based on one or more relevance factors comprising the distances from the plurality of places to the user;
• and
• rank the plurality of places based on the determined scores of the plurality places.

A system for identifying places associated with a user of a computing device comprising:

• one or more processors;
• and a memory coupled to the processors comprising instructions executable by the processors instructions, the processors being operable when executing the to:
• receive a query from the user for a specified place or a type of place;
• receive an identification of a location of the computing device of the user, wherein the location is within a first map tile;
• identify one or more first places that are located at least partially within the first map tile and correspond to the query, wherein the one or more first places are identified in an index by one or more records that correspond to the first map tile;
• when the one or more first places comprise less than a threshold number of places, identify one or more second places that are each located at least partially within one or more second map tiles and correspond to the query,
• wherein the second map tiles include a parent map tile associated with the first map tile, and the second places are identified in the index by one or more records that correspond to the second map tiles;
• calculate a distance from each of a plurality of places including the first and second places to the user based at least in part on a forward index, the location of the user, and one or more sample points associated with that place;
• determine scores for the plurality of places including the first and second places based on one or more relevance factors comprising the distances from the plurality of places to the user;
• and
• rank the plurality of places based on the determined scores of the plurality places.