Reverse geocoder

• US 8,909,255 B1
• Filed: 02/20/2013
• Issued: 12/09/2014
• Est. Priority Date: 02/21/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Eriksson, Gran Ingemar, Ekwall, Nils Richard
• Primary Examiner(s): Arevalo, Joseph
• Application Number:
  US13/772,243
• Time in Patent Office: 657 Days
• Field of Search: 455/434, 455/435.1, 455/458, 455/448, 455/437, 455/150, 455/422.1, 455/552.1, 455/456.3, 455/456.5, 455/561, 455/562.1, 370/280, 370/281, 370/335, 370/331, 370/342
• US Class Current: 455/456.3
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

Aspect of the subject technology relate to a computer-implemented method for identifying geographic features related to a location lookup point. In some implementations, the method includes steps for receiving location information for a location look-up point, generating a plurality of search cells containing the location look-up point, wherein the plurality of search cells correspond with a respective plurality of hierarchical map cells and using the plurality of search cells to identify at least one geographic feature that is associated with at least one of the plurality of search cells. In certain aspects, the method can further include steps for providing at least one geographic feature to a user for display. Systems and computer-readable media for generating a geographic feature index are also provided.

Claims

1. A computer-implemented method for identifying geographic features related to a location lookup point, comprising:

receiving location information for a location look-up point;

generating a plurality of search cells containing the location look-up point, wherein the plurality of search cells correspond with a respective plurality of hierarchical map cells;

using the plurality of search cells to identify at least one geographic feature that is associated with at least one of the plurality of search cells;

scoring the at least one geographic feature based on an amount of area overlap between the at least one geographic feature and the at least one of the plurality of search cells, the score comprising a coverage score based on a search cell area and a covering fraction; and

providing the at least one geographic feature to a user for display based on the scoring of the at least one geographic feature.

2. The computer-implemented method of claim 1, wherein the at least one geographic feature has a geographic coverage area that includes the at least one of the plurality of search cells.

3. The computer-implemented method of claim 1, wherein each of the plurality of search cells covers a different amount of geographic area that includes the location look-up point.

4. The computer-implemented method of claim 1, further comprising:

using two or more search cells, corresponding with hierarchical map cells of different levels, to identify two or more political features that are related at different hierarchical levels.

5. A system for identifying geographic features related to a location look-up point, the system comprising:

one or more processors; and

a computer-readable medium comprising instructions stored therein, which when executed by the processors, cause the processors to perform operations comprising;

receiving location information for a location look-up point;

generating a plurality of search cells containing the location look-up point, wherein the plurality of search cells correspond with a respective plurality of hierarchical map cells;

using the plurality of search cells to identify at least one geographic feature that is associated with at least one of the plurality of search cells; and

scoring the at least one geographic feature based on an amount of area overlap between the at least one geographic feature and the at least one of the plurality of search cells, the score comprising a coverage score based on a search cell area and a covering fraction.

6. The system of claim 5, wherein scoring the at least one geographic feature further comprises:

identifying one or more geographic feature having a score above a predetermined threshold; and

providing the one or more geographic feature to a user.

7. The system of claim 5, wherein the at least one geographic feature has a geographic coverage area that includes the at least one of the plurality of search cells.

8. The system of claim 5, wherein each of the plurality of search cells covers a different amount of geographic area that includes the location look-up point.

9. The system of claim 5, further comprising:

using two or more search cells, corresponding with hierarchical map cells of different levels, to identify two or more political features that are related at different hierarchical levels.

10. A computer-implemented method for generating a geographic feature index, the method comprising:

receiving a plurality of geographic features each having a geographic coverage area;

determining, for each of the geographic features, one or more map cells that, when taken together, approximate the geographic coverage area of the geographic feature;

determining, for each of the cells, a list of one or more of the plurality of geographic features that include the map cell in its geographic coverage area; and

scoring each of the one or more of the plurality of geographic features in the list based on an amount of area overlap between the one or more of the plurality of geographic features and the map cell in its geographic coverage area, the score comprising a coverage score based on a search cell area and a covering fraction.

11. The computer-implemented method of claim 10, further comprising:

generating a first index associating each of the plurality of geographic features with the one or more map cells that approximate the geographic coverage area of the geographic feature.

12. The computer-implemented method of claim 10, further comprising:

generating a second index associating the one or more map cells with at least one of the geographic features in the list based on the score associated with the at least one of the plurality of geographic features.

13. The computer-implemented method of claim 12, further comprising

providing at least one of the plurality of geographic features to a user if the score of the at least one of the plurality of geographic features exceeds a predetermined threshold.

14. The computer-implemented method of claim 10, further comprising:

using two or more search cells, corresponding with hierarchical map cells of different levels, to identify two or more political features that are related at different hierarchical levels.

15. A system for generating a geographic feature index, the system comprising:

one or more processors; and

a computer-readable medium comprising instructions stored therein, which when executed by the processors, cause the processors to perform operations comprising;

receiving a plurality of geographic features each having a geographic coverage area;

determining, for each of the geographic features, one or more map cells that, when taken together, approximate the geographic coverage area of the geographic feature;

determining, for each of the cells, a list of one or more of the plurality of geographic features that include the map cell in its geographic coverage area; and

scoring each of the one or more of the plurality of geographic features in the list based on an amount of area overlap between the one or more of the plurality of geographic features and the map cell in its geographic coverage area, the score comprising a coverage score based on a search cell area and a covering fraction.

16. The system of claim 15, wherein the processors are further configured to perform operations comprising:

generating a first index associating each of the plurality of geographic features with the one or more map cells that approximate the geographic coverage area of the geographic feature.

17. The system of claim 15, wherein the processors are further configured to perform operations comprising:

generating a second index associating the one or more map cells with at least one of the geographic features in the list based on the score associated with the at least one of the plurality of geographic features.

18. The system of claim 17, wherein the processors are further configured to perform operations comprising:

providing at least one of the plurality of geographic features to a user if the score of the at least one of the plurality of geographic features exceeds a predetermined threshold.

19. The system of claim 15, wherein the processors are further configured to perform operations comprising:

using two or more search cells, corresponding with map cells of different hierarchical levels, to identify two or more political features that are related at different hierarchical levels.