System and method for tile-based reduction of access point location information

• US 10,042,035 B2
• Filed: 09/11/2012
• Issued: 08/07/2018
• Est. Priority Date: 06/08/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Grosman, Yefim, Mayor, Robert W., Huang, Ronald K., Konstantinov, Andrew
• Primary Examiner(s): Eng, George
• Assistant Examiner(s): DU, HUNG K
• Application Number:
  US13/609,830
• Publication Number:
  US 20130331113A1
• Time in Patent Office: 2,156 Days
• Field of Search: 4554561, 4554562, 4554563, 4554566
• CPC Class Codes: G01S 5/0242 Determining the position of transmitters to be subsequently used in positioning G01S5/0289 takes precedence
• CPC Class Codes: H04W 24/02 Arrangements for optimising operational condition
• CPC Class Codes: H04W 24/10 Scheduling measurement reports ; Arrangements for measurement reports

Abstract

Embodiments of a system and method for tile-based reduction of access point location information are described. Embodiments may reduce a set of network access points and respective locations to generate a reduced set. For instance, embodiments may include parsing a representation of a geographic region into multiple tiles. Embodiments may also include, for each sub-area or “bucket” of multiple buckets that make up a given tile, evaluating the set of network access points and respective locations to identify network access points residing in that bucket, and based on a ranking of the network access points in that bucket, eliminating at least some network access points of that sub-area from the reduced set. Embodiments may also include, for each sub-tile of multiple sub-tiles of the given tile, assigning within the reduced set a common location to multiple access points residing within different locations of that sub-tile.

Claims

1. A method comprising:

receiving network access point information for a plurality of network access points located in a region, wherein the network access point information comprises location information for each network access point of the plurality of network access points;

parsing the region into multiple tiles and for at least one of the multiple tiles into a plurality of sub-tiles;

assigning respective sub-sets of the network access points to respective buckets, wherein each of the respective buckets corresponds to one or more sub-tiles of a respective one of the multiple tiles;

decimating at least a portion of the network access point information assigned to the respective buckets, wherein decimating the at least a portion of the network access point information comprises;

for each bucket;

ranking the network access points assigned to that bucket, and

eliminating network access point information for some network access points assigned to that bucket, based at least in part on the ranking, to generate reduced network access point information for that bucket; and

quantizing the reduced network access point information for each bucket, wherein quantizing the reduced network access point information comprises;

designating a common location for a sub-tile corresponding to a respective bucket;

reassigning multiple network access points residing within different locations of the sub-tile to the common location; and

further reducing the reduced network access point information for the respective bucket by including the common location for the multiple network access points instead of different location information for the multiple network access points.

2. The method of claim 1, wherein the method comprises, subsequent to decimating at least some access point information from the respective buckets and quantitating access point information of the respective buckets, evaluating the access point information of the respective buckets to determine a location of an access point having a specific identifier.

3. The method of claim 1, wherein

said reassigning comprises reassigning all access points that corresponds with the sub-tile to the common location.

4. The method of claim 1, wherein network access points that are accessed by client devices more frequently are ranked higher than network access points that are accessed by client devices less frequently.

5. The method of claim 1, wherein the method comprises generating multiple files each associated with different tiles of said multiple tiles, wherein each file comprises an index for locating location information for specific network access points within the file.

6. The method of claim 1, wherein one or more of the network access points are Wi-Fi access points.

7. A mobile device, comprising:

a memory; and

one or more processors coupled to the memory, wherein the memory comprises program instructions executable by the one or more processors to implement a location component configured to;

detect a plurality of network access points including at least a first network access point in a first geographic location and a second network access point in a second geographic location;

generate a request for one or more tiles including access point information specifying geographic locations of the detected network access points;

receive information specifying the one or more tiles, wherein access point information for the one or more tiles has been reduced via decimation and further reduced via quantization, wherein the quantized access point information for the one or more tiles includes a common location for multiple network access points instead of different location information for the multiple network access points; and

utilize the first detected network access point or the second detected network access point and the access point information of the one or more tiles to determine a geographic location of the mobile device

wherein the location component determines a same geographic location of the mobile device when either the first detected network access point or the second detected network access point is utilized to determine the geographic location of the mobile device, wherein the first network access point and the second network access point are physically located in different geographic locations.

8. The mobile device of claim 7, wherein the information specifying the one or more tiles includes one or more tile files, wherein the location component is configured to generate a database of tiles within the memory based on the files.

9. The mobile device of claim 8, wherein the location component is configured to locate within the generated database an entry for the first or second detected network access point.

10. The mobile device of claim 7, wherein the location component is configured to generate the request in response to determining that a tile containing location information for the first or second detected network access point does not already reside within said memory.

11. A system, comprising:

one or more memories; and

one or more processors coupled to the one or more memories, wherein the one or more memories comprise program instructions executable by the one or more processors to implement a tile generator configured to reduce information describing a set of network access points and respective locations to generate a reduced information set, wherein the access points are located in a region, wherein to perform the reduction the tile generator is configured to;

parse the region into multiple tiles and for at least one of the multiple tiles into a plurality of sub-tiles;

assign respective sub-sets of the network access points to respective buckets, wherein each of the respective buckets corresponds to one or more sub-tiles of one of the multiple tiles; and

decimate at least a portion of the network access point information assigned to the respective buckets, wherein to decimate the at least a portion of the network access point information the tile generator is configured to;

for each bucket;

based on a ranking of the network access points in that bucket, eliminate network access point information for some network access points assigned to that bucket to generate the reduced network access point information for that bucket; and

store the reduced network access point information for that bucket; and

quantize the reduced network access point information for the respective buckets, wherein to quantize the reduced network access point information the tile generator is configured to;

designate a common location for a sub-tile corresponding to a respective bucket;

reassign multiple network access points residing within different locations of the sub-tile to the common location; and

further reduce the reduced network access point information for the respective bucket by including the common location for the multiple network access points instead of different location information for the multiple network access points.

12. The system of claim 11, wherein the tile generator is configured to generate a file for each tile, wherein each file comprises an index for expedited searching of multiple location entries for network access points.

13. The system of claim 11, wherein network access points that are accessed by client devices more frequently are ranked higher than network access points that are accessed by client devices less frequently.

14. The system of claim 13, wherein the tile generator is configured to generate said ranking based on historical access point location information received from multiple client devices.

15. A method, comprising:

detecting, by a mobile device, an identifier of a first network access point in a first geographic location and an identifier of a second network access point in a second geographic location;

generating a request for one or more tiles including information specifying the identifier of the first network access point and a corresponding geographic location and the identifier of the second network access point and a corresponding geographic location;

receiving information specifying the one or more tiles, wherein access point information for the one or more tiles has been reduced via decimation and further reduced via quantization, wherein the quantized access point information for the one or more tiles includes a common location for multiple network access points instead of different location information for the multiple network access points; and

utilizing the first detected network access point identifier or the second detected network access point identifier and the access point information of the one or more tiles to determine a geographic location of the mobile device,

wherein a same geographic location of the mobile device is determined when either the first detected network access point or the second detected network access point is utilized to determine the geographic location of the mobile device, wherein the first network access point and the second network access point are physically located in different geographic locations.

16. The method of claim 15, wherein the method comprises storing the one or more tiles in a local cache.

17. The method of claim 15, wherein the method comprises:

detecting an identifier of an additional network access point; and

in response to determining that an entry for the additional network access point is not in the cache, generating a request to obtain a tile comprising location information for the additional network access point.

18. The method of claim 15, wherein the method comprises:

detecting an identifier of an additional network access point; and

in response to determining that the cache contains a location entry for the additional network access point, determine the location of the additional network access point based on that location entry.

19. The method of claim 15, wherein the information specifying the one or more tiles includes an index into a list of location entries for multiple access points, wherein the method further comprises evaluating the index to locate a sub-portion of the list that contains an entry for the first network access point.

20. A non-transitory computer-readable storage medium, storing program instructions computer-executable on a computer to implement a tile generator configured to generate a reduced information set, wherein to perform the reduction the tile generator is configured to:

receive network access point information for a plurality of network access points located in a region, wherein the network access point information comprises location information for each network access point of the plurality of network access points;

parse the region into multiple tiles and for at least one of the multiple tiles into a plurality of sub-tiles;

assign respective sub-sets of the network access points to respective buckets, wherein each of the respective buckets corresponds to one or more sub-tiles of one of the multiple tiles;

decimate at least a portion of the network access point information assigned to the respective buckets, wherein to decimate the at least a portion of the network access point information the tile generator is configured to;

for each bucket;

based on a ranking of the network access points assigned to that bucket, eliminate network access point information for some network access points assigned to that bucket to generate the reduced network access point information for that bucket; and

quantize the reduced network access point information for the respective buckets, wherein to quantize the reduced network access point information the tile generator is configured to;

for each bucket;

designate a common location for a sub-tile corresponding to that bucket;

reassign multiple network access points residing within different locations of the sub-tile to the common location; and

further reduce the reduced network access point information for that bucket by including the common location for the multiple network access points instead of different location information for the multiple network access points in the further reduced network access point information for that bucket.

21. The non-transitory medium of claim 20, wherein the tile generator is configured to generate a file for each tile, wherein each file comprises an index for expedited searching of multiple location entries for network access points.

22. The non-transitory medium of claim 20, wherein network access points that are accessed by client devices more frequently are ranked higher than network access points that are accessed by client devices less frequently.

23. The non-transitory medium of claim 22, wherein the tile generator is configured to generate said ranking based on historical access point location information received from multiple client devices.