Abstract:
The present invention is directed to a method for integrating road names recorded in a source data, particularly comprising steps of merging all interconnected segments having this road name into a user road group and merging these user road groups if they belongs to the same physical road entity. The present invention also relates to a method for integrating points of interest recorded in a source data, particularly comprising steps of, beginning from node with highest priority in the tree to the other nodes one at a time, finding nodes with same point of interest to redirect all child links of lower priority node to higher priority node among the same point of interest nodes and delete link between the same point of interest nodes; creating geometry relationship based on above new arrangement.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    The invention relates to a method for integrating database in navigation system, and more particularly, relates to a method for integrating road names and points of interest (place names) in navigation system. 
       DESCRIPTION OF RELATED ART 
       [0002]    In navigation system such as global positioning system (GPS), according to a map database of discrete data such as road segment and place name, it runs an algorithm for extracting the desired data conforming specific conditions. For example, each road segment has specific fields used for address searching, such as road name(s), zip code, and various level of points of interest (place names). The result shown to users is achieved by calculating and combining fields across the map database. The combination method is similar to following SQL grammer: 
         [0003]    Select VestalBlvd, a9, a2, a0, 10572(zipcode) from road segments, where road segments are arranged as a table for all road segments in the map database, and VestalBlvd, a 9 , a 2 , a0, 10572 are data fields attached to each segment. 
         [0004]    However, if the data fields of the map database are arranged improperly such as repetition, users will get confused after the above selection and combination algorithm. For example, when a new highway is built between an existing road segment, the road segment in the map database sometimes will become two road segments, and thus the result becomes two segments and is confused by users. As another example, if a point of interest in the map database has alias name, the repetition result can not be avoided. 
         [0005]    Therefore, a method for integrating road names and places name in the navigation system is desired. 
       SUMMARY OF THE INVENTION 
       [0006]    Accordingly, the present invention is directed to a method for integrating road names recorded in a source data, comprising the steps of: extracting unique road name; for each unique road name, merging all interconnected segments having this road name into a user road group, wherein, as a result, segments having this road name but not interconnected are grouped in a different user road group; merging these user road groups if they belongs to the same physical road entity based on unnamed segments, connectivity across junctions, complex junction, user road overlaps, distance. 
         [0007]    In another prospect, the present invention relates to a method for integrating point of interest recorded in a source data, comprising the steps of: extracting all points of interest and assigning priority to each point of interest; loading relationships among the points of interest from the source data and storing the relationship so that hierarchy tree is built and a node with higher priority is a parent of a node with lower priority if they are connected; beginning from node with highest priority in the tree to other nodes with lower priority one at a time, finding nodes with same point of interest to redirect all child links of lower priority node to higher priority node and delete parent link of the lower priority node; creating geometry based on new relationships. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0008]      FIG. 1  is a map showing disjoint roads with same road name; 
           [0009]      FIG. 2  is another example to show disjoint roads with same road name; 
           [0010]      FIG. 3  is a map to explain an example of to a method for integrating road names recorded in a source data of the present invention; 
           [0011]      FIG. 4  is a table structure to explain an example of to a method for integrating points of interest recorded in a source data of the present invention; 
           [0012]      FIG. 5   a  to  FIG. 5   c  are trees to explain an example of to a method for integrating points of interest recorded in a source data of the present invention; and 
           [0013]      FIG. 6  is a linking diagram showing an example of to a method for integrating road names recorded in a source data of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0014]    In the following description, like parts are marked with the same reference numerals throughout the specification and drawings. 
         [0015]    A method of the present invention are for integrating two fields attached to a road segment, including a road name and a point of interest in map database of navigation system. 
         [0016]    The method for integrating road names is firstly described as follows. 
         [0017]    A ‘road entity’ is defined as a collection of discrete digital map road segments sharing one road name. However, it happens but not unusual that a new highway  11 , as shown in  FIG. 1 , is introduced between an existing road segment  12 , and thus the road segment  12  is sliced into two disjoint sets (i.e.,  121  and  122 ) of road segment. In  FIG. 1 , it also shows situations that two disjoint road segments ( 131 ,  132 ) with the identical road name and three road segments ( 141 ,  142 ,  143 ) having the same road name due to road realignment. 
         [0018]    Each road segments has specific attributes attached to them such as house number information, road class (rural, highway etc), road elevation and most importantly the various names given to this road. 
         [0019]    The attributes are stored in a separated ‘geocoding” table. This table contains one row for each name that a segment is known by. Some segments however might not have any name information attached to them. These ‘unnamed’ segments do not contain any geocoding attributes and is known as ‘unnamed segments’. 
         [0020]    As shown in  FIG. 2 , it discloses 3 consecutive segments named ‘Will Way’ that should be part of the same road. And in some cases, the two road segments named ‘High St’ might be considered by a user to be the same road. The method for integrating road names is used to integrating the above. 
         [0021]    In an embodiment, the source data used is as following tables: 
         [0022]    GC (Geocode) Table: All names and alternate names for all segments; 
         [0023]    RN (Route Number) Table: Route number for all relevant segments; 
         [0024]    NW (Road Network &amp; Geometry) Table: Used to extract road geometry and junctions for each segment; 
         [0025]    2R (Level 2 Roads) Table: Used to extract road segment groups; 
         [0026]    IG (Intersection Index) Table: Use to extract complex intersection-segment memberships; 
         [0027]    TA (Transport Element Relationships) Table: Relationships between segments and areas; 
         [0028]    The method of the present invention for integrating road names/route number is explained as follows. 
         [0029]    Step 1: All unique road names and route numbers recorded in the source data are extracted. 
         [0030]    Step 2: Merging all interconnected segments having the same road name or route number one at a time. This is done by the following two stages. 
         [0031]    (Stage 1) All segments with one road name/route number are extracted as a new set. 
         [0032]    (Stage 2) Picking a random segment from this new set (made in stage 1) and finding all segments connected to this segment. Performing the same operating on all segments of this new set. This continues until no new segments are added. This set is then considered ‘one user road’. These segments are added to a segment table (SPG_USER_ROAD_SEG) and a new row is added to a user_road_table (SPG_USER_ROAD). These segments are then removed from the original set and the process continues. Once all segments have been exhausted, the next road/route name is processed. 
         [0033]    An example is explained as below by referring to Tables 1 to 4 and  FIG. 3 . 
         [0000]    
       
         
               
               
               
               
               
               
             
               
               
               
               
               
               
               
             
           
               
                 TABLE 1 
               
               
                   
               
               
                   
                 Road Name/ 
                 Connecting 
                 Area 
                   
                   
               
               
                 Segment 
                 Route No. 
                 Nodes 
                 No. 
                 Detailed 
                 Zipcode 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 1 
                 Vestal Blvd 
                 A 
                 B 
                 A9 
                 Skipped . . . 
                 10511 
               
               
                 2 
                 Federal Rd 
                 D 
                 I 
                 A9 
                   
                 10511 
               
               
                 3 
                 1 St 
                 E 
                 L 
                 A9 
                   
                 10511 
               
               
                 4 
                 Vestal Blvd 
                 B 
                 G 
                 A8 
                   
                 10513 
               
               
                 5 
                 Taylor Rd 
                 C 
                 D 
                 A9 
                   
                 10511 
               
               
                 6 
                 Federal Rd 
                 D 
                 H 
                 A8 
                   
                 10513 
               
               
                 7 
                 Grand Ave 
                 J 
                 L 
                 A8 
                   
                 10513 
               
               
                   
               
             
          
         
       
     
         [0000]    
       
         
               
               
             
           
               
                 TABLE 2 
               
               
                   
               
               
                 Vestal Blvd 
                 Connected Segments 
               
               
                   
               
             
             
               
                 S1 
                 S3, S4 
               
               
                 S4 
                 S1, S7 
               
               
                   
               
             
          
         
       
     
         [0000]    
       
         
               
               
             
           
               
                 TABLE 3 
               
               
                   
               
               
                 Federal Rd 
                 Connected Segments 
               
               
                   
               
             
             
               
                 S2 
                 S3, S5, S6 
               
               
                 S6 
                 S2, S7 
               
               
                   
               
             
          
         
       
     
         [0034]    In Table 1, there are 7 segments representing each road segment in the map of  FIG. 3 . Each segment is defined with fields of ‘Road Name/Route Number’, ‘Nodes’, ‘Area Number’, ‘zip code’ and the other detailed information such as unit numbers of houses. For example, Segment 2 is defined with ‘Federal Rd’, ‘Connecting Nodes of D and I’, ‘Area 9’, ‘Zipcode 10511’ and is marked displayed in  FIG. 3  with a dark line. 
         [0035]    The method of the present invention for integrating road names/route number according to the above example is as follows. 
         [0036]    Step (1) : All unique road names and route numbers recorded in the source data are extracted as shown in Table 1. 
         [0037]    Step (2): 5 new sets are extracted, where 2 sets are shown in Table 2 and Table 3, and the other 3 sets are all single segment set (not shown). 
         [0038]    We take Table 2 as an example. There are two segments with name of ‘Vestal Blvd’, which are S1 and S4. Firstly, S1 is fetched, and S3 and S4 are found as segments connected with S1. Secondly, S4 is fetched, and S1 and S7 are found as segments connected with S4. After further searching, there are not any segments with name of ‘Vestal Blvd’ connected with S1 or S4. Thenas in  FIG. 6 , the name of ‘Vestal Blvd’ is stored in one field of link table ‘SPG_USER_ROAD’ as a road entity. ‘S1’ and ‘S4’ are stored in fields of link table ‘SPG_USER_ROAD_SEG’ as segments with name of ‘Vestal Blvd’. The process for ‘Federal Rd’ is done in the same manner. 
         [0039]    In other words,at this step we only connect road segment if they are with the same named segment. 
         [0040]    Step (3) : At this step, we have a large set of user roads. Each is guaranteed to contain same named, interconnected segments. We now attempt to see if any of these user roads in fact belong to the same ‘physical’ road entity. We do this based on certain assumptions and understanding of the road network that a user road might be revisited after the initial trial. 
         [0041]    Stage 1: Merge based on unnamed segments. 
         [0042]    We check if any of the user roads (with the same name) are connected to each other through a series of unnamed segments. Currently, the length of this series is set to 1 but can be increased to any arbitrary number. 
         [0043]    Stage 2: Merge based on Level 2 Roads. 
         [0044]    Level 2 Roads (2R) table is defined for grouping road segments based on their connectivity across junctions. As shown in  FIG. 1 , we use this information to merge same named user roads ( 121 , 122 ) which share the same junction. 
         [0045]    Stage 3: Merge based on complex junction. 
         [0046]    The IG table contains groups of segments that make up what is known as ‘complex’ junction. There are usually junctions between dual carriageway and motorway in New Zealand and the Great Britain. As shown in  FIG. 1 , these entities can be used to merge disjoint similar named user roads ( 13 ) which are indirected connected through a complex junction (cj) and combines them into a single user road entity. 
         [0047]    Stage 4: Merge based on user road overlaps 
         [0048]    At this stage, we might still have many disjoint user roads with the same name. Some of these user roads ( 131 , 132 ) lie on top of larger user roads ( 13 ), as shown in  FIG. 1 . In other words, some user roads ( 131 , 132 ) are defined with the same user road name but is disjoint in a parallel direction with another larger user road ( 13 ). We first check for the shortest distance between these user roads ( 131 , 132 ). If this distance is less than 2 km, we join them together to form a single user road entity. 
         [0049]    Stage 5: Merge based on distance. 
         [0050]    In some cases, we might have two or more disconnected user roads that are very close together. These are quite common where a single road has been cut due to the introduction of a new highway/motorway. The stage attempts to combine these roads into a single user road based on the shortest distance between them In a preferred embodiment, they are combined if this distance is less than 500 meter. 
         [0051]    Secondly, the method for integrating points of interest is described as follows. 
         [0052]    Source data usually contains many different types of named areas in different data tables. Some of them closely represent the named area for a location and others represent historical names that are still in use. Moreover, source data providers sometimes supply area naming way. 
         [0053]    Thus, the integrated points of interest of the present invention help to solve the problems of repeated results and alias result. 
         [0054]    A point of interest hierarchy is created by extracting all available points of interest and place hierarchies from the data source. These are then processed and merged to create an interconnected graph of all places and alternate points of interest. 
         [0055]    The source data is extracted from the following table. 
         [0056]    [Places and Points of Interest]
       A0-A0 (Administrative Area) Tables
           Including alternate names from the AN table   
           0A06 (Index Area) Table   AP (Administrative Places) Table
           Including alternate names from the NP table   
           BU (Built-up Areas) Table
           Including alternate names from the BN table   
           SM (Settlement Names) Table
           Including alternate names from the SMNM table   
               
 
         [0066]    Relationships 
         [0067]    PP Table links 0A06 places into its own hierarchy as well as into the administrative area hierarchy (A0-A9) 
         [0068]    BA Table links the BU areas into the admin area hierarchy. 
         [0069]    The algorithm as follows utilizes the table structure as shown in  FIG. 4 . 
         [0070]    Step (1): All points of interest are loaded into a user place table (SPG_USER_PLACE) creating a unique user place for each distinctive point of interest. If a given place has multiple names then a separate user place entity is created for each of these. A specific ‘priority’ is given to each place entity base on its data source. This is done to allow ‘official’ name of places to be displayed (since it&#39;s is possible that a given place has more than one parent). 
         [0071]    In a preferred embodiment, the following order of priority is assigned. (Top of the list=highest priority) and thus emphasis is placed on using the Administrative Area hierarchy for official naming (and reverse geocoding) 
         [0072]    1. Administrative Areas 
         [0073]    2. Index Areas 
         [0074]    3. Administrative Places 
         [0075]    4. Built-up Areas 
         [0076]    If a given place does not have a parent Administrative Area, then the list is searched in the above order until a valid parents is found. 
         [0077]    Step (2): The settlement names table (SM and SMMN) contains settlement centers and alternate names for these centers. In the preferred embodiment, these names are used as alternate names for the settlements themselves, so no separate entity is created for a ‘settlement center’, wherein the SM Table links to AX, AP and BU tables. 
         [0078]    Step (3): Once all available points of interest have been loaded as user place entities, relationships between them are loaded from the corresponding source data. The relationships are stored in a separate ‘relationship’ table (SPG_USER_PLACE_REL) which simply consists of two entities and their relation to each other. In a preferred embodiment, the following relationships are extracted. 
         [0079]    A0-A9 tables contain explicit relationships between all administrative areas. 
         [0080]    AP table links all administrative places into the administrative areas. 
         [0081]    BA table links the Built-up areas into the administrative area hierarchy. 
         [0082]    PP table contains a ‘place within place’ relationship for the Index Areas. These are used link Areas to each other and to create links into the Administrative Area hierarchy. 
         [0083]    Step (4): At this stage, we have a complex tree which consists of multiple area hierarchies combined into one. This tree however will always have multiple place entities with the same name connected to each other. An example of this would be an Administrative area called ‘New York’ contained an Administrative Place called ‘New York’. Although both places should be at the same in the place hierarchy, they might be connected to each other through an unwanted ‘parent-child’ relationship. 
         [0084]    At this stage, we perform a merge to clean up the tree and to make points of interest more distinguishable. The aim of the merge is to combine duplicate items into single entities if and only if they can be perceived to the same place. 
         [0085]    The detailed stages in the step (4) are as follows. 
         [0086]    Stage 1: We start at the top of the place hierarchy and traverse downwards through the nodes of the tree. 
         [0087]    Stage 2: At each node, we get all of its child nodes and checks if they have the same name. If two or more children have the same name, then 
         [0088]    (1) Only the entity with the highest priority (as mentioned in the above) is kept; 
         [0089]    (2) The children of the remaining entities are linked to the chosen entity; and 
         [0090]    (3) The child-parent links for all other entities are deleted. 
         [0091]    Stage 3: Once the children have been merged, recursively traverse down each of the children. 
         [0092]    Stage 4: Once returned, checking if any of the children have the same name as the current parent. If they do, then 
         [0093]    (1) All the child nodes of this selected entity are connected to the parent; and 
         [0094]    (2) The parent-child link between the current parent and child is deleted. 
         [0095]    Please note that each time two or more places are merged, a new ‘similar’ relationship is created between the merged objects. This informs us that these user places are in fact the same object. 
         [0096]    Step (5): Creating geometry based relationships. This is the final stage of area processing and this creates new links between current entities based on their geometries. If a given area is completely within another area, we create a parent-child relationship between these two. 
         [0097]    An example of the method for integrating points of interest of the present invention is described as follows. 
         [0098]    However, in order to abbreviate the description, we assume the relationship of user places can be found in  FIG. 5 . Please refer to  FIG. 5  to understand the algorithm regarding step (4) and step (5) as follows. We also assume node C, node F and node K are in fact the same node. 
         [0099]    Step (4): 
         [0100]    Stage 1: Start at node A to traverse downwards through the nodes of the tree. 
         [0101]    Stage 2: At node A, we find all child nodes of node A, and the we find node C and node F have the same point of interest ( FIG. 5   a ). 
         [0102]    (1) node C which is with higher priority than the node F is kept, and node F is deleted ( FIG. 5   b ); 
         [0103]    (2) The child nodes of node F, which is nodes I and J, are redirected to node C ( FIG. 5   b ); 
         [0104]    (3) The parent link c of node F is deleted ( FIG. 5   b ). 
         [0105]    Stage 3: Once the node C has been merged, we recursively traverse down from node C; 
         [0106]    Stage 4: We check if any of the children of node C has the same name as node C. We find node K has the same name as node C, and thus 
         [0107]    (1) All the child nodes of node K, which is nodes M and N, are connected to node C; 
         [0108]    (2) The parent link g of node K is deleted. 
         [0109]    It should be understood by those skilled in the art that various modifications, combinations, sub-combinations and alternations may occur depending on design requirements and other factors insofar as they are within the scope of the appended claims or the equivalents thereof.