# US 10,311,090 B2 · Polygon-based indexing of places > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,311,090 B2 - Document ID: US10311090B2 - Status: Granted - Kind: B2 - Application number: 15/260,090 - Filed: 2016-09-08 - Published: 2016-12-29 - Granted: 2019-06-04 - Earliest claimed: 2014-03-20 - Assignees: Facebook, Inc. - Applicants: Facebook, Inc. - Inventors: Stanislav Basovnik; Abhinav A. Vora - Web page: https://patentgrep.com/patent/US10311090B2 ## CPC - G06F 16/29: Geographical information databases - G06F 16/319: {Inverted lists} - G06F 16/334: Query execution (filtering based on additional data G06F16/335) - G06Q 10/00: Administration; Management - G06Q 10/02: Reservations, e.g. for tickets, services or events - G06Q 10/48: using social graphs - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR ## Abstract In particular embodiments, a method includes receiving a query for a specified place or a type of place, receiving an identification of a location of the computing device within a first map tile, identifying first places that are located at least partially within the first map tile and correspond to the query, the first places being identified in an index by records that correspond to the first map tile, and identifying second places that correspond to the query and are each located at least partially within second map tiles that include a parent map tile associated with the first map tile. The second places are identified in the index by one or more records that correspond to the second map tiles. The method further includes determining scores for places that include the first and second places based on one or more relevance factors. ## Claims ### Claim 1 A method for identifying places associated with a user of a computing device comprising: by the computing device, receiving a query from the user for a specified place or a type of place; by the computing device, receiving an identification of a location of the computing device of the user, wherein the location is within a first map tile; by the computing device, identifying 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; by the computing device, when the one or more first places comprise less than a threshold number of places, identifying 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; by the computing device, calculating 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; by the computing device, determining 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 by the computing device, ranking the plurality of places based on the determined scores of the plurality places. ### Claim 2 (depends on 1) The method of claim 1, wherein: the index comprises a plurality of records, each record corresponds to a map tile and identifies one or more places corresponding to the map tile, each place of the one or more first places is modeled as a polygon that circumscribes the place, the place corresponds to a plurality of map tiles, wherein each map tile is at least partially contained within the polygon, and the place is identified in a plurality of records of the index corresponding to the plurality of map tiles, wherein the plurality of map tiles correspond to the polygon that circumscribes the place. ### Claim 3 (depends on 1) The method of claim 1, wherein the first map tile corresponds to a child node and the parent map tile corresponds to a parent node of the child node in a tree data structure, a root node in the tree data structure corresponds to a map, and parent nodes represent larger portions of the map than child nodes. ### Claim 4 (depends on 1) The method of claim 1, wherein the second map tiles include a neighbor tile of the first map tile. ### Claim 5 (depends on 1) The method of claim 1, wherein the relevance factors comprise relevance of a place to the query, social-relevance of a place, or a combination thereof. ### Claim 6 (depends on 1) The method of claim 1, wherein the relevance factors comprise social-graph information of the user of the computing device, and the social-graph information is associated with each place in the plurality of places. ### Claim 7 (depends on 6) The method of claim 6, wherein the score for each place is based on proximity of one or more of the user's social contacts to the place. ### Claim 8 (depends on 7) The method of claim 7, wherein the score for each place is proportional to a distance between the place and one or more of the user's friends. ### Claim 9 (depends on 6) The method of claim 6, wherein the score for each place is based on how closely associated the place is with one or more of the user's social contacts who have previously interacted with the place. ### Claim 10 (depends on 6) The method of claim 6, wherein the score for each place is based on a degree of separation in a social graph between a user node of the user and a social-graph entity corresponding to the place. ### Claim 11 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. ### Claim 12 (depends on 11) The media of claim 11, wherein: the index comprises a plurality of records, each record corresponds to a map tile and identifies one or more places corresponding to the map tile, each place of the one or more first places is modeled as a polygon that circumscribes the place, the place corresponds to a plurality of map tiles, wherein each map tile is at least partially contained within the polygon, and the place is identified in a plurality of records of the index corresponding to the plurality of map tiles, wherein the plurality of map tiles correspond to the polygon that circumscribes the place. ### Claim 13 (depends on 11) The media of claim 11, wherein the first map tile corresponds to a child node and the parent map tile corresponds to a parent node of the child node in a tree data structure, a root node in the tree data structure corresponds to a map, and parent nodes represent larger portions of the map than child nodes. ### Claim 14 (depends on 11) The media of claim 11, wherein the second map tiles include a neighbor tile of the first map tile. ### Claim 15 (depends on 11) The media of claim 11, wherein the relevance factors comprise relevance of a place to the query, social-relevance of a place, or a combination thereof. ### Claim 16 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. ### Claim 17 (depends on 16) The system of claim 16, wherein: the index comprises a plurality of records, each record corresponds to a map tile and identifies one or more places corresponding to the map tile, each place of the one or more first places is modeled as a polygon that circumscribes the place, the place corresponds to a plurality of map tiles, wherein each map tile is at least partially contained within the polygon, and the place is identified in a plurality of records of the index corresponding to the plurality of map tiles, wherein the plurality of map tiles correspond to the polygon that circumscribes the place. ### Claim 18 (depends on 16) The system of claim 16, wherein the first map tile corresponds to a child node and the parent map tile corresponds to a parent node of the child node in a tree data structure, a root node in the tree data structure corresponds to a map, and parent nodes represent larger portions of the map than child nodes. ### Claim 19 (depends on 16) The system of claim 16, wherein the second map tiles include a neighbor tile of the first map tile. ### Claim 20 (depends on 16) The system of claim 16, wherein the relevance factors comprise relevance of a place to the query, social-relevance of a place, or a combination thereof.