Geocoding locations near a specified city

• US 20050171691A1
• Filed: 12/20/2004
• Published: 08/04/2005
• Est. Priority Date: 12/19/2003
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Decarta (Uber Technologies, Inc.)
• Inventors: Dunn, Linnea A., Smartt, Brian E., Poppen, Richard F.
• Granted Patent: US 7,813,873 B2
• Time in Patent Office: Days
• US Class Current: 701/208
• CPC Class Codes: G01C 21/3605 Destination input or retrieval
• CPC Class Codes: G06F 16/2468 Fuzzy queries
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

Specified streets or intersections that are within a specified distance of a specified city can be found by a search, even when they are not actually in that city. For computational efficiency, some addresses are included in search results even when they exceed the specified distance from the specified city by a small amount (“false positives”). The search method guarantees that no instance of the street name within the specified distance of the specified city is erroneously missed (“false negatives”).

Claims

1. A method for locating a geographic object, the method comprising:

receiving an address of a geographic object to be located, the address including at least one known address component and at least one additional address component;

receiving a buffer distance;

determining a set of geographic objects, each object in the set having the known address component and a second address component, wherein a distance from the second address component to the additional address component does not exceed the buffer distance by more than a threshold amount.

2. The method of claim 1 wherein the known address component is a street address.

3. The method of claim 2 wherein the additional address component is a city.

4. The method of claim 1 wherein the known address component is an intersection of two streets.

5. The method of claim 4 wherein the additional address component is a city.

6. The method of claim 1 wherein the threshold amount is equal to the buffer distance.

7. A method for locating a geographic object, the method comprising:

receiving an address of a geographic object to be located, the address including at least one known address component and at least one additional address component;

receiving a buffer distance;

determining a set of geographic objects, each object in the set having the known address component and a second address component, wherein a distance from the second address component to the additional address component is at most the buffer distance.

8. The method of claim 7 wherein the known address component is a street address.

9. The method of claim 8 wherein the additional address component is a city.

10. The method of claim 7 wherein the known address component is an intersection of two streets.

11. The method of claim 10 wherein the additional address component is a city.

12. A system for locating a geographic object, the system comprising:

a map file, the map file including a plurality of data records, each data record including a location of at least one geographic object;

a geocoding engine, coupled to the map file, for locating a specified geographic object, the specified geographic object having an address including at least one known address component and at least one additional address component by;

determining a set of geographic objects located in data records of the map file, each object in the set having the known address component and a second address component, wherein a distance from the second address component to the additional address component is at most a specified buffer distance.

13. The system of claim 12 wherein the known address component is a street address.

14. The system of claim 13 wherein the additional address component is a city.

15. The system of claim 12 wherein the known address component is an intersection of two streets.

16. The system of claim 15 wherein the additional address component is a city.

17. A computer program product for locating a geographic object, the computer program product stored on a computer-readable medium and induding program code for causing a processor to execute the steps of:

receiving an address of a geographic object to be located, the address induding at least one known address component and at least one additional address component;

receiving a buffer distance;

determining a set of geographic objects, each object in the set having the known address component and a second address component, wherein a distance from the second address component to the additional address component is at most the buffer distance.

18. The computer program product of claim 17 wherein the known address component is a street address.

19. The computer program product of claim 18 wherein the additional address component is a city.

20. The computer program product of claim 17 wherein the known address component is an intersection of two streets.

21. The computer program product of claim 20 wherein the additional address component is a city.

22. The computer program product of claim 17 wherein the threshold amount is equal to the buffer distance.

23. A method for locating a geographic object, the geographic object located in a city and having an address including a street number and a street, the method comprising:

receiving an address of a geographic object, the received address including a specified street number, street and city;

receiving a buffer distance;

determining a first list of keys, each key in the list having a geographic footprint that includes the specified city;

determining a second list of keys, each key in the second list having a geographic footprint that includes a point located within the buffer distance of the geographic footprint of at least one key in the first list;

determining a third list of keys, each key in the third list associated with an instance in a map file of the specified street and street number;

determining a fourth list of keys, wherein each key in the fourth list is also in the third list and either the first or second list; and

returning the fourth list of keys.

24. A method for locating a geographic object, the geographic object located in a city and having an address including a street number and a street, the method comprising:

receiving an address of a geographic object, the received address including a specified street number, street and city;

receiving a buffer distance;

determining a first list of keys, each key in the list having a geographic footprint that includes the specified city and associated with at least one data record in a map file;

determining a second list of keys, each key in the second list having a geographic footprint that includes a point located within the buffer distance of the geographic footprint of at least one key in the first list, and each key associated with at least one data record in the map file;

determining a third list of keys, each key in the third list associated with at least one data record in the map file having an instance of the specified street and street number;

determining a fourth list of keys, wherein each key in the fourth list is also in the third list and either the first or second list; and

returning the data records associated with the keys in the fourth list of keys.