Associating geographic attributes with a physical location including a threshold portion of a geographic region

Patent metadata

Field	Value
Publication number	US-9641972-B1
Application number	US-201615063457-A
Country	US
Kind code	B1
Filing date	Mar 7, 2016
Priority date	Mar 7, 2016
Publication date	May 2, 2017
Grant date	May 2, 2017

Abstract

An online system receives a description of a physical location associated with a content item and a threshold distance of the physical location. To identify users eligible to be presented with the content item, the online system divides a geographic map of the physical location associated with the content item into a plurality of geo-tiles each representing a portion of the map. The online system computes and stores values describing portions of a geographic region represented by certain geo-tiles and associates the geographic region with the physical location if the stored values equal or exceed a threshold value. If the geographic region is associated with the physical location, users associated with the geographic region are identified by the online system as eligible to receive the content item.

First claim

What is claimed is:

1. A method comprising:
accessing, at an online system, a set of geo-tiles associated with a map of a physical location, each geo-tile representing a section of the map;
determining, for each geo-tile, whether a threshold portion of the geo-tile represents a portion of a geographic region;
responsive to determining at least the threshold portion of the geo-tile represents a portion of the geographic region:
computing a value associated with the geo-tile, the value based at least in part on the portion of the geographic region represented by the geo-tile, and
storing the computed value with an identifier associated with the geo-tile;

responsive to determining less than the threshold portion of the geo-tile represents the portion of the geographic region:
accessing an additional set of geo-tiles, the additional set of geo tiles collectively representing the section of the map of the physical location region represented by the geo-tile,
determining, for each of the additional set of geo-tiles,
whether a portion of the geo-tile representing the portion of the geographic region is at least the threshold portion,

responsive to determining at least the threshold portion of the geo tile of the additional set represents a portion of the geographic region,
computing the value associated with the geo-tile, and
storing the computed value with an identifier associated with the geo-tile;

determining the portion of the geographic region included in the map based at least in part on the stored values; and
storing the determined portion in an index associated with the geographic region and the map of the physical location.

2. The method of claim 1 , further comprising:
determining whether the portion of the geographic region included in the map is at least a threshold portion of the geographic region based at least in part on the stored index.

3. The method of claim 1 , wherein accessing the additional set of geo-tiles comprises:
for each geo-tile having less than the threshold portion representing the portion of the geographic region, dividing the section of the map represented by the geo-tile into the additional set of geo-tiles, each of the additional set of geo-tiles representing a smaller section of the map represented by the geo-tile; and
repeating the dividing until at least the threshold portion of the geographic region is represented by each of the additional set of geo-tiles.

4. The method of claim 1 , wherein the set of geo-tiles and the additional set of geo-tiles include geo-tiles of various sizes.

5. The method of claim 1 , wherein the physical location comprises a geographic area within a threshold distance of the physical location.

6. The method of claim 1 , wherein the physical location is selected from a group consisting of: a physical address, a set of geographic coordinates, a neighborhood, a landmark, and any combination thereof.

7. The method of claim 1 , wherein the geographic region is selected from a group consisting of: a city, a zip code, an area code, a neighborhood, a county, and any combination thereof.

8. The method of claim 1 , further comprising:
receiving criteria for presenting a content item to one or more users of the online system, the criteria including the physical location and a threshold distance from the physical location;
determining whether the portion of the geographic region included in the map equals or exceeds a threshold value based at least in part on the index; and
responsive to determining the portion of the geographic region included in the map equals or exceeds the threshold value, associating the geographic region with the criteria.

9. The method of claim 8 , further comprising:
receiving a request to present content to a user of the online system;
responsive to determining an attribute of the user identifies the geographic region included in the map, including the content item in selection process selecting content for presentation to the user.

10. The method of claim 9 , wherein the attribute of the user identifying the geographic region included in the map is selected from a group consisting of: a hometown, a workplace, a current location, a birthplace, and any combination thereof.

11. A method comprising:
retrieving, at an online system, a set of geo-tiles associated with a map of a physical location, each geo-tile representing a section of the map and at least a portion of a geographic region;
for each geo-tile, generating one or more additional sets of geo-tiles, each additional set of geo-tiles representing a portion of the section of the map represented by the geo-tile;
identifying, from the one or more additional sets of geo-tiles, a subset of geo-tiles, wherein at least a threshold portion of each of the subset of geo-tiles represents the portion of the geographic region;
computing a value associated with each of the subset of geo-tiles, the value for a geo-tile of the subset based at least in part on the portion of the geographic region represented by the geo-tile of the subset of geo-tiles;
storing the computed values with identifiers associated with a corresponding geo-tile of the subset of geo-tiles;
determining whether the portion of the geographic region included in the map is at least a threshold portion based at least in part on the stored values; and
storing the determined portion in an index associated with the geographic region and the map of the physical location.

12. The method of claim 11 , wherein generating one or more additional sets of geo-tiles comprises:
for each geo-tile, dividing the section of the map represented by the geo-tile into a set of smaller geo-tiles, each smaller geo-tile representing a portion of the section of the map represented by the geo-tile; and repeating the dividing until less than a threshold portion of the geographic region is represented by each of the set of smaller geo-tiles.

13. A computer program product comprising a non-transitory computer-readable storage medium having instructions encoded thereon that, when executed by a processor, cause the processor to:
access, at an online system, a set of geo-tiles associated with a map of a physical location, each geo-tile representing a section of the map;
determine, for each geo-tile, whether a threshold portion of the geo-tile represents a portion of a geographic region;
responsive to determining at least the threshold portion of the geo-tile represents a portion of the geographic region:
compute a value associated with the geo-tile, the value based at least in part on the portion of the geographic region represented by the geo-tile, and
store the computed value with an identifier associated with the geo-tile;

responsive to determining less than the threshold portion of the geo-tile represents the portion of the geographic region:
access an additional set of geo-tiles, the additional set of geo-tiles collectively representing the section of the map of the physical location region represented by the geo-tile,
determine, for each of the additional set of geo-tiles, whether a portion of the geo-tile representing the portion of the geographic region is at least the threshold portion,
responsive to determining at least the threshold portion of the geo-tile of the additional set represents a portion of the geographic region,
compute the value associated with the geo-tile, and
store the computed value with an identifier associated with the geo-tile;

determine the portion of the geographic region included in the map based at least in part on the stored values; and
store the determined portion in an index associated with the geographic region

Assignees

• Facebook Inc

Inventors

• Hughes Charles Joseph

Classifications

• H04L67/306

  User profiles · CPC title

• H04W4/021 Primary

  Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences · CPC title