Geocoding Locations Near A Specified City

• US 20110004399A1
• Filed: 09/14/2010
• Published: 01/06/2011
• Est. Priority Date: 12/19/2003
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Uber Technologies, Inc.
• Inventors: Dunn, Linnea A., Smartt, Brian E., Poppen, Richard F.
• Granted Patent: US 9,453,739 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• 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 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 first 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.

2. The method of claim 1 wherein returning the fourth list of keys further comprises:

providing a set of addresses, each address having the specified street number and street and a city other than the specified city.

3. The method of claim 2 wherein providing the set of addresses comprises:

determining a first set of addresses, each address having the specified street number and street and a city other than the specified city;

determining a distance to the specified city from a location specified by each address;

providing a second set of addresses, each address in the second set of addresses also in the first set of addresses, and having a determined distance to the specified city of at most the buffer distance.

4. The method of claim 2 wherein at least one address in the set of addresses has a city located in a state other than a state in which the specified city is located.

5. The method of claim 1 wherein the buffer distance is received in conjunction with the address of the geographic object to be located.

6. The method of claim 1 wherein the buffer distance is determined according to a stored value.

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

receiving, by a computer, an address of a geographic object to be located, the address including at least a street address component and a first city address component representing a city;

determining a buffer distance;

determining, by the computer, a set of geographic objects, each object in the set having an address including the street address component and a second city address component representing a city, wherein a distance from each of the objects to the city represented by the first city address component does not exceed the buffer distance by more than a threshold amount; and

returning indicia of at least one of the set of geographic objects.

8. The method of claim 7 wherein the street address component is an intersection of two streets.

9. The method of claim 7 wherein the threshold amount is equal to the buffer distance.

10. The method of claim 7 wherein the first city and the second city are located in different states.

11. The method of claim 7 wherein the buffer distance is received in conjunction with the address of the geographic object to be located.

12. The method of claim 7 wherein the buffer distance is determined according to a stored value.

13. The method of claim 7 wherein the street address component includes a street number.

14. The method of claim 7 further comprising:

displaying at least one of the geographic objects in the set of geographic objects on a digital map.

15. 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 a street address component and a first city address component representing a city by;

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

16. The system of claim 15 wherein the geocoding engine is further adapted to display at least one of the geographic objects in the determined set.

17. The system of claim 16 wherein the displayed geographic objects are located on a digital map.

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

receiving a request for a location of a geographic object, the request including an address having at least a street address component and a first city address component representing a city;

receiving a buffer distance;

determining, by a computer, a set of geographic objects, each object in the set having the street address component and a second city address component, wherein a distance from the object to the city represented by the first city address component is at most the buffer distance; and

providing in response to the request indicia of at least one of the geographic objects in the set of geographic objects.

19. The method of claim 18 further comprising displaying indicia of at least one of the geographic objects in the determined set.

20. The method of claim 19 wherein the displayed geographic objects are located on a digital map.

21. The method of claim 18 further comprising:

displaying indicia of at least one of the geographic objects in the set of geographic objects on a digital map.

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

receiving an address of a geographic object to be located, the address including at least a street address component and a first city address component representing a city;

receiving a buffer distance;

determining a set of geographic objects, each object in the set having the street address component and a second city address component, wherein a distance from the object to the city represented by the first city address component is at most the buffer distance.

23. The computer program product of claim 22 wherein the program code is further configured to caused a processor to execute the step of:

displaying at least one of the geographic objects in the set of geographic objects on a digital map.

24. The computer program product of claim 22 wherein the program code further causes the processor to display at least one of the geographic objects in the determined set.

25. The computer program product of claim 24 wherein the displayed geographic objects are located on a digital map.

26. A computer program product having a non-transitory computer-readable storage medium having computer executable code for locating a geographic object, the code adapted to perform steps comprising:

receiving an address of a geographic object to be located, the address including a street address component and a first city address component representing a city;

receiving a buffer distance;

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

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

28. The computer program product of claim 26 wherein the program code is further configured to caused a processor to execute the step of:

displaying at least one of the geographic objects in the set of geographic objects on a digital map.

29. A method for displaying a location of a geographic object, the method comprising:

receiving, by a geocoding system, an address of a geographic object to be located, the address including at least a street address component and a first city address component representing a city;

determining a buffer distance;

determining a set of geographic objects, each object in the set having an address including the street address component and a second city address component representing a city, wherein a distance from the object to the city represented by the first city address component does not exceed the buffer distance by more than a threshold amount; and

displaying at least one of the geographic objects in the determined set.

30. The method of claim 29 wherein the displayed geographic objects are located on a digital map.

31. The method of claim 29 wherein the request is received through the world wide web, and the digital map is displayed to the requester via the world wide web.

32. The method of claim 29 wherein the threshold amount is equal to the buffer distance.

33. 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 first 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.

34. The method of claim 33 wherein returning the data records associated with the keys in the fourth list of keys further comprises:

providing a set of addresses, each address having the specified street number and street and a city other than the specified city.

35. The method of claim 34 wherein providing the set of addresses comprises:

determining a first set of addresses, each address having the specified street number and street and a city other than the specified city;

determining a distance to the specified city from a location specified by each address;

providing a second set of addresses, each address in the second set of addresses also in the first set of addresses, and having a determined distance to the specified city of at most the buffer distance.

36. The method of claim 33 further comprising displaying at least one of the returned data records.

37. The method of claim 36 wherein data from at least one of the returned data records is displayed on a digital map.

38. A computer program product having a non-transitory computer-readable storage medium having computer executable code for locating a geographic object, the code adapted to perform steps 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 first 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.

39. The computer program product of claim 38 wherein returning the fourth list of keys further comprises:

providing a set of addresses, each address having the specified street number and street and a city other than the specified city.

40. The computer program product of claim 39 further comprising displaying indicia of the provided set of addresses on a digital map.

41. The computer program product of claim 39 wherein providing the set of addresses comprises:

determining a first set of addresses, each address having the specified street number and street and a city other than the specified city;

determining a distance to the specified city from a location specified by each address;

providing a second set of addresses, each address in the second set of addresses also in the first set of addresses, and having a determined distance to the specified city of at most the buffer distance.

42. The computer program product of claim 39 wherein at least one address in the set of addresses has a city located in a state other than a state in which the specified city is located.