Systems and methods for cross-street identification

• US 8,176,045 B2
• Filed: 03/27/2009
• Issued: 05/08/2012
• Est. Priority Date: 03/27/2009
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Hulubei, Tudor
• Primary Examiner(s): Breene, John E
• Assistant Examiner(s): PHILLIPS, III, ALBERT M
• Application Number:
  US12/412,458
• Publication Number:
  US 20100250619A1
• Time in Patent Office: 1,138 Days
• Field of Search: 707/920, 707/919, 707/724
• US Class Current: 707/724
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/92 Navigation

Abstract

Aspects of the invention relate to the use of electronic maps and providing information about intersecting streets. A given region of interest on a map may include any number of features. Features of interest, including road segments and intersections, can be filtered to remove non-street data. The results may be analyzed according to individual street segments. Each segment may be identified by a feature ID, and the relationship each segment has with a given intersection is analyzed. Thus, the direction of a segment into or out of an intersection is determined, along with the physical locations of the beginning and end of the segment. This information is used to provide robust map information that may be displayed to a user. Heuristics can be applied to the map information to provide coherent address or direction information to the user for a given point of interest.

Claims

1. A method, comprising:

identifying a plurality of streets and at least one intersection thereof, the plurality of streets and the at least one intersection being associated with a region of interest of a map, each of the plurality of streets including at least one road segment;

extracting features from a map database for each road segment and the at least one intersection;

creating, for each intersection of interest, a set of road segments connected to that intersection and a relationship of each road segment in the set to that intersection, including whether a given road segment begins or ends at the intersection;

storing the set of road segments and their relationships to the intersection of interest in a cross-street database;

identifying all cross-streets of the intersection of interest by road segment IDs, each cross street comprising at least one of the road segments;

retrieving original features of interest from the map database;

filtering non-road segments from the original features of interest to obtain a set of filtered road segments;

matching each cross-street of the intersection of interest with the filtered road segments; and

storing the matched cross-streets in the cross-street database.

2. The method of claim 1, wherein retrieving the original features, filtering the non-road segments and matching each cross-street are done by road segment ID.

3. The method of claim 1, further comprising:

retrieving selected matched cross-streets from the cross-street database in response to a user query;

applying a heuristic to the retrieved cross-streets to select a display option; and

displaying a geographical map on a display to identify cross-street information based upon the display option.

4. The method of claim 3, wherein the display option reports the cross-street information in increasing order of street numbers.

5. The method of claim 3, wherein the display option reports the cross-street information without mixing cardinal directions if alternative cross-streets that are on the same cardinal direction exist.

6. The method of claim 3, further comprising determining a distance between a point of interest on the geographical map and endpoints of the cross-street on which the point of interest is located.

7. The method of claim 6, wherein the display option reports a location of the point of interest in relation to the cross-street on which the point of interest is located.

8. A processing system for processing geographical map information, comprising:

at least one processor; and

memory for storing data, the memory being electrically coupled to the at least one processor;

wherein the at least one processor is configured to identify a plurality of streets and at least one intersection thereof, the plurality of streets and the at least one intersection being associated with a region of interest of a map, each of the plurality of streets including at least one road segment, to extract features from a map database for each road segment and the at least one intersection, to create, for each intersection of interest, a set of road segments connected to that intersection and a relationship of each road segment in the set to that intersection, including whether a given road segment begins or ends at the intersection, and to store the set of road segments and their relationships to the intersection of interest in a cross-street database in the memory; and

wherein the at least one processor is further configured to identify all cross-streets of the intersection of interest by road segment IDs, each cross street comprising at least one of the road segments, to retrieve original features of interest from the map database, to filter non-road segments from the original features of interest to obtain a set of filtered road segments, to match each cross-street of the intersection of interest with the filtered road segments, and to store the matched cross-streets in the cross-street database.

9. A computer-readable recording medium having instructions stored thereon, the instructions, when executed by a processor, cause the processor to perform the operations of:

identifying a plurality of streets and at least one intersection thereof, the plurality of streets and the at least one intersection being associated with a region of interest of a map, each of the plurality of streets including at least one road segment;

extracting features from a map database for each road segment and the at least one intersection;

creating, for each intersection of interest, a set of road segments connected to that intersection and a relationship of each road segment in the set to that intersection, including whether a given road segment begins or ends at the intersection;

storing the set of road segments and their relationships to the intersection of interest in a cross-street database;

identifying all cross-streets of the intersection of interest by road segment IDs, each cross street comprising at least one of the road segments;

retrieving original features of interest from the map database;

filtering non-road segments from the original features of interest to obtain a set of filtered road segments;

matching each cross-street of the intersection of interest with the filtered road segments; and

storing the matched cross-streets in the cross-street database.