Determining a Location and Area of a Place

• US 20140019532A1
• Filed: 07/10/2012
• Published: 01/16/2014
• Est. Priority Date: 07/10/2012
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Narasimhan, Mukund, Chang, Jonathan, Redstone, Joshua, Jia, Yuntao
• Granted Patent: US 9,426,236 B2
• Time in Patent Office: Days
• US Class Current: 709/204
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: H04L 67/306 User profiles
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34

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.

Claims

1. A method comprising, by one or more computing devices:

accessing data for a plurality of check-in locations associated with a 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. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

access data for a plurality of check-in locations associated with a 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.

10. The media of claim 9, 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.

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

12. The media of claim 9, wherein a check-in location comprises a geographic location of a check-in by a user of a social-networking system.

13. The media of claim 9, wherein the central location is a center or a centroid.

14. The media of claim 9, 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.

15. The media of claim 9, wherein the distances between the first mean and the check-in locations are calculated using great-circle distances.

16. The media of claim 9, 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.

17. 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 data for a plurality of check-in locations associated with a 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.

18. The apparatus of claim 17, 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.

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

20. The apparatus of claim 17, wherein a check-in location comprises a geographic location of a check-in by a user of a social-networking system.