Query completion based on location

A system for storing entities for retrieval, the system comprising:

• a query completion component having one or more processors that receive a prefix and a location, and, based at least in part on the prefix and location, determine a tile in one or more levels of a database structure that represents a geographic area at a plurality of levels, each level divided into a plurality of tiles each having a geographic scope, and for successive levels, the tiles in each successive level have a progressively reduced geographic scope, wherein to determine the tile comprises:
• selecting between a first level and a second level from the successive levels for returning matching entities based at least in part on a first count of the matching entities in a first tile at the first level being below a threshold and a second count of the matching entities in a second tile at the second level being above the threshold;
• and
• a data store component having one or more storage locations that store the entities in multiple levels based on locations associated with the entities, wherein the entities are stored in tries including a level identifier, a tile identifier, and an entity name, wherein the tries include data structures that, in response to a query including the prefix, return the matching entities that include the prefix within a corresponding level and a corresponding tile to the one or more processors for ranking based on popularity and distance from a user that provides the prefix and the location.

At least one memory device storing computer-usable instructions which, when executed by at least one processor, implement a method of storing entities for retrieval, the method comprising:

• receiving a prefix and a location;
• mapping the location to a tile in one or more levels of a database structure that represents a geographic area at a plurality of levels, each level divided into a plurality of tiles each having a geographic scope, and for successive levels, the tiles in each successive level have a progressively reduced geographic scope, wherein to map the location to the tile comprises:
• selecting between a first level and a second level from the successive levels for returning matching entities based at least in part on a first count of the matching entities in a first tile at the first level being below a threshold and a second count of the matching entities in a second tile at the second level being above the threshold;
• and
• storing the entities in multiple levels in the database structure based on locations associated with the entities, wherein the entities are stored in tries including a level identifier, a tile identifier, and an entity name, wherein the tries include data structures that, in response to a query including the prefix, return the matching entities that include the prefix within a corresponding level and a corresponding tile to the at least one processor for ranking based on popularity and distance from a user that provides the prefix and the location.