用于在导航应用中使用的方法和装置

1.一种用于在导航应用中使用的方法，包括：
提供或接收经更新的信息，先前信息和所述经更新的信息与地理地区相关联，其中所述先前信息和所述经更新的信息包括边缘标志信息，所述先前信息包括与能够用于连接至不同地理地区中的一个或多个链路的一个或多个链路有关的信息，并且所述经更新的信息至少包括所述先前信息以及与用于连接至所述不同地理地区中的一个或多个链路的一个或多个链路有关的新信息；
生成针对包括所述经更新的信息的所述地理地区的更新；以及
使得针对所述地理地区的所述更新被存储在导航数据库中。
2.根据权利要求1所述的方法，其中所述提供包括：
针对所述地理地区中能够用于连接至所述不同地理地区的一个或多个链路的每条链路计算排名；
针对所述每条链路确定所述计算的排名是否具有比针对所述链路先前计算的排名低的重要性；以及
如果是，则保持所述先前计算的排名作为所述链路的排名。
3.根据权利要求1所述的方法，包括将针对所述地理地区的所述经更新的信息与针对所述地理地区的地图信息相关联地进行存储。
4.根据权利要求1所述的方法，其中地理区域至少被划分为所述地理地区和所述不同地理地区，其中所述地理地区和所述不同地理地区彼此相邻，并且所述地理地区和所述不同地理地区中的每一个包括至少一个能够用于形成所述地理地区中的第一位置与所述不同地理地区中的第二位置之间的路线的相应链路。
5.根据权利要求1所述的方法，进一步包括：
在确定所述地理地区和所述不同地区之间或者所述地理地区中的第一位置和所述不同地区中的第二位置之间的路线时使用所述经更新的信息。
6.根据权利要求1所述的方法，其中所述新信息涉及与所述先前信息所涉及的链路不同的一个或多个链路和/或在所述先前信息所涉及的所述一个或多个链路已经发生变化的情况下所述先前信息所涉及的一个或多个链路。
7.根据权利要求1所述的方法，其中所述先前信息和所述经更新的信息包括指示所述链路是否是去往地区的相应分区的相应节点的期望路径的向量。
8.根据权利要求7所述的方法，其中所述先前信息包括先前向量并且所述经更新的信息包括更新向量，所述更新向量中的每个值与所述先前向量相同或者相对于所述先前向量变化为表示更高排名的值。
9.根据权利要求1所述的方法，其中所述先前信息和所述经更新的信息包括链路分级信息。
10.根据权利要求9所述的方法，其中所述经更新的信息处于第一链路级别并且所述先前信息被保持在所述第一链路级别。
11.根据权利要求1所述的方法，其中所述链路中的每个链路都具有与之相关联的链路等级。
12.根据权利要求1所述的方法，进一步包括：
向所述链路中的一个或多个链路应用成本函数；
其中所述成本函数取决于以下各项中的一项或多项：与所述链路相关联的长度、与所述链路相关联的速度、以及所述链路的一个或多个属性。
13.根据权利要求1至12中任一项所述的方法，进一步包括：
存储所述先前信息，在所述地区的更新地区信息已经被更新时对所述更新地区信息进行编译并且存储与所述编译相关联的第一信息，以及根据所述先前信息和所述第一信息提供所述经更新的信息。
14.根据权利要求13所述的方法，进一步包括：
关于所述先前信息和所述第一信息执行OR运算以提供所述经更新的信息。
15.根据权利要求13所述的方法，其中所述经更新的信息包括所述先前信息和所述第一信息。
16.一种用于在导航应用中使用的装置，包括至少一个处理器和包括计算机程序代码的至少一个存储器，所述至少一个存储器和所述计算机程序代码被配置为与所述至少一个处理器一起使得所述装置至少提供或接收经更新的信息，先前信息和所述经更新的信息与地理地区相关联，其中所述先前信息和所述经更新的信息包括边缘标志信息，所述先前信息包括与能够用于连接至不同地理地区中的一个或多个链路的一个或多个链路有关的信息，并且所述经更新的信息至少包括所述先前信息以及与用于连接至所述不同地理地区中的一个或多个链路的一个或多个链路有关的新信息；
生成针对包括所述经更新的信息的所述地理地区的更新；以及
使得针对所述地理地区的所述更新被存储在导航数据库中。
17.根据权利要求16所述的装置，其中所述至少一个存储器和所述计算机程序代码被配置为与所述至少一个处理器一起使得所述装置针对所述地理地区中能够用于连接至所述不同地理地区的一个或多个链路的每条链路计算排名、针对所述每条链路确定所述计算的排名是否具有比针对所述链路先前计算的排名低的重要性、并且如果是，则保持所述先前计算的排名作为所述链路的排名。
18.根据权利要求16所述的装置，其中所述至少一个存储器和所述计算机程序代码被配置为与所述至少一个处理器一起使得所述装置将针对所述地理区域的所述经更新的信息与针对所述地理区域的地图信息相关联地进行存储。

用于在导航应用中使用的方法和装置
技术领域
[0001] 一些实施例涉及一种特别地但并非排他地在导航应用中使用的方法和装置。一些实施例还可以涉及导航数据库。
背景技术
[0002] 许多设备都能够提供导航功能。作为示例，这些设备可以是用于该用途的专用设备。这些专用设备可以是便携式的或者可以例如整合在车辆之中。导航设备还可以被提供在诸如移动电话之类的用户设备之中。
[0003] 这些设备需要访问导航数据库。该导航数据库可以被包括在该设备自身之中。可替换地，该数据库可以在该导航设备与之进行通信的服务器中被提供。在后者的情况下，与该数据库的通信例如可以经由无线电接口和/或核心网络来进行。
[0004] 这样的导航数据库可能需要进行更新，以便例如考虑提供新的道路或者针对已有道路的变更。这样的数据库被用来计算起点和终点之间的适当路线。
[0005] NDS(导航数据标准)是开发用于导航系统中的地图的标准化物理存储格式(PSF)的经注册的机构。目前，有多种不同的更新媒体和数种更新机制可被用于车载系统或移动客户端。NDS可以为不同系统提供与之协调的格式并且提供有关地图合成和地图更新的灵活性。
发明内容
[0006] 根据一个方面，提供了一种方法，包括：提供或接收经更新的信息，先前信息和所述经更新的信息与地理地区相关联，所述先前信息包括与能够用于连接至不同地理地区中的一个或多个链路(link)的一个或多个链路有关的信息，并且所述经更新的信息至少包括所述先前信息以及与用于连接至所述不同地理地区中的一个或多个链路的一个或多个链路相关的新信息。
[0007] 所述提供可以包括针对所述地理地区中能够用于连接至所述不同地理地区的一个或多个链路的每条链路计算排名(rank)、针对所述每条链路确定所述计算的排名是否具有比针对所述链路先前计算的排名更低的重要性、并且如果是，则保持所述先前计算的排名作为所述链路的排名。
[0008] 所述方法可以包括将针对所述地理地区的所述经更新的信息与针对所述地理地区的地图信息相关联地进行存储。
[0009] 地理区域可以至少被划分为所述地理地区和所述不同地理地区，其中所述地理地区和所述不同地理地区彼此相邻，并且所述地理地区和所述不同地理地区中的每一个包括至少一个能够用于形成所述地理地区中的第一位置与所述不同地理地区中的第二位置之间的路线的相应链路。
[0010] 所述方法可以包括在确定所述地理地区和所述不同地理地区之间或者所述地理地区中的第一位置和所述不同地区中的第二位置之间的路线时使用所述经更新的信息。
[0011] 所述新信息可以涉及与所述先前信息所涉及的链路不同的一个或多个链路和/或在所述先前信息所涉及的所述一个或多个链路已经发生变化的情况下所述先前信息所涉及的一个或多个链路。
[0012] 所述先前信息和经更新的信息可以包括边缘标志信息。
[0013] 所述先前信息和所述经更新的信息可以包括指示所述链路是否是去往地区的相应分区的相应节点的期望路径的向量。
[0014] 所述先前信息可以包括先前向量并且所述经更新的信息可以包括更新向量，所述更新向量中的每个值与所述先前向量相同或者相对于所述先前向量变化为表示更高排名的值。
[0015] 所述先前信息和所述经更新的信息可以包括链路分级信息。
[0016] 所述经更新的信息可以处于第一链路级别并且所述先前信息可以被保持在所述第一链路级别。
[0017] 所述链路中的每个链路都具有与之相关联的链路等级。
[0018] 所述方法可以包括向所述链路中的一个或多个应用成本函数。
[0019] 所述成本函数可以取决于以下各项中的一项或多项：与所述链路相关联的长度、与所述链路相关联的速度、以及所述链路的一个或多个属性。
[0020] 所述一个或多个属性可以包括隧道和桥梁中的一个或多个。
[0021] 所述方法可以包括存储所述先前信息，在更新地区信息已经被更新时对所述地区的更新地区信息进行编译并且存储与所述编译相关联的第一信息，并且根据所述先前信息和所述第一信息提供所述经更新的信息。
[0022] 所述方法可以包括关于所述先前信息和第一信息执行OR运算以提供所述经更新的信息。
[0023] 所述经更新的信息可以包括所述先前信息和所述第一信息。
[0024] 根据一个方面，提供了一种装置，包括用于提供或接收经更新的信息的装置，先前信息和所述经更新的信息与地理地区相关联，所述先前信息包括与能够用于连接至不同地理地区中的一个或多个链路的一个或多个链路有关的信息，并且所述经更新的信息至少包括所述先前信息以及与用于连接至所述不同地理地区中的一个或多个链路的一个或多个链路相关的新信息。
[0025] 所述用于提供的装置可以用于针对所述地理地区中能够用于连接至所述不同地理地区的一个或多个链路的每条链路计算排名、针对所述每条链路确定所述计算的排名是否具有比针对所述链路先前计算的排名更低的重要性、并且如果是，则保持所述先前计算的排名作为所述链路的排名。
[0026] 所述装置可以包括用于将针对所述地理地区的所述经更新的信息与针对所述地理地区的地图信息相关联地进行存储的装置。
[0027] 地理区域可以至少被划分为所述地理地区和所述不同地理地区，其中所述地理地区和所述不同地理地区彼此相邻，并且所述地理地区和所述不同地理地区中的每一个包括至少一个能够用于形成所述地理地区中的第一位置与所述不同地理地区中的第二位置之间的路线的相应链路。
[0028] 所述装置可以包括用于在确定所述地理地区和所述不同地理地区之间或者所述地理地区中的第一位置和所述不同地区中的第二位置之间的路线时使用所述经更新的信息的装置。
[0029] 所述新信息可以涉及与所述先前信息所涉及的链路不同的一个或多个链路和/或在所述先前信息所涉及的所述一个或多个链路已经发生变化的情况下所述先前信息所涉及的一个或多个链路。
[0030] 所述先前信息和经更新的信息可以包括边缘标志信息。
[0031] 所述先前信息和所述经更新的信息可以包括指示所述链路是否是去往地区的相应分区的相应节点的期望路径的向量。
[0032] 所述先前信息可以包括先前向量并且所述经更新的信息可以包括更新向量，所述更新向量中的每个值与所述先前向量相同或者相对于所述先前向量变化为表示更高排名的值。
[0033] 所述先前信息和所述经更新的信息可以包括链路分级信息。
[0034] 所述经更新的信息可以处于第一链路级别并且所述先前信息可以被保持在所述第一链路级别。
[0035] 所述链路中的每一个都可以具有与之相关联的链路等级。
[0036] 所述装置可以包括用于向所述链路中的一个或多个应用成本函数的装置。
[0037] 所述成本函数可以取决于以下各项中的一项或多项：与所述链路相关联的长度、与所述链路相关联的速度、以及所述链路的一个或多个属性。
[0038] 所述一个或多个属性可以包括隧道和桥梁中的一个或多个。
[0039] 所述装置可以包括用于存储所述先前信息的装置，用于在更新地区信息已经被更新时对所述地区的更新地区信息进行编译的装置，用于存储与所述编译相关联的第一信息，以及用于根据所述先前信息和所述第一信息提供所述经更新的信息的装置。
[0040] 所述装置可以包括用于关于所述先前信息和第一信息执行OR运算以提供所述经更新的信息的装置。
[0041] 所述经更新的信息可以包括所述先前信息和所述第一信息。
[0042] 根据一个方面，提供了一种装置，包括：至少一个处理器和至少一个包括计算机程序代码的存储器，所述至少一个存储器和计算机程序代码被配置为与所述至少一个处理器一起使得所述装置至少提供或接收经更新的信息，先前信息和所述经更新的信息与地理地区相关联，所述先前信息包括与能够用于连接至不同地理地区中的一个或多个链路的一个或多个链路有关的信息，并且所述经更新的信息至少包括所述先前信息以及与用于连接至所述不同地理地区中的一个或多个链路的一个或多个链路相关的新信息。
[0043] 所述至少一个存储器和计算机程序代码可以被配置为与所述至少一个处理器一起使得所述装置针对所述地理地区中能够用于连接至所述不同地理地区的一个或多个链路的每条链路计算排名、针对所述每条链路确定所述计算的排名是否具有比针对所述链路先前计算的排名更低的重要性、并且如果是，则保持所述先前计算的排名作为所述链路的排名。
[0044] 所述至少一个存储器和计算机程序代码可以被配置为与所述至少一个处理器一起使得所述装置将针对所述地理地区的所述经更新的信息与针对所述地理地区的地图信息相关联地进行存储。
[0045] 地理区域可以至少被划分为所述地理地区和所述不同地理地区，其中所述地理地区和所述不同地理地区彼此相邻，并且所述地理地区和所述不同地理地区中的每一个包括至少一个能够用于形成所述地理地区中的第一位置与所述不同地理地区中的第二位置之间的路线的相应链路。
[0046] 所述至少一个存储器和所述计算机程序代码可以被配置为与所述至少一个处理器一起使得所述装置在确定所述地理地区和所述不同地理地区之间或者所述地理地区中的第一位置和所述不同地区中的第二位置之间的路线时使用所述经更新的信息。
[0047] 所述新信息可以涉及与所述先前信息所涉及的链路不同的一个或多个链路和/或在所述先前信息所涉及的所述一个或多个链路已经发生变化的情况下所述先前信息所涉及的一个或多个链路。
[0048] 所述先前信息和经更新的信息可以包括边缘标志信息。
[0049] 所述先前信息和所述经更新的信息可以包括指示所述链路是否是去往地区的相应分区的相应节点的期望路径的向量。
[0050] 所述先前信息可以包括先前向量并且所述经更新的信息可以包括更新向量，所述更新向量中的每个值与所述先前向量相同或者相对于所述先前向量变化为表示更高排名的值。
[0051] 所述先前信息和所述经更新的信息可以包括链路分级信息。
[0052] 所述经更新的信息可以处于第一链路级别并且所述先前信息可以被保持在所述第一链路级别。
[0053] 所述链路中的每个链路都可以具有与之相关联的链路等级。
[0054] 所述至少一个存储器和计算机程序代码可以被配置为与所述至少一个处理器一起使得所述装置向所述链路中的一个或多个应用成本函数。
[0055] 所述成本函数可以取决于以下各项中的一项或多项：与所述链路相关联的长度、与所述链路相关联的速度、以及所述链路的一个或多个属性。
[0056] 所述一个或多个属性可以包括隧道和桥梁中的一个或多个。
[0057] 所述至少一个存储器和计算机程序代码可以被配置为与所述至少一个处理器一起使得所述装置存储所述先前信息、在更新地区信息已经被更新时对所述地区的更新地区信息进行编译并且存储与所述编译相关联的第一信息、并且根据所述先前信息和所述第一信息提供所述经更新的信息。
[0058] 所述至少一个存储器和计算机程序代码可以被配置为与所述至少一个处理器一起使得所述装置关于所述先前信息和第一信息执行OR运算以提供所述经更新的信息。
[0059] 所述经更新的信息可以包括所述先前信息和所述第一信息。
[0060] 以上方法中的任一个都可以由一种装置来执行。
[0061] 还可以提供一种计算机程序，其包括适于执行所述方法的程序代码装置。所述计算机程序可以被存储和/或以其它方式利用载体介质来体现。
[0062] 应当意识到的是，任何方面的任何特征都可以与其它方面的任何其它特征进行组合。
附图说明
[0063] 现在将仅作为示例对附图加以参考，其中：
[0064] 图1A至C示出了例如由NDS提供的更新地区概念；
[0065] 图2A至C示出了使用预先计算的边缘标志的方法；
[0066] 图3示出了使用分级链路的路线制定的方法；
[0067] 图4A至H图示了对具有预先计算的全局路线信息的更新地区进行更新所存在的问题；
[0068] 图5A至H图示了实施例；
[0069] 图6示出了可以在其中提供实施例的系统；
[0070] 图7示意性示出了一些实施例的装置；
[0071] 图8示出了使用预先计算的路线制定信息的方法的流程；以及
[0072] 图9示出了用于确定预先计算的路线制定信息的方法的流程。
具体实施方式
[0073] 为了支持特定地区的增量更新，数据库系统经常被划分为一般独立的地区。这些地区例如可以是一个国家或者该国家的一部分，或者具有一些地理意义。例如在NDS的环境中，这些地区可以被称作更新地区。这些地区可以彼此独立地进行更新。例如NDS中的地区的更新将在随后进行更为详细的描述。
[0074] 可能需要导航数据库支持长距离的路线制定。例如，根据数据库的应用，可能期望例如计算两个不同国家的两个城市之间的距离。这些国家可能是相邻的或者彼此被一个或多个其它国家所隔开。通常期望这样的长距离路线在相对短的时间段内、例如几秒钟量级的时间段内进行计算。一些导航数据库提供商为了应对该需求而可以将预先计算的信息包括在数据库之中。该预先计算的信息是基于完整数据库的而并没有考虑到独立的地区。这将在随后进行更为详细的描述。
[0075] 现在将参考图1A至1C对更新地区概念进行更为详细的描述。更新地区使得能够对导航数据库内所定义的地理地区进行增量和部分更新。更新地区可以表示数据库中能够被进行更新的地理区域。符合NDS标准的数据库可以在逻辑上被划分为并不相连但是可以在被定义的点处进行重叠的更新地区。这些被定义的点可以是连接更新地区的通道(gateway)。两个或更多更新地区可以仅在边界处进行重叠。NDS将地理区域划分为规则的分片区域(tiling area)。因此，更新地区边界通常并不与分片边界一致。就此而言，参考图
1A，其示意性示出了逻辑分片2。该逻辑分片覆盖了边界区域。特别地，该分片的一部分与第一地区4相关联并且该分片的另一部分与第二地区6相关联。这两个地区将被单独更新。因此，与边界重叠的诸如分片2的逻辑分片在物理上被存储在每个相交的更新地区之中。换句话说，分片2关于更新地区1被存储一次并且关于更新地区2被存储一次。图1B示出了关于更新地区1进行存储的分片，并且图1C示出了关于更新地区2进行存储的分片。如能够看到的，相应分片仅被填充有属于对应的更新地区的内容。换句话说，关于更新地区1进行存储的分片2将仅包含更新地区1的内容，而关于更新地区2进行存储的分片2将仅包含更新地区2的内容。
[0076] 两个不同更新地区之间的道路网络经由通道进行连接。这些通道可以被称作交叉通道。在两个更新地区中，边界的交叉点利用稳定的标识进行存储。这有时被称作“通道ID”。稳定的通道ID允许从一个更新地区向另一个更新地区制定路线。在图1A至C的上下文中，通道交叉点以附图标记8表示。
[0077] 现在参考图2A至C，它们示出了用于在导航数据库编译过程期间向导航数据库中提供预先计算的路线制定信息的第一技术。该信息可以被用来加速目标系统中的路线制定。图2A至C中所图示的方法是使用预先计算的边缘标志信息的技术。如图2A中所示，假设数据库被划分为带有编号或序号的分区。图2A示出了被划分为多个分区的地理区域。
[0078] 参考图2B，其示意性地示出了六个分区，其中每一个被编号为1至6。每条边缘被分配一个位向量，以便针对每个分区i指示该边缘是否处于从该边缘的起始节点到分区i内的任意节点的最优路径上。分区的网格数或编号将反映出该网格的空间位置。假设存在n个这样的分区。针对每条链路(或道路)，分配两个向量，其中的每个向量由n位组成。在第一位向量中，位置i处的“1”位指示该链路处于从该链路的基准节点开始去往分区i中的任意目的地的最优路线上。在第二位向量中，位置i处的“1”指示该链路处于从该链路的非基准点开始去往分区i中的任意目的地的最优路线上。已知目的地位于分区i中的路线制定算法仅需要探究针对其设置对应项目的那些链路。
[0079] 参考图2B，对于从第一节点14到第二节点10的链路，向量将为110110，这意味着该链路处于针对分区1、2、4和5中的目的地的最优路线上(在图2B的示例中有6个分区)。对于从第一节点14到第三节点12的链路，向量将为011001，这意味着该链路处于针对分区2、3和
6中的目的地的最优路线上。
[0080] 考虑图2C，提供了起点16并且在分区3中提供了目的地18。对于该行程而言，经由节点10的路线能够进行修剪，因为该向量在与分区3相关联的位置并没有“1”。换句话说，不存在经由节点10去往分区3的最优路线。诸如迪杰斯特拉(Dijkstra)或A*的图形算法可以被配置为使用该边缘信息。
[0081] 另一种用于加速路线制定的方法关于图3进行了图示并且其使用分级链路的集合。在NDS中，提供了多个不同的层。高级别的层可以仅包括更为重要的链路而较低级别的层则将包括更多链路。该结构是分级的，这意味着较低级别将包括前一层的所有链路以及一个或多个附加链路。最低级别通常将包含所有链路。
[0082] 为了对一个实施例进行说明，考虑其中使用五个不同层的示例。这五个不同层可以被称作级别13、10、8、6和4。应当意识到的是，所使用的层的数目在一些实施例中可以大于或小于5。可用层的数目可以大于或小于13。
[0083] 在该示例中，最为详细的层可以被认为处于级别13，其包含所有道路。例如处于级别10、8、6和4上的层因此可能仅包含重要的道路。级别4上的层可以仅包含最为重要的道路。
[0084] 一种得到这样的分层的方法是使用函数道路等级值。该值可以以人工方式、算法方式或者以任意其它适当方式进行指定。FRC值可以反映出道路的重要性。FRC值可以依据由当地机关定义的行政道路等级。在德国，FRC值1可以被分配给高速公路，2被分配给国道，等等。然而，这样的方法可能没有对于给定的成本函数提供最优路线。为了实现路线制定的优化，可能需要一种针对具体成本函数来计算分层的算法。针对链路l的成本函数c可以是c(L)＝length(L)或者c(L)＝length(L)*averageSpeed(L)等。该成本函数可以取决于链路的长度和/或该链路的速度类别，并且可选地可以考虑诸如隧道、桥梁等属性。
[0085] 在图3中，被分配至级别6的链路可以如下计算。图3所示的外部边界20表示扩展级别6的分片边界20。内部边界22表示级别6的分片T。因此，针对每个级别6的分片T，确定其扩展分片ET的边界链路。如图3所示，扩展ET边界可以通过向分片T的每条边添加级别7的分片进行计算。扩展分片ET的边界链路是级别8的链路中与扩展分片ET的边界相交的那些链路。
这些级别8的链路均以附图标记24来表示。这些链路24例如可以被划分为两个集合。例如，链路可以被划分为起始链路集合和目的地链路集合。起始链路集合可以包含去往ET之中的所有边界链路，并且目的地边界集合可以包含从ET 20离开的所有链路。双向边界链路可以被分配给两个集合。基于这两个集合，能够计算出从起始边界集合中的所有链路到目的地边界集合中的所有链路的最优路线。这些可以是最优路线。最优路线可以基于包含于扩展分片之中的级别8链路。分片T中作为最优路线的一部分的所有级别8链路可以蔓延至级别
6。因此，仅作为其中起始和目的地链路至少处于远离该链路的级别7分片的最优路线的一部分的那些链路被包含在级别6中。分片T的级别6链路的最终集合由处于从任意级别8起始边界链路到扩展分片的任意级别8目的地边界链路的最优路线上的所有级别8链路组成。
[0086] 在图3所示的布置中，级别8边界链路24以附图标记R1至R6来表示。由于除R4和R2以外的所有链路都是双向的，所以起始链路集合包括R1、R3、R4、R5和R6。目的地链路集合包括R1、R2、R3、R5和R6。在边界链路之间的、级别8上的用于最优路线的链路以附图标记26来表示。如所能够看到的，级别8上存在链路30，而链路30并非级别8边界链路的一部分而且也并非在边界链路之间的、级别8上的用于最优路线的级别8链路的一部分。如所能够看到的，具有一些以附图标记28表示的蔓延至级别6的链路。这些链路有效地成为级别8上的边界链路之间的最优路线的一部分，但是其处于分片T之内并且因此蔓延至级别6。
[0087] 现在参考图4A至H，它们图示了可以通过一些实施例来解决的问题。特别地，图4A或4H图示了可能在第一更新地区UR1被更新但是相邻的更新地区UR2未被更新的情况下计算路线制定信息所可能出现的问题。考虑图4A中的初始情形。第一更新地区UR1和第二更新地区UR2经由Q1/2014中的一些次要道路进行连接。
[0088] 图4B示出了更新后的情形，其中更新地区UR1和更新地区UR2变为由Q2/2014中新的主要道路进行连接。
[0089] 图4C示出了对应于图4A中所示的情形(即Q1/2014中的情形)的边缘标志。在该示例中，所有链路都可能具有指示该链路被用于进入到一些地区之中的一些最优路线的相同的边缘标志位向量。作为示例，该位向量可以是001100111。
[0090] 在图4D中，示出了Q2/2014中的情形，其中假设两个更新地区都已经被更新。所示出的是，次要道路的边缘标志向量现在仅包含零值，这指示链路并不是去往任何边缘向量分区的最优路线的一部分。两个地区之间的所有最优路线现在都使用新的高速公路，并且该新的主要道路链路的边缘向量现在与关联于该主要道路的先前的边缘链路相同。
[0091] 考虑图4E中所示的情形。特别地，更新地区UR1已经被更新以反映新的道路。然而，更新地区UR2还没有被更新并且包括Q1/2014的信息。如图4E中所示，规划了从第一更新地区UR1中的起点S开始到包含于新的边缘标志向量中被标记为1的分区之中的目的地的路线。换言之，向量中相应的位是“1”。将期望在更新地区UR1中使用该新的主要路线，但是这将无法延伸至更新地区UR2的路线之中(因为该更新地区还没有被更新)。UR1中之前的次要道路路线将不再被考虑，因为它们现在与目的地区域的边缘标志向量中的零值相关联。因此，在这种情况下将不可能使用边缘标志找到最优路线。
[0092] 现在将参考图4F至4H，它们示出了随着分层方法而出现的问题。同样，图4F示出了Q1/2014中的情形，其中更新地区UR1和更新地区UR2之间的路线仅经由次要道路。图4G示出了Q2/2014中的情形，其中主要道路现在将更新地区UR1和更新地区UR2相连。在图4F所示的布置中，该次要道路蔓延至更高的路线制定层，因为它们对于长距离路线制定而言是相关的。在Q2/2014中，仅新的主要链路蔓延至高路线制定层中，因为次要道路对于长距离路线制定而言不再重要。最优路线制定现在使用该主要链路。然而，考虑图4H中所示的情形，其中更新地区UR1已经被更新但是更新地区UR2还没有更新。如能够看到的，高层上的链路现在将不再被连接。更新地区UR1将具有主要道路，而更新地区UR2将具有次要路线。因此，将不可能在两个不同地区中使用这些高层找到最优路线。
[0093] 一些实施例可以提供对个体更新地区的增量更新。一些实施例可以使用预先计算的路线制定信息。
[0094] 现在参考图5A至5H，它们示出了一些实施例。一些实施例可以解决并避免之前所描述的问题。一些实施例可以允许对不同更新地区进行单独更新同时仍然允许找到最优路线。
[0095] 实施例可以与预先计算的路线制定信息一起使用。该预先计算的路线制定信息可以是任意适当的信息，并且例如可以使用之前所描述的边缘标志方法和/或链路分级方法。
[0096] 应当意识到的是，图5A和5B图示了与图4A至4B相同的场景。特别地，图5A示出了Q1/2014中的情形，其中两个更新地区UR1和UR2被边界隔开并且这两个更新地区通过次要道路进行链接。
[0097] 图5B示出了Q2/2014中的情形，其中已经提供了跨边界地区将两个更新地区UR1和UR2进行链接的新的主要道路。
[0098] 现在将参考图5C、5D和5E，它们图示了在使用边缘标志方法的部署的上下文中的实施例。同样，图5C与图4C中相同。考虑图5D。在Q2/2014中，随着主要道路的出现，包含该新的主要道路的道路网络上的边缘标志将会如下：新的主要道路的边缘标志将为001100111并且次要道路的边缘标志将为000000000。
[0099] 在一些实施例中，可以使用单调增大的边缘标志。由此，边缘标志向量中的位并不会从“1”切换到“0”，其允许位以增大方式从0切换到1。在所给出的示例中，这意味着Q2/
2014中的次要道路将保持边缘向量001100111。换句话说，次要道路和主要道路都保持相同的边缘向量。在一些实施例中，位的值仅可能增大，即值在新的数据库中从0变为1。可以防止值从1减小到0。例如，一个链路在位置i具有值1。在下一次更新中，再次运行编译并且该计算的结果将为该值在位置i应当为0。在一些实施例中，值“1”得以被保持而并不变为0。因此，位的值在某些位置会增大但是在一些实施例中并不减小。
[0100] 考虑图5E所示的场景，其中更新地区UR1被更新但是更新地区UR2并未被更新。现在将从更新地区UR1中的起点S找出最优路线制定。旧的次要道路和新的主要道路都将进行扩展并且由于次要道路连接至UR2，所以仍然能够找到最优路线。在UR1中，次要道路和主要道路在路线制定期间都将进行扩展。主要道路在图5E所示的场景中并非有必要被扩展，但是这考虑到了有关更新地区UR2是否已经被更新的不确定性。
[0101] 现在参考图5F至5H，它们示出了使用链路分级方法的实施例。图5F对应于图4F所示出的内容。利用先前的方法，如果对Q2/2014的链路分级进行编译，则如图4G中所示，主要道路将不会被包括在内。然而，如图5G所示，在实施例中，在某个链路级别的处于较旧的数据库中的链路将被保持在该级别并且在后续并不被存储在低链路级别之中。在一些实施例中，这将意味着Q2/2014中的次要道路被存储在它们在Q1/2014中被存储的相同链路级别。
因此，如能够从图5G所看到的，次要和主要道路现在都被存储在该链路级别。如果仅更新地区UR1进行了更新，则得到图5H所示的情形。因此，更新地区UR1中的起点S到更新地区UR2中的任何目的地的任何路线计算都将会找出最优路线，这是因为即使在更新地区UR2中还不包括主要路线的情况下次要路线也互相连接。
[0102] 一些实施例可以具有可能对更新地区进行单独更新的优点。一些实施例允许使用预先计算的路线制定信息。
[0103] 在一些实施例中，数据库编译的结果可以存储在数据库或存储器地图之中。例如，来自先前编译、例如针对Q1/2012的数据，例如可以存储在关系数据库中的表格中。
[0104] 对于边缘标志(edge flag)，这样的关系可以是旧边缘标志(永久链路ID，方向，边缘向量)。在这样的表格中，针对Q1/2014编译的所有链路都会被存储。
[0105] 随后可以执行针对新地区Q2/2014的数据的路线制定网络的预先编译。结果可以存储在新的表格临时新边缘标志(永久链路ID，方向，边缘向量)中。为了创建最终的表格新边缘标志(永久链路ID，方向，边缘向量)，可以使用以(伪)SQL描述的以下过程来如下执行：
[0106] INSERT INTO NewEdgeFlags
[0107] SELECT*FROM NewTempEdgeFlags UNION
[0108] SELECT*FROM OldEdgeFlags WHERE PermanentLinkID NOT IN(SELECT PermanentLinkID FROM NewTempEdgeFlags)；
[0109] UPDATE NewEdgeFlags N,OldEdgeFlags O SET N.EdgeVector＝(N.EdgeVector BITOR O.EdgeVector)WHERE N.PermanentLinkID＝O.PermanentLinkID AND N.Direction＝O.Direction；
[0110] DELETE OldEdgeFlags；
[0111] INSERT INTO OldEdgeFlags SELECT*FROM NewEdgeFlags；
[0112] 表格新边缘标志将包含针对Q2/2014编译的最终结果。
[0113] 边缘向量可以通过利用新的Q2/2014计算其值来计算，并且随后在位的级别与Q1/
2014中使用的边缘向量进行OR运算。位的级别上的该OR运算保证了该位绝对不会在新的边缘中从值1减小为值0，相反该位仅能够从值0增大为值1。新的结果存储在旧的表格之中，使得其可用于Q3/2014数据的编译。
[0114] 对于链路分级(link hierarchy)而言，情形会是相似的。
[0115] 之前表格的结果被存储在关系旧链路分级(永久链路ID，层级)中(与边缘标志的情形相反，不要求存储方向，因为只要要求一个方向，链路就蔓延至更高级别)。随后，利用新的数据执行链路分级计算，并且其结果被存储在中间表格临时新链路分级(永久链路ID，层级)中。为了创建最终的表格新链路分级(永久链路ID，层级)，可以使用以(伪)SQL所描述的以下过程来如下执行：
[0116] INSERT INTO NewLinkHierarchy
[0117] SELECT*FROM NewTempLinkHierarchy UNION
[0118] SELECT*FROM OldLinkHierarchy WHERE PermanentLinkID NOT IN(SELECT PermanentLinkID FROM NewTempLinkHierarchy)；
[0119] UPDATE NewLinkHierarchy N,OldLinkHierarchy O SET N.Level＝max(N.Level,O.Level)WHERE N.PermanentLinkID＝O.PermanentLinkID；
[0120] DELETE OldLinkHierarchy；
[0121] INSERT INTO OldLinkHierarchy SELECT*FROM NewLinkHierarchy；
[0122] MAX算子确保了链路绝对不会被存储在较低级别，即使这是新编译的结果。因此，可以保证即使在两个更新地区之一并未更新的情况下也能够在某个级别上找到最优路线。
[0123] 一些实施例可以允许对更新地区进行单独更新。
[0124] 在一些实施例中可以使用预先计算的路线制定信息。
[0125] 一些实施例可以使用更新地区的概念以及预先计算的路线制定信息。
[0126] 一些实施例除了“新的”编译的预先计算的信息之外还可以使用来自“旧的”编译的信息来创建包含预先计算的路线制定信息的新的数据库。
[0127] 一些实施例可以针对基于边缘标志的路线制定方法而在位的级别上应用OR运算。
[0128] 一些实施例可以针对分级路线制定方法的链路级别应用MAX算子。
[0129] 现在参考图6，其示意性示出了可以在其中提供一些实施例的系统。该系统包括能够使用地图服务的用户设备101。该用户设备所需要的地图信息可以经由通信网络105从地图服务平台103接收。提供保存地图数据的地图数据库109。该地图数据可以包括如以上所描述的用于一个或多个更新地区的数据以及预先计算的路线制定信息。在该实施例中，地图服务由地图服务平台103提供给用户设备101。
[0130] 导航设备可以是独立设备或装置，并且因此使得所需的地图信息被存储在该设备或装置自身上。
[0131] 参考图7。其示出了实施例可以与其一起来使用的装置。该装置包括位置传感器
110。该位置传感器可以包括能够获取与该装置的位置相关的信息的传感器。仅作为示例，该位置传感器可以是卫星定位传感器，诸如全球定位系统(GPS)传感器、辅助全球定位系统(辅助GPS)传感器或者任意其它适当的卫星定位传感器。应当意识到的是，可替换地或除此之外，该装置可以以任意其它适当方式获得位置信息，例如从基站等获得。
[0132] 该装置包括控制器120。在一些实施例中，控制器120包括至少一个处理器。控制器
120可以包括路线制定器功能122，其能够运算或计算期望的路线。
[0133] 提供了用户界面UI 114。用户界面114例如允许用户选择目的地和/或起点。
[0134] 该装置包括显示器112。显示器112可以被配置为显示地图信息，诸如路线和/或区域地图。在一些实施例中，该显示器可以是触摸屏并且因此提供了全部或部分的UI功能。
[0135] 提供了地图存储器114，其被配置为存储地图信息。该地图信息可以包括更新地区和/或预先计算的路线制定信息的至少一部分中的一种或多种。该地图存储器可以由一个或多个存储器提供。
[0136] 提供了接口118。在用户设备被配置为随地图服务平台一起工作的示例情形中，接口118将允许该设备例如与通信网络105进行通信。应当意识到的是，在其它实施例中，该接口可以被提供以允许使用适当方法或装置对独立设备进行更新。在一些实施例中，经更新的地图信息可以被提供至接口118并且被存储在地图存储器114中。
[0137] 路线制定器122例如可以使用来自位置传感器110的有关当前位置的信息、有关所需路线的信息以及存储在地图存储器中的信息来计算期望的路线。该期望的路线例如可以被显示在显示器112上。
[0138] 在一些实施例中，路线制定器122所提供的至少一部分路线计算可以在地图服务平台103中被提供。
[0139] 参考图8，其示出了一种方法。
[0140] 在步骤S1，输入针对路线的请求。该路线可以具有起点和目的地。例如，该起点可以被输入或者可以被假设为装置的当前位置。
[0141] 在步骤S2，确定信息可用于该起点和目的地之间的路线。
[0142] 在步骤S3，在需要的情况下下载地图信息。这可以例如经由地图服务平台103而来自于地图数据库109。应当意识到的是，在一些实施例中，步骤S2和S3可以至少部分被省略。
在该装置是独立设备的一部分的情况下，步骤S2和S3可以被完全省略。
[0143] 在步骤S4，使用如之前所讨论的预先计算的信息来计算该起点和目的地之间的路线。
[0144] 在步骤S5，从导航设备输出所计算的路线。该输出可以包括在显示器上显示该路线的至少一部分和/或诸如音频输出之类的任意其它适当输出。
[0145] 参考图9，其示出了一些实施例的方法流程。
[0146] 在步骤T1，确定更新地区已经被修改，特别是在边界地区中进行了修改，并且例如在表格中存储旧数据。
[0147] 在步骤T2，对新的更新地区进行编译并且例如将其存储在第二表格中。
[0148] 在步骤T3，对边缘信息进行更新以有效保持先前的信息和新的信息，或者如之前所描述的先前的信息的至少一部分。在使用边缘标志的情况下这可以通过针对旧的表格和新的表格执行OR运算来进行。在使用链路级别的情况下这可以是应用MAX算子。
[0149] 应当意识到的是，在可替换的实施例中，可以与预先计算的路线制定信息的其他方法一起使用。
[0150] 应当意识到的是，该实施例在图5中示出并且所概括的情形是作为示例的，并且实施例显然可以在其它适当场景中使用。
[0151] 已经关于更新地区对实施例进行了描述。应当意识到的是，其它实施例可以在其中两个相邻区域或地区可能在不同时间进行更新的任意其它场景中使用。
[0152] 在一些实施例中，链路的重要性随着发布的不同而并不出现退化，即使预先计算的路线制定算法希望如此。链路重要性由边缘标志向量中的值1或者该链路被存储于其中的最高级别来反映。换句话说，针对任何链路，位绝对不会从值1减小到值0。在分级方法中，链路被存储于其中的最大级别永远不会降低。
[0153] 所需的数据处理装置可以利用一个或多个数据处理器来提供。所描述功能在每个方面都可以由单独处理器或者集成处理器来提供。该数据处理器可以为适用于本地技术环境的任意类型，并且作为非限制性示例可以包括一个或多个通用计算机、专用计算机、微处理器、数字信号处理器(DSP)、应用特定集成电路(ASIC)、门级电路，以及基于处理器的多核处理器架构。数据处理可以跨若干数据处理模块进行分布。数据处理器例如可以利用至少一个芯片来提供。还可以在相关设备中提供适当的存储器容量。一个或多个存储器可以为适用于本地技术环境的任意类型，并且可以使用任意适当的数据存储技术来实施，诸如基于半导体的存储器设备、磁性存储器设备和系统、光学存储器设备和系统、固定存储器和可移动存储器。
[0154] 总体上，各个实施例可以以硬件或专用电路、软件、逻辑或者它们的任意组合来实施。一些方面可以以硬件实施，而其它方面则可以以固件或软件来实施，后者可以由控制器、微处理器或其它计算设备来执行，虽然实施例并不局限于此。虽然各个方面可以被图示并描述为框图、流程图或者使用其它一些图形表示进行图示，但是将要理解的是，作为非限制性示例，这里所描述的这些模块、装置、系统、技术或方法可以以硬件、软件、固件、专用电路或逻辑、通用硬件或控制器或者其它计算设备，或者它们的一些组合来实施。软件可以存储在物理媒体上，诸如存储器芯片或者在处理器内实施的存储器模块，诸如硬盘或软盘的磁性介质，以及诸如DVD及其数据变化形式、CD的光学介质。
[0155] 以上描述已经通过示例性而非限制性的示例提供了本发明的示例性实施例的完整且信息性的描述。然而，当结合附图和所附权利要求阅读时，各种修改和适配将通过以上描述而对于本领域技术人员是显而易见的。然而，对于本发明教导的所有这样和类似的修改都将落入如所附权利要求所限定的本发明的范围之内。实际上，存在着包括之前所讨论的一个或多个任意其它实施例的组合形式的另外的实施例。