Systems, methods, and computer storage media having computer-executable instructions embodied thereon that return query completions are provided. A user of a computing device like a mobile phone may enter a prefix. In turn, the prefix and location information associated with the device are transmitted to a server device. The server device receives the prefix and location information. The prefix and the location information are matched with names and locations of entities stored in a database connected to the server device. The server device transmits query completion data to the mobile device. The query completion data includes one or more names that complete the received prefix. The names provided by the server device may be associated with entities that are within a threshold radius of the location information.