Adaptive location determination

• US 8,660,576 B2
• Filed: 01/15/2010
• Issued: 02/25/2014
• Est. Priority Date: 01/15/2010
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Huang, Ronald K.
• Primary Examiner(s): SAMS, MATTHEW C
• Application Number:
  US12/688,811
• Publication Number:
  US 20110177832A1
• Time in Patent Office: 1,502 Days
• Field of Search: 4554561-457, 701/469, 701/300, 342/357.4, 342/357.42, 342/357.43, 342/450, 342463-465
• US Class Current: 455/456.1
• CPC Class Codes: H04L 67/04 specially adapted for terminals or networks with limited capabilities; specially adapted for terminal portability
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04W 64/003 locating network equipment

Abstract

Methods, program products, and systems for adaptive location determination are described. A server computer can receive location information from location-aware mobile devices (e.g., GPS-enabled devices) located in a cell of a cellular communications network. The server computer can calculate an average geographic location using the received locations and distance between each location and the calculated average. The server computer can exclude locations that are sufficiently far away from the average. The server computer can repeat the calculation and exclusion until a level of precision is achieved for the average geographic location. The average geographic location and an error margin can be associated with the cell. The server computer can provide the average geographic location and the error margin to a mobile device (e.g., a non-GPS-enabled device) that is in the cell. The mobile device can display the information on a map display of the mobile device.

Claims

1. A method, comprising:

receiving a set of locations from mobile devices, each location being associated with a cell of a cellular communication network;

in a first iteration;

determining a first centroid of the locations using the set of locations;

determining distances between the first centroid and locations in the set; and

reducing the set of locations, including excluding a first location from the set and preserving a second location in the set based on a first threshold and the distances between the first centroid and the locations;

in a second iteration;

determining a second centroid of locations using locations remaining in the reduced set of locations;

determining distances between the second centroid and locations in the reduced set of locations; and

further reducing the set of locations, including excluding, from the set and based on a second threshold and the distances determined in the second iteration, the second location preserved during the first iteration;

determining a geographic area having a center and a radius, the center corresponding to the second centroid, the radius corresponding to at least one of the distances determined in the second iteration; and

associating the geographic area with the cell when an exit condition is satisfied.

2. The method of claim 1, where the radius is calculated based on a longest distance between the second centroid and a location remaining in the set after the second iteration.

3. The method of claim 1, where the exit condition is satisfied when a number of iterations reaches a threshold number.

4. The method of claim 1, where the exit condition is satisfied when the radius of the geographic area determined in the second iteration reaches below a threshold radius.

5. The method of claim 1, where excluding the second location from the reduced set includes:

determining a threshold distance to the second centroid within which a percentage of the locations remaining in the set that has been reduced in the first iteration are located; and

excluding the second location from the set when the distance between the second centroid and the second location exceeds the threshold distance.

6. The method of claim 1, where each of the locations in the set includes a latitude and a longitude.

7. The method of claim 6, where each of the locations in the set further includes an altitude.

8. The method of claim 1, further comprising:

providing the geographic area for displaying on a map display of a mobile device.

9. The method of claim 1, wherein determining the second centroid of the locations uses a calculation that is different from a calculation used in the first iteration.

10. The method of claim 9, wherein at least one calculation for determining the centroid includes calculating an average geographic location using the set of locations.

11. A system, comprising:

one or more computers configured to perform operations comprising;

receiving a set of locations from mobile devices, each location being associated with a cell of a cellular communication network;

in a first iteration;

determining a first centroid of the locations using the set of locations;

determining distances between the first centroid and locations in the set; and

reducing the set of locations, including excluding a first location from the set and preserving a second location in the set based on a first threshold and the distances between the first centroid and the locations;

in a second iteration;

determining a second centroid of locations using locations remaining in the reduced set of locations;

determining distances between the second centroid and locations in the reduced set of locations; and

further reducing the set of locations, including excluding, from the set and based on a second threshold and the distances determined in the second iteration, the second location preserved during the first iteration;

determining a geographic area having a center and a radius, the center corresponding to the second centroid, the radius corresponding to at least one of the distances, determined in the second iteration; and

associating the geographic area with the cell when an exit condition is satisfied.

12. The system of claim 11, where the radius is calculated based on a longest distance between the second centroid and a location remaining in the set after the second iteration.

13. The system of claim 11, where the exit condition is satisfied when a number of iterations reaches a threshold number.

14. The system of claim 11, where the exit condition is satisfied when the radius of the geographic area determined in the second iteration reaches below a threshold radius.

15. The system of claim 11, where excluding the second location from the reduced set includes:

determining a threshold distance to the second centroid within which a percentage of the locations remaining in the set that has been reduced in the first iteration are located; and

excluding the second location from the set when the distance between the second centroid and the second location exceeds the threshold distance.

16. The system of claim 11, where each of the locations in the set includes a latitude and a longitude.

17. The system of claim 16, where each of the locations in the set further includes an altitude.

18. The system of claim 11, the operations further comprising:

providing the geographic area for displaying on a map display of a mobile device.

19. A computer program product tangibly stored on a non-transitory storage device, operable to cause data processing apparatus to perform operations comprising:

receiving a set of locations from mobile devices, each location being associated with a cell of a cellular communication network;

in a first iteration;

determining a first centroid of the locations using the set of locations;

determining distances between the first centroid and locations in the set; and

reducing the set of locations, including excluding a first location from the set and preserving a second location in the set based on a first threshold and the distances between the first centroid and the locations;

in a second iteration;

determining a second centroid of locations using locations remaining in the reduced set of locations;

determining distances between the second centroid and locations in the reduced set of locations; and

further reducing the set of locations, including excluding, from the set and based on a second threshold and the distances determined in the second iteration, the second location preserved during the first iteration;

determining a geographic area having a center and a radius, the center corresponding to the second centroid, the radius corresponding to at least one of the distances determined in the second iteration; and

associating the geographic area with the cell when an exit condition is satisfied.

20. The product of claim 19, where the radius is calculated based on a longest distance between the second centroid and a location remaining in the set after the second iteration.

21. The product of claim 19, where the exit condition is satisfied when a number of iterations reaches a threshold number.

22. The product of claim 19, where the exit condition is satisfied when the radius of the geographic area determined in the second iteration reaches below a threshold radius.

23. The product of claim 19, where excluding the second location from the reduced set includes:

determining a threshold distance to the second centroid within which a percentage of the locations remaining in the set that has been reduced in the first iteration are located; and

excluding the second location from the set when the distance between the second centroid and the second location exceeds the threshold distance.

24. The product of claim 19, where each of the locations in the set includes a latitude and a longitude.

25. The product of claim 24, where each of the locations in the set further includes an altitude.

26. The product of claim 19, the operations further comprising:

providing the geographic area for displaying on a map display of a mobile device.