SYSTEM AND METHOD FOR TILE-BASED REDUCTION OF ACCESS POINT LOCATION INFORMATION

• US 20130331113A1
• Filed: 09/11/2012
• Published: 12/12/2013
• Est. Priority Date: 06/08/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Andrew Konstantinov
• Inventors: Grosman, Yefim, Mayor, Robert W., Huang, Ronald K., Konstantinov, Andrew
• Granted Patent: US 10,042,035 B2
• Time in Patent Office: Days
• US Class Current: 455/452.1
• 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 for reducing a set of network access points and respective locations to generate a reduced set, the access points being located in a region, the method comprising:

parsing the region into multiple tiles;

for each sub-area of multiple sub-areas of a given tile;

evaluating the set of network access points and respective locations to identify network access points residing in that sub-area; and

based on a ranking of the network access points in that sub-area, eliminating at least some network access points of that sub-area from the reduced set; and

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.

2. The method of claim 1, wherein the method comprises, subsequent to elimination of at least some access points from the set and assigning common locations to access points of the set based on sub-tile location, evaluating the set of access points to determine a location of an access point having a specific identifier.

3. The method of claim 1, wherein the method comprises, for each sub-tile:

generating a geographic location for that sub-tile; and

assigning that geographic location to all access points residing in that sub-tile such that all of the access points residing in that sub-tile are designated as having a common location.

4. The method of claim 1, wherein within said ranking 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 entries 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 system, 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 an identifier of a particular network access point;

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

receive information specifying the one or more tiles, wherein each tile specifies multiple sub-tiles and, for at least one sub-tile, multiple network access points designated as having a common geographic location; and

evaluate the one or more tiles to identify a location of the particular network access point.

8. The system 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 system of claim 8, wherein to identify the location of the particular network access point, the location component is configured to locate within the generated database an entry for the particular network access point.

10. The system 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 particular 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 a set of network access points and respective locations to generate a reduced 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 each sub-area of multiple sub-areas of a given tile;

evaluate the set of network access points and respective locations to identify network access points residing in that sub-area; and

based on a ranking of the network access points in that sub-area, eliminating at least some network access points of that sub-area from the reduced set.

12. The system of claim 11, wherein to perform the reduction the tile generator is further configured to:

for each sub-tile of multiple sub-tiles of the given tile, assign within the reduced set a common location to multiple access points residing within different locations of that sub-tile.

13. 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.

14. The system of claim 11, wherein within said ranking 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.

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

16. A method, comprising:

detecting an identifier of a particular network access point;

generating a request for one or more tiles specifying geographic locations of access points including the particular network access point;

receiving information specifying the one or more tiles, wherein each tile specifies multiple sub-tiles and, for at least one sub-tile, multiple network access points designated as having a common geographic location; and

evaluating the one or more tiles to identify a location of the particular network access point.

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

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

detecting an identifier of a second network access point; and

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

19. The method of claim 16, wherein the method comprises:

detecting an identifier of a second network access point; and

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

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

21. A computer-readable storage medium, storing program instructions computer-executable on a computer to implement a tile generator configured to generate a reduced 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 each sub-area of multiple sub-areas of a given tile;

evaluate the set of network access points and respective locations to identify network access points residing in that sub-area; and

based on a ranking of the network access points in that sub-area, eliminating at least some network access points of that sub-area from the reduced set.

22. The medium of claim 21, wherein to perform the reduction the tile generator is further configured to:

for each sub-tile of multiple sub-tiles of the given tile, assign within the reduced set a common location to multiple access points residing within different locations of that sub-tile.

23. The medium of claim 21, 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.

24. The medium of claim 21, wherein within said ranking 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.

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