Geocoding locations near a specified city

• US 7,813,873 B2
• Filed: 12/20/2004
• Issued: 10/12/2010
• 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.
• Primary Examiner(s): Tran; Khoi
• Assistant Examiner(s): Peche; Jorge O
• Application Number:
  US11/018,566
• Publication Number:
  US 20050171691A1
• Time in Patent Office: 2,122 Days
• Field of Search: 701/200, 701/201, 701/202, 701/208, 701/209, 701/211, 701/214, 340/990, 340/995.1
• 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 identifying a location of a point of interest, the point of interest having an address, the address including at least a street component and a city component, the method comprising:

receiving, by a computer, an input address, the input address including an input street component and an input city component;

identifying an unbloated city key list, the unbloated city key list including a first set of geospatial keys, each key having a footprint, and each key including data associated with the input city;

determining a buffer distance;

determining a first geographic region defined by a union of the footprints of the keys in the unbloated city key list;

determining a second geographic region, the second geographic region defined by expanding the first geographic region to include all points within the determined buffer distance of the first geographic region;

identifying a bloated city key list, the bloated city key list including a second set of geospatial keys, each key having a footprint contained in or overlapping the second geographic region;

determining a street key list, the street key list including a set of geospatial keys including data associated with the input street;

determining an intersecting set of keys, each key in the intersecting set being a member of the bloated city key list and the street key list;

retrieving map data for each key in the intersecting set of keys;

determining a candidate set of points of interest, each point of interest in the candidate set having an address included in the footprint of at least one key in the intersecting set of keys; and

displaying indicia of at least one of the points of interest of the candidate set of points of interest.

2. The method of claim 1 wherein displaying the indicia of at least one of the points of interest includes displaying a location of the point of interest on a digital map.

3. The method of claim 1 wherein the input street component is an intersection of two streets.

4. The method of claim 1 wherein determining the candidate set of points of interest further comprises:

determining a distance to the input city from each point of interest in the candidate set; and

removing from the candidate set of points of interest each point of interest having a distance to the input city greater than the buffer distance.

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. The method of claim 1 wherein displaying indicia of at least one of the points of interest comprises displaying the indicia on a web page via a network.

8. 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 cause a processor to execute the steps of:

receiving an input address, the input address including an input street component and an input city component;

identifying an unbloated city key list, the unbloated city key list including a first set of geospatial keys, each key having a footprint, and each key including data associated with the input city;

determining a buffer distance;

determining a first geographic region defined by a union of the footprints of the keys in the unbloated city key list;

determining a second geographic region, the second geographic region defined by expanding the first geographic region to include all points within the determined buffer distance of the first geographic region;

identifying a bloated city key list, the bloated city key list including a second set of geospatial keys, each key having a footprint contained in or overlapping the second geographic region;

determining a street key list, the street key list including a set of geospatial keys including data associated with the input street;

determining an intersecting set of keys, each key in the intersecting set being a member of the bloated city key list and the street key list;

retrieving map data for each key in the intersecting set of keys;

determining a candidate set of points of interest, each point of interest in the candidate set having an address included in the footprint of at least one key in the intersecting set of keys; and

displaying indicia of at least one of the points of interest of the candidate set of points of interest.

9. The computer program product of claim 8 wherein displaying the indicia of at least one of the points of interest includes displaying a location of the point of interest on a digital map.

10. The computer program product of claim 8 wherein the input street component is an intersection of two streets.

11. The method of claim 8 wherein determining the candidate set of points of interest further comprises:

determining a distance to the input city from each point of interest in the candidate set; and

removing from the candidate set of points of interest each point of interest having a distance to the input city greater than the buffer distance.

12. The computer program product of claim 8 wherein the buffer distance is received in conjunction with the address of the geographic object to be located.

13. The computer program product of claim 8 wherein the buffer distance is determined according to a stored value.

14. The computer program product of claim 8 wherein displaying indicia of at least one of the points of interest comprises displaying the indicia on a web page via a network.