# US 12,602,445 B2 · Query completion based on location > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,602,445 B2 - Document ID: US12602445B2 - Status: Granted - Kind: B2 - Application number: 18/636,065 - Filed: 2024-04-15 - Published: 2024-08-01 - Granted: 2026-04-14 - Earliest claimed: 2011-09-15 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Technology Licensing, LLC - Inventors: Hussein Mohamed Mehanna; Tabreez Govani; Jun Wang; Kun Jing - Web page: https://patentgrep.com/patent/US12602445B2 ## CPC - G06F 16/9537: Spatial or temporal dependent retrieval, e.g. spatiotemporal queries - G06F 16/24578: {using ranking} - G06F 16/3322: {using system suggestions (G06F16/3325 takes precedence)} - G06F 16/9535: Search customisation based on user profiles and personalisation - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract 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. ## Claims ### Claim 1 A computer-implemented method comprising: receiving a query prefix including a set of characters provided by a user and a location associated with a device operated by the user; matching the location and the query prefix to a first set of entities included in a database to select a first tile of a set of tiles, the database including a plurality of levels where levels of the plurality of levels include all entities stored in the database and a first level is divided into the set of tiles, where the first tile of the set of tiles represents a geographic area and stores at least one entity of the first set of entities in a trie including a level identifier, a tile identifier, and an entity name; selecting a second tile of the set of tiles to search based on a number of entities within the first set of entities being below a threshold, where the second tile represents a second geographic area that includes at least a portion of the geographic area or is adjacent to the geographic area; matching the location and the query prefix to a second set of entities include in the second tile of the set of tiles; generating a set of results by at least generating a ranking of entities included in the first set of entities and the second set of entities based on a set of factors, where the ranking indicates a value associated with the entities and the set of factors includes at least one of: a distance relative to the location, a popularity, a set of reviews, a frequency, or a combination thereof; and return the set of results based on ranking. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein selecting the second tile of the set of tiles to search based on the number of entities further comprises selecting the second tile based on the number of entities being below a threshold. ### Claim 3 (depends on 1) The computer-implemented method of claim 1, wherein the set of factors includes at least one of: distance from the location, popularity, reviews, and frequency. ### Claim 4 (depends on 3) The computer-implemented method of claim 3, wherein the database includes a set of popularity tries which store popular entities relative to other entities associated with the first tile. ### Claim 5 (depends on 4) The computer-implemented method of claim 4, wherein the set of popularity tries is searched for a match to the location and the query prefix prior to the trie. ### Claim 6 (depends on 1) The computer-implemented method of claim 1, wherein the first level and a second level of the plurality of levels include a different number of tiles. ### Claim 7 (depends on 6) The computer-implemented method of claim 6, wherein the set of tiles associated with the first level represent a larger geographic scope then a second set of tiles associated with the second level. ### Claim 8 (depends on 7) The computer-implemented method of claim 7, wherein the first level and the second level include data representing the first set of entities and the second set of entities. ### Claim 9 (depends on 7) The computer-implemented method of claim 7, wherein the set of tiles and the second set of tiles include a different number of entities. ### Claim 10 One or more computer storage media storing computer-useable instructions that, when used by one or more computing devices, cause the one or more computing devices to perform operations comprising: receiving a query prefix and a location, the query prefix including a set of characters; determining a set of entities that match the query prefix and the location, the set of entities maintained in a database including a set of levels where levels of the set of levels include data representing all entities stored in the database and a first level of the set of levels is divided into a plurality of tiles, where a first tile of the plurality of tiles represent a geographic area and stores at least one entity in a trie including a level identifier, a tile identifier, and an entity name, where the trie is stored in a data structure that is queried to obtain entities of the set of entities; selecting a second level of the set of levels to search based on a number of entities within the set of entities being below a threshold, where the second level is selected to adjust a number of candidate entities such that the number of candidate entities are above the threshold; determining a second set of entities by at least matching the location and the query prefix to the second set of entities included in a second tile within the second level of the database; and returning a set of results that includes a ranking of entities included in the second set of entities based on a set of factors. ### Claim 11 (depends on 10) The one or more computer storage media of claim 10, wherein the query prefix and the location are received from a mobile device. ### Claim 12 (depends on 11) The one or more computer storage media of claim 11, wherein returning the set of results includes transmitting the set of results to the mobile device. ### Claim 13 (depends on 10) The one or more computer storage media of claim 10, wherein the second set of entities includes names that are partial matches to the query prefix. ### Claim 14 (depends on 10) The one or more computer storage media of claim 10, wherein the set of factors includes distance, popularity, reviews, and frequency. ### Claim 15 (depends on 14) The one or more computer storage media of claim 14, wherein the first level and the second level contain a different number of tiles. ### Claim 16 (depends on 10) The one or more computer storage media of claim 10, wherein a first geographic scope of the second tile is less than a second geographic scope of the first tile. ### Claim 17 (depends on 16) The one or more computer storage media of claim 16, wherein the first tile and the second tile include a different number of entities. ### Claim 18 (depends on 17) The one or more computer storage media of claim 17, wherein the second tile includes a popularity trie which stores popular entities relative to other entities associated with the second tile. ### Claim 19 A system, comprising: a processor; and a memory coupled to the processor and storing instructions that, when executed by the processor, perform operations, comprising: receiving a set of characters representing a query prefix and a location, associated with a user; matching a first set of entities included in a database to the query prefix and the location, the database including a set of levels where levels of the set of levels include entities stored in the database and a first level of the set of levels is divided into a plurality of tiles that represent a geographic area and stores a subset of entities of the first set of entities in a trie including a level identifier, a tile identifier, and an entity name, wherein the first set of entities are maintained within a first tile of the plurality of tiles; based on a number of entities within the first set of entities, matching a second set of entities to the location and the query prefix included in a second tile within the first level associated with a second geographic area associated with the location; and generating a ranking of the second set of entities based on geospatial coordinates and a set of factors including distance, popularity, reviews, frequency, or a combination thereof; and returning the second set of entities and the ranking and an indication that the second tile associated with the second geographic area was searched to obtain the second set of entities. ### Claim 20 (depends on 19) The system of claim 19, wherein the first tile and the second tile represent contiguous geographic area with a radius of the location.