IDENTIFYING NEIGHBORS OF GEO-SPATIALLY DISTRIBUTED RADIO TRANSMITTERS

• US 20110084881A1
• Filed: 10/14/2009
• Published: 04/14/2011
• Est. Priority Date: 10/14/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Fischer, Markus
• Granted Patent: US 8,634,856 B2
• Time in Patent Office: Days
• US Class Current: 342/451
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: H04W 24/02 Arrangements for optimising operational condition
• CPC Class Codes: H04W 64/003 locating network equipment

Abstract

Processes and systems are presented, for identifying a set of neighbors of a radio transmitter based on available geo-spatial coordinates of radio transmitters in operation around the world. In one aspect, the identified set of radio transmitters can be have a desired size (in terms of number of neighbors and/or radial range). The identified set of radio transmitters can be further customized to include radio transmitters of a specific type, and/or radio transmitters that belong to specific network carriers, and/or other possible grouping criteria.

Claims

1. A method performed by a server computer, the method comprising:

receiving from a central source updates about geographically distributed radio transmitters;

responsive to the received updates, generating an associated set of neighbors for each of the geographically distributed radio transmitters, wherein the associated set of neighbors of a radio transmitter includes up to a predetermined number of geographically-closest neighboring radio transmitters of the radio transmitter, wherein each radio transmitter of the associated set of neighbors of the radio transmitter is located up to a predetermined geographical-distance away from the radio transmitter; and

upon request from a mobile device in communication with a given radio transmitter, providing to the mobile device geo-spatial coordinates for each of a generated set of neighbors associated with the given radio transmitter to facilitate location-based services (LBS).

2. The method of claim 1, wherein generating the associated set of neighbors for each of the geographically distributed radio transmitters comprises:

receiving a data-set including geo-spatial coordinates for each of the geographically distributed radio transmitters;

grouping the geographically distributed radio transmitters in latitude-bins, wherein each latitude-bin is centered on an associated latitude, has an identical latitude-angle range, and overlaps half of a next latitude-bin to the North and half of a next latitude-bin to the South; and

for each radio transmitter from each latitude-bin, generating a set of neighbors of a radio transmitter from a latitude-bin, wherein the radio transmitter is also from another latitude-bin, and each of the generated set of neighbors is from among radio transmitters, located in either of the latitude-bin and the other latitude-bin, that are separated from the radio transmitter by a longitude-distance shorter than the predetermined geographical-distance, wherein the longitude-distance between a first and second radio transmitters is measured, along a line of latitude of the latitude-bin, between a longitude line of the first radio transmitter and a longitude line of the second radio transmitter.

3. The method of claim 2, wherein generating the set of neighbors of the radio transmitter comprises:

sorting radio transmitters from the latitude-bin by longitude-distance to the radio transmitter;

building the set of neighbors of the radio transmitter, wherein radio transmitters included in the built set of neighbors are from the sorted latitude bin;

sorting radio transmitters in the other latitude-bin by longitude-distance to the radio transmitter; and

updating the built set of neighbors, wherein the radio transmitters included in the updated set of neighbors are either from the sorted latitude-bin or from the other sorted latitude-bin.

4. The method of claim 3, wherein building the set of neighbors of the radio transmitter comprises:

selecting a next radio transmitter from the sorted latitude-bin;

responsive to a longitude-distance between the radio transmitter and the selected radio transmitter being shorter than a maximum distance between the radio transmitter and anyone of the set of neighbors, calculating a geographical distance between the selected radio transmitter and the radio transmitter;

responsive to the calculated distance being shorter that the maximum distance, and to the set of neighbors having fewer that a predetermined number of radio transmitters, adding the selected radio transmitter to the set of neighbors;

responsive to the calculated distance being less that the maximum distance, and to the set of neighbors having the predetermined number of radio transmitters, eliminating from the set of neighbors a radio transmitter corresponding to the maximum distance prior to adding the selected radio transmitter to the set of neighbors; and

responsive to the longitude-distance between the radio transmitter and the selected radio transmitter being longer than the maximum distance, providing the set of neighbors for the radio transmitter.

5. The method of claim 4, further comprising:

tagging the selected radio transmitter; and

skipping the selected radio transmitter upon identification of the tag.

6. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

receiving from a central source updates about geographically distributed radio transmitters; and

responsive to the received updates, generating an associated set of neighbors for each of the geographically distributed radio transmitters, wherein the associated set of neighbors of a radio transmitter includes up to a predetermined number of geographically-closest neighboring radio transmitters of the radio transmitter, wherein each radio transmitter of the associated set of neighbors of the radio transmitter is located up to a predetermined geographical-distance away from the radio transmitter.

7. The computer storage medium of claim 6, wherein generating the associated set of neighbors for each of the geographically distributed radio transmitters comprises:

receiving a data-set including geo-spatial coordinates for each of the geographically distributed radio transmitters;

grouping the geographically distributed radio transmitters in latitude-bins, wherein each latitude-bin is centered on an associated latitude, has an identical latitude-angle range, and overlaps half of a next latitude-bin to the North and half of a next latitude-bin to the South; and

for each radio transmitter from each latitude-bin, generating a set of neighbors of a radio transmitter from a latitude-bin, wherein the radio transmitter is also from another latitude-bin, and each of the generated set of neighbors is from among radio transmitters, located in either of the latitude-bin and the other latitude-bin, that are separated from the radio transmitter by a longitude-distance shorter than the predetermined geographical-distance, wherein the longitude-distance between a first and second radio transmitters is measured, along a line of latitude of the latitude-bin, between a longitude line of the first radio transmitter and a longitude line of the second radio transmitter.

8. The computer storage medium of claim 7, wherein generating the set of neighbors of the radio transmitter comprises:

sorting radio transmitters from the latitude-bin by longitude-distance to the radio transmitter;

building the set of neighbors of the radio transmitter, wherein radio transmitters included in the built set of neighbors are from the sorted latitude bin;

sorting radio transmitters in the other latitude-bin by longitude-distance to the radio transmitter; and

updating the built set of neighbors, wherein the radio transmitters included in the updated set of neighbors are either from the sorted latitude-bin or from the other sorted latitude-bin.

9. The computer storage medium of claim 8, wherein building the set of neighbors of the radio transmitter comprises:

selecting a next radio transmitter from the sorted latitude-bin;

responsive to a longitude-distance between the radio transmitter and the selected radio transmitter being shorter than a maximum distance between the radio transmitter and anyone of the set of neighbors, calculating a geographical distance between the selected radio transmitter and the radio transmitter;

responsive to the calculated distance being shorter that the maximum distance, and to the set of neighbors having fewer that a predetermined number of radio transmitters, adding the selected radio transmitter to the set of neighbors;

responsive to the calculated distance being less that the maximum distance, and to the set of neighbors having the predetermined number of radio transmitters, eliminating from the set of neighbors a radio transmitter corresponding to the maximum distance prior to adding the selected radio transmitter to the set of neighbors; and

responsive to the longitude-distance between the radio transmitter and the selected radio transmitter being longer than the maximum distance, providing the set of neighbors for the radio transmitter.

10. The computer storage medium of claim 9, further comprising:

tagging the selected radio transmitter; and

skipping the selected radio transmitter upon identification of the tag.

11. A system comprising:

a user device;

one or more computers operable to interact with the device;

a set of geographically distributed assets of known latitude and longitude; and

a specified geographic location, wherein

the one or more computers are further operable to provide to the user device a subset of the set of assets, the subset comprising assets located within a predetermined radial-distance from the specified location, wherein the one or more computers are configured to perform operations comprising;

group assets from the set of geographically distributed assets in latitude-bins, each latitude-bin having a width equal to twice the predetermined radial-distance, and overlapping half of a next-to-the-North latitude-bin and half of a next-to-the-South latitude-bin;

sort the assets, in two latitude-bins containing the specified location, by longitude-distance to the specified location;

for each sorted asset having the longitude-distance to the specified location shorter than the predetermined radial-distance, calculate a geographical-distance to the specified location; and

add to the subset an asset having the calculated geographical-distance to the specified location shorter than the predetermined radial-distance.

12. The system of claim 11, wherein the one or more computers comprise a server operable to interact with the device through a data communication network, and the device is operable to interact with the server as a client.

13. The system of claim 12, wherein the device comprises a mobile telephone configured to request from the server the subset of assets located within a predetermined radial-distance from the specified location.

14. The system of claim 11, wherein the one or more computers consist of one computer, the device is a user interface device, and the one computer comprises the user interface device.

15. The system of claim 11, wherein the set of geographically distributed assets comprises radio transmitters.

16. The system of claim 15, wherein the radio transmitters comprise cell tower transmitters.

17. The system of claim 15, wherein the radio transmitters comprise one or more of Wireless Fidelity (WiFi) and Worldwide Interoperability for Microwave Access (WiMAX) transmitters.

18. The system of claim 15, wherein the radio transmitters comprise cell tower transmitters and one or more of WiFi and WiMAX transmitters.

19. A system comprising:

a user device;

one or more computers operable to interact with the device;

a set of geographically distributed radio transmitters of known latitude and longitude; and

a specified geographic location, wherein

the one or more computers are further operable to provide to the device a subset of the set of radio transmitters, the subset comprising up to a predetermined number of radio transmitters located within a predetermined radial-distance from the specified location, wherein the one or more computers are configured to perform operations comprising;

group radio transmitters from the set of geographically distributed radio transmitters in latitude-bins, each latitude-bin having a width equal to twice the predetermined radial-distance, and overlapping half of a next-to-the-North latitude-bin and half of a next-to-the-South latitude-bin;

sort the radio transmitters, in two latitude-bins containing the specified location, by longitude-distance to the specified location;

for each sorted radio transmitter having the longitude-distance to the specified location shorter than a maximum distance for the subset, calculate a geographical-distance to the specified location, wherein the maximum distance for the subset is equal to

the predetermined radial-distance, if the predetermined number of radio transmitters has not been reached, and

a geographical-distance corresponding to an radio transmitter of the subset that is located farthest from the specified location, if the predetermined number of radio transmitters has been reached;

add to the subset, a radio transmitter having the calculated geographical-distance shorter than the maximum distance for the subset; and

responsive to the predetermined number of radio transmitters having been reached, remove from the subset the radio transmitter that is located farthest from the specified location.

20. A computer-implemented method for searching waypoints, the method comprising:

a) receiving a set of waypoints, each waypoint having associated latitude and longitude values;

b) ordering the received set of waypoints along lines of latitude, sorted by longitude values;

c) closing the lines of latitude by linking the highest and lowest longitude value waypoints per latitude line;

d) examining each one of the set of waypoints starting at a reference waypoint on a line of latitude and moving away from the reference waypoint through longitude values;

e) during the examination, ascending and descending along the lines of latitude and calculating a geographical-distance between the reference waypoint and an examined neighboring waypoint;

f) stopping examination and providing a set of neighbors of the reference waypoint when a last examined waypoint is closer than a next waypoint in latitude-distance, either ascending or descending, wherein the set of neighbors comprises the examined waypoints; and

g) repeating steps (d-f) for all of the set of waypoints along the lines of latitude, for all the lines of latitude.