Determining a location and area of a place based on distances between the first mean and check in locations

Patent metadata

Field	Value
Publication number	US-9426236-B2
Application number	US-201213545229-A
Country	US
Kind code	B2
Filing date	Jul 10, 2012
Priority date	Jul 10, 2012
Publication date	Aug 23, 2016
Grant date	Aug 23, 2016

Abstract

In one embodiment, a method includes calculating a first mean of check-in locations associated with a place; selecting a subset of the check-in locations based on distances between the first mean and the check-in locations; and determining a central location and at least a portion of a perimeter of the place based on the subset of the check-in locations.

First claim

What is claimed is:

1. A method comprising, by one or more computing devices:
accessing a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the nodes comprising:
a plurality of user nodes corresponding to a plurality of users of an online social network; and
a plurality of concept nodes corresponding to a plurality of places;

accessing geographic location data for a plurality of check-in locations associated with a place, wherein each of the check-in locations corresponds to an edge of the social graph corresponding to a check-in activity between a user node of a user and a concept node of the place;
calculating a first mean of the plurality of check-in locations;
selecting a subset of the check-in locations based on distances between the first mean and the check-in locations; and
determining a central location and at least a portion of a perimeter of the place based on the subset of the check-in locations.

2. The method of claim 1 , wherein calculating the first mean comprises weighting one or more of the check-in locations based on their recency, accuracy, trustworthiness, or carrier reliability.

3. The method of claim 2 , wherein the weighting of one or more of the check-in locations comprises an exponential decay function.

4. The method of claim 1 , wherein a check-in location comprises a geographic location of a check-in by a user of a social-networking system.

5. The method of claim 1 , wherein the central location is a center or a centroid.

6. The method of claim 1 , wherein calculating the first mean comprises:
projecting two-dimensional geographic coordinates of the check-in locations onto a three-dimensional sphere;
calculating a second mean in each dimension of the three-dimensional sphere; and
calculating the first mean by projecting the one or more of the second means onto a two-dimensional surface.

7. The method of claim 1 , wherein the distances between the first mean and the check-in locations are calculated using great-circle distances.

8. The method of claim 1 , wherein determining the central location and at least the portion of the perimeter comprises:
constructing a cumulative distribution function for the subset of the check-in locations with weighted percentile buckets in distances from the central location; and
determining the perimeter based at least in part on one or more characteristics of the cumulative distribution function.

9. The method of claim 1 , wherein, for each of one or more of the check-in locations, the place associated with the check-in location was selected by a user from a plurality of places presented to the user based on a determined geographic location of the user.

10. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:
access a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the nodes comprising:
a plurality of user nodes corresponding to a plurality of users of an online social network; and
a plurality of concept nodes corresponding to a plurality of places;

access geographic location data for a plurality of check-in locations associated with a place, wherein each of the check-in locations corresponds to an edge of the social graph corresponding to a check-in activity between a user node of a user and a concept node of the place;
calculate a first mean of the plurality of check-in locations;
select a subset of the check-in locations based on distances between the first mean and the check-in locations; and
determine a central location and at least a portion of a perimeter of the place based on the subset of the check-in locations.

11. The non-transitory storage media of claim 10 , wherein to calculate the first mean, the software is operable when executed to weight one or more of the check-in locations based on their recency, accuracy, trustworthiness, or carrier reliability.

12. The non-transitory storage media of claim 11 , wherein the weighting of one or more of the check-in locations comprises an exponential decay function.

13. The non-transitory storage media of claim 10 , wherein a check-in location comprises a geographic location of a check-in by a user of a social-networking system.

14. The non-transitory storage media of claim 10 , wherein the central location is a center or a centroid.

15. The non-transitory storage media of claim 10 , wherein to calculate the first mean, the software is operable when executed to:
project two-dimensional geographic coordinates of the check-in locations onto a three-dimensional sphere;
calculate a second mean in each dimension of the three-dimensional sphere; and
calculate the first mean by projecting the one or more of the second means onto a two-dimensional surface.

16. The non-transitory storage media of claim 10 , wherein the distances between the first mean and the check-in locations are calculated using great-circle distances.

17. The non-transitory storage media of claim 10 , wherein to determine the central location and at least the portion of the perimeter, the software is operable when executed to:
construct a cumulative distribution function for the subset of the check-in locations with weighted percentile buckets in distances from the central location; and
determine the perimeter based at least in part on one or more characteristics of the cumulative distribution function.

18. The non-transitory storage media of claim 10 , wherein, for each of one or more of the check-in locations, the place associated with the check-in location was selected by a user from a plurality of places presented to the user based on a determined geographic location of the user.

19. An apparatus comprising:
one or more processors; and
one or more computer-readable non-transitory storage media embodying instructions operable, when executed by the processors, to cause the processors to:
access a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the nodes comprising:
a plurality of user nodes corresponding to a plurality of users of an online social network; and
a plurality of concept nodes corresponding to a plurality of places;
access geographic location data for a plurality of check-in locations associated with a place, wherein each of the check-in locations corresponds to an edge of the social graph corresponding to a check-in activity between a user node of a user and a concept node of the place;

calculate a first mean of the plurality of check-in locations;
select a subset of the check-in locations based on distances between the first mean and the check-in locations; and
determine a central location and at least a portion of a perimeter of the place based on the subset of the check-in locations.

20. The apparatus of claim 19 , wherein to calculate the first mean, the instructions are operable, when executed by the processors, to cause the processors to weight one or more of the check-in locations based on their recency, accuracy, trustworthiness, or carrier reliability.

21. The apparatus of claim 19 , wherein the weighting of one or more of the check-in locations comprises an exponential deca

Assignees

• Jia Yuntao
• Narasimhan Mukund
• Chang Jonathan
• Redstone Joshua
• Facebook Inc

Inventors

• Jia Yuntao
• Narasimhan Mukund
• Chang Jonathan
• Redstone Joshua

Classifications

• G06Q10/40

  Business processes related to social networking or social networking services · CPC title

• G06F16/9537 Primary

  Spatial or temporal dependent retrieval, e.g. spatiotemporal queries · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/29

  Geographical information databases · CPC title

• G06F16/2379

  Updates performed during online database operations; commit processing · CPC title