生成地图版本间对应关系的方法、设备和计算机程序产品

摘要

本文提供一种生成和传送地图版本不可知的道路标识符的方法。方法可包括：提供对起点与目的地之间的路线请求的指示；响应于路线请求，接收道路链路标识符列表；响应于第一道路链路标识符不对应于道路链路标识符网络的道路链路标识符：将异或函数应用于第一道路链路标识符和道路链路标识符列表中的随后的道路链路标识符；响应于应用于第一道路链路标识符和随后的标识符的异或函数的结果与道路链路标识符网络的道路链路标识符对应，将道路链路标识符网络的道路链路标识符添加到路线。

说明书

技术领域

本文描述的实施例总体上涉及将来自第一地图版本的一个或多个地图元素与第二地图版本的一个或多个地图元素相关联，并且更具体地涉及在不考虑从中导出地图元素的地图版本的情况下生成地图元素之间的对应关系。

背景技术

历史上，基于纸的地图按照月、年或更长时间被周期性地更新以考虑道路基础设施的变化。地图更新需要大量的人力和基于预期需要打印新的地图。纸质地图已经为数字地图让路，数字地图可以被更有规律地更新，并且可以具有实质上更详细的细节，包括从道路到兴趣点的所有方式的特征或者可以被地理定位的其它特征。

数字地图可受益于各种数据源，例如卫星图像、众包位置和图像数据、众包特征/兴趣点信息、城市数据库、包括沿着道路网络行进的配备有传感器的车辆的地图服务提供商数据等。可以编译、过滤以及分析海量的地图相关数据以建立地图更新和改变。这些更新和改变可以相对容易地实现，并且可以基于最新的可用数据周期性地或按需更新。然而，地图数据可被更新的频率可相对快速地将一些数字地图降级为老式或过时。此外，较旧的地图版本可能与较新的地图版本不兼容，特别是当在地图版本之间存在实质性改变时。此问题导致在一个地图版本与另一地图版本之间的数据(如位置数据、兴趣点数据、道路基础设施数据等)交换中的问题。

发明内容

根据示例实施例提供了一种用于识别不同地图版本之间的一个或多个地图元素之间的对应关系的方法、设备和计算机程序产品。本文提供的实施例可以包括一种设备，该设备具有至少一个处理器和包括计算机程序代码的至少一个存储器。至少一个存储器和计算机程序代码被配置为利用处理器使得设备至少：提供对起点与目的地之间的路线请求的指示；响应于所述路线请求接收道路链路标识符列表；识别所述道路链路标识符列表中的第一道路链路标识符；响应于所述第一道路链路标识符对应于道路链路标识符网络的道路链路标识符，将所述第一道路链路标识符添加到路线；响应于所述第一道路链路标识符不对应于所述道路链路标识符网络的道路链路标识符：将异或函数应用于所述第一道路链路标识符和所述道路链路标识符列表中的随后的道路链路标识符，响应于应用于所述第一道路链路标识符和随后的标识符的所述异或函数与所述道路链路标识符网络的道路链路标识符对应，将所述道路链路标识符网络的所述道路链路标识符添加到所述路线；响应于所述道路链路标识符的顺序列表中的所述道路链路标识符直接或通过应用所述异或函数而对应于所述道路链路标识符网络的道路链路标识符，在由所述道路链路标识符网络表示的道路链路网络内建立所述路线。

示例实施例的设备可被促使：响应于第一道路链路标识符不对应于道路链路标识符网络的道路链路标识符：将异或函数应用于第一道路链路标识符和道路链路标识符网络的候选道路链路标识符；响应于应用于第一道路链路标识符和道路链路标识符网络的候选道路链路标识符的异或函数导致第一候选道路链路标识符、第一道路链路标识符和第二道路链路标识符之间的对应关系，建立第一候选道路链路标识符和第二候选道路链路标识符与第一道路链路标识符之间的对应关系。响应于道路链路标识符的顺序列表中的至少一个道路链路标识符不直接或通过应用异或函数而对应于道路链路标识符网络的道路链路标识符，设备可被促使：提供对道路链路标识符的顺序列表的拒绝。示例设备可以可选地被促使：提供起点与目的地之间的第二路线请求的指示，其中，第二路线请求包括避开所述道路链路标识符列表中的至少一个道路链路标识符不直接或通过应用所述异或函数而与所述道路链路标识符网络的道路链路标识符对应的指令。

促使设备在由道路链路标识符网络表示的道路链路网络内建立路线可以包括：促使设备提供沿路线的路线引导。起点和目的地之间的路线请求可包括对起点和目的地之间最快路线的请求，其中，路线请求可以可选地包括与所述最快路线不同的替代路线以及与所述替代路线相关联的时间惩罚的指示。促使设备在由道路链路标识符网络表示的道路链路网络内建立路线可以包括：促使设备提供沿着路线的路线引导，并且识别与替代路线相关联的时间惩罚。

本文提供的实施例可以包括具有至少一个非暂时性计算机可读存储介质的计算机程序产品，所述至少一个非暂时性计算机可读存储介质具有存储在其中的计算机可执行程序代码部分。计算机可执行程序代码部分包括程序代码指令，其被配置为：提供对起点与目的地之间的路线请求的指示；响应于所述路线请求接收道路链路标识符列表；识别所述道路链路标识符列表中的第一道路链路标识符；响应于所述第一道路链路标识符对应于道路链路标识符网络的道路链路标识符，将所述第一道路链路标识符添加到路线；响应于所述第一道路链路标识符不对应于所述道路链路标识符网络的道路链路标识符：将异或函数应用于所述第一道路链路标识符和所述道路链路标识符列表中的随后的道路链路标识符；响应于应用于所述第一道路链路标识符和随后的标识符的所述异或函数的结果与所述道路链路标识符网络的道路链路标识符对应，将所述道路链路标识符网络的所述道路链路标识符添加到所述路线；响应于所述道路链路标识符顺序列表中的所述道路链路标识符直接或通过应用所述异或函数而对应于所述道路链路标识符网络的道路链路标识符，在由所述道路链路标识符网络表示的道路链路网络内建立所述路线。

一些实施例的计算机程序产品可以包括程序代码指令，用于：响应于第一道路链路标识符不对应于道路链路标识符网络的道路链路标识符：将异或函数应用于第一道路链路标识符和道路链路标识符网络的候选道路链路标识符；响应于应用于第一道路链路标识符和道路链路标识符网络的候选道路链路标识符的异或函数导致第一候选道路链路标识符、第一道路链路标识符和第二候选道路链路标识符之间的对应关系，建立第一候选道路链路标识符和第二候选道路链路标识符与第一道路链路标识符之间的对应关系。

一些实施例的计算机程序产品还可以包括程序代码指令，用于：响应于道路链路标识符列表中的至少一个道路链路标识符不直接或通过应用异或函数而对应于道路链路标识符网络的道路链路标识符，提供对道路链路标识符列表的拒绝。实施例可以可选地包括用于提供在起点和目的地之间的第二路线请求的指示的程序代码指令，其中，所述第二路线请求包括用于避开所述道路链路标识符列表中的至少一个道路链路标识符不直接或通过应用所述异或函数而与所述道路链路标识符网络的道路链路标识符对应的指令。用于在由道路链路标识符网络表示的道路链路网络内建立路线的程序代码指令可以包括用于提供沿路线的路线引导的程序代码指令。起点和目的地之间的路线请求可包括对起点和目的地之间最快路线的请求，其中，路线请求还可包括与最快路线不同的替代路线以及与替代路线相关联的时间惩罚的指示。用于在由道路链路标识符网络表示的道路链路网络内建立路线的程序代码指令可包括用于提供沿路线的路线引导并且识别与替代路线相关联的时间惩罚的程序代码指令。

本文提供的实施例可以包括一种方法，包括：提供对起点与目的地之间的路线请求的指示；响应于所述路线请求，接收道路链路标识符列表；识别所述道路链路标识符列表中的第一道路链路标识符；响应于所述第一道路链路标识符对应于道路链路标识符网络的道路链路标识符，将所述第一道路链路标识符添加到路线；响应于所述第一道路链路标识符不对应于道路链路标识符网络的道路链路标识符：将异或函数应用于所述第一道路链路标识符和所述道路链路标识符列表中的随后的道路链路标识符；响应于应用于所述第一道路链路标识符和所述随后的标识符的所述异或函数的结果与所述道路链路标识符网络的道路链路标识符对应，将所述道路链路标识符网络的所述道路链路标识符添加到所述路线；以及响应于道路链路标识符的顺序列表中的道路链路标识符直接或通过应用所述异或函数而对应于所述道路链路标识符网络的道路链路标识符，在由所述道路链路标识符网络表示的道路链路网络内建立所述路线。

根据一些实施例，响应于第一道路链路标识符不对应于道路链路标识符网络的道路链路标识符，方法可包括：将异或函数应用于第一道路链路标识符和道路链路标识符网络的候选道路链路标识符；以及响应于应用于第一道路链路标识符和道路链路标识符网络的候选道路链路标识符的异或函数导致第一候选道路链路标识符、第一道路链路标识符和第二候选道路链路标识符之间的对应关系，建立第一候选道路链路标识符和第二候选道路链路标识符与第一道路链路标识符之间的对应关系。

响应于所述道路链路标识符列表中的至少一个道路链路标识符不直接或通过应用所述异或函数而对应于所述道路链路标识符网络的道路链路标识符，提供对所述道路链路标识符的顺序列表的拒绝。方法可以包括：提供起点和目的地之间的第二路线请求的指示，其中，第二路线请求包括用于避开所述道路链路标识符列表中的至少一个道路链路标识符不直接或通过应用所述异或函数而与所述道路链路标识符网络的道路链路标识符对应的指令。在由道路链路标识符网络表示的道路链路网络内建立路线可以包括提供沿路线的路线引导。起点和目的地之间的路线请求可包括：对起点和目的地之间最快路线的请求，其中，请求还可包括与最快路线不同的替代路线以及与替代路线相关联的时间惩罚的指示。

本文提供的实施例可以包括一种设备，该设备包括：用于提供对起点与目的地之间的路线请求的指示的装置；用于响应于路线请求，接收道路链路标识符列表的装置；用于识别道路链路标识符列表中的第一道路链路标识符的装置；用于响应于第一道路链路标识符对应于道路链路标识符网络的道路链路标识符，将第一道路链路标识符添加到路线的装置；响应于第一道路链路标识符不对应于道路链路标识符网络的道路链路标识符：用于将异或函数应用于第一道路链路标识符和道路链路标识符列表中的随后的道路链路标识符的装置；响应于应用于第一道路链路标识符和随后的标识符的异或函数的结果与道路链路标识符网络的道路链路标识符对应，用于将道路链路标识符网络的道路链路标识符添加到路线的装置；响应于道路链路标识符的顺序列表中的道路链路标识符直接或通过应用异或函数而对应于道路链路标识符网络的道路链路标识符，用于在由道路链路标识符网络表示的道路链路网络内建立路线的装置。

根据一些实施例，响应于第一道路链路标识符不对应于道路链路标识符网络的道路链路标识符，设备可以包括：用于将异或函数应用于第一道路链路标识符和道路链路标识符网络的候选道路链路标识符的装置；以及响应于应用于第一道路链路标识符和道路链路标识符网络的候选道路链路标识符的异或函数导致第一候选道路链路标识符、第一道路链路标识符和第二候选道路链路标识符之间的对应关系，用于建立第一候选道路链路标识符和第二候选道路链路标识符与第一道路链路标识符之间的对应关系的装置。

响应于道路链路标识符列表中的至少一个道路链路标识符不直接或通过应用异或函数而对应于道路链路标识符网络的道路链路标识符，设备可以包括用于提供对道路链路标识符的顺序列表的拒绝的装置。一些实施例的设备可以包括：用于提供起点和目的地之间的第二路线请求的指示的装置，其中，第二路线请求包括用于避开所述道路链路标识符列表中的至少一个道路链路标识符不直接或通过应用所述异或函数而与所述道路链路标识符网络的道路链路标识符对应的指令。用于在由道路链路标识符网络表示的道路链路网络内建立路线的装置可以包括用于提供沿路线的路线引导的装置。起点和目的地之间的路线请求可包括对起点和目的地之间最快路线的请求，其中，请求还可包括与最快路线不同的替代路线以及与替代路线相关联的时间惩罚的指示。

附图说明

已经概括地描述了本发明的示例性实施例，现在将参考附图，附图不一定按比例绘制，并且其中：

图1示出根据本公开的示例实施例的通信图；

图2是根据本公开的示例实施例的可以被具体配置用于在不同版本的地图之间使路段/道路标识符相关的设备的框图；

图3示出根据本公开的示例性实施例的道路链路，该道路链路被分割成两个道路链路，并添加了新的道路链路和节点；

图4示出根据本公开的示例性实施例的包括道路链路的道路网络；

图5示出根据本公开的示例性实施例的图4的道路网络，其中，移除了道路链路和节点；

图6示出根据本公开的示例实施例的在两个端节点之间定义的道路链路；

图7示出根据本公开的示例性实施例的被分割成三个道路链路的图6的道路链路；以及

图8是根据本公开的示例实施例的用于生成地图格式不可知的道路链路标识符的方法的流程图。

具体实施方式

现在将在下文中参考附图更全面地描述本发明的一些实施例，其中示出了本发明的一些但不是全部实施例。实际上，本发明的各种实施例可以以许多不同的形式来实施，并且不应被解释为限于本文阐述的实施例；相反，提供这些实施例是为了使本公开满足适用的法律要求。相同的附图标记始终表示相同的元件。如本文所使用的，术语“数据”、“内容”、“信息”和类似术语可以互换地使用，以指代能够根据本发明的实施例被发送、接收和/或存储的数据。因此，任何这种术语的使用不应被认为限制本发明的实施例的精神和范围。

如本文所定义的，指代非暂时性物理存储介质(例如，易失性或非易失性存储器装置)的“计算机可读存储介质”可以与指代电磁信号的“计算机可读传输介质”区分开。

根据示例实施例，本文提供了一种方法、设备和计算机程序产品，用于将来自第一地图版本的一个或多个地图元素与第二地图版本的一个或多个地图元素相关联，以适应可能具有不兼容的地图或地图版本的系统。在此描述的实施例能够在地图和地图版本不具有兼容的路段标识符或者可能以其它方式禁止传统的路线通信和导航的其它不兼容性的情况下，唯一地识别在地图版本之间已经改变的地图元素，并且确保旧的地图元素和修正的地图元素之间的适当的相关性。

图1示出用于实现本文描述的示例实施例的系统的示例实施例的通信图。图1的所示实施例包括地图服务提供商系统116、通过网络112与地理地图数据库(例如地图数据库108)进行数据通信的处理服务器102、以及一个或多个移动装置114。移动装置114可以与车辆相关联、耦接或以其它方式集成，例如，诸如仪表板(in-dash)车辆导航单元、车辆头端(vehicle head)单元、电子控制单元或高级驾驶员辅助系统(ADAS)或促进自动或半自主驾动的控制器。可以提供附加的、不同的或更少的组件。例如，许多移动装置114可以与网络112连接。地图服务提供商116可以包括计算机系统和系统运营商的网络。处理服务器102可以包括地图数据库108，诸如远程地图服务器。网络可以是有线的、无线的、或者有线和无线通信网络的任何组合，诸如蜂窝、Wi-Fi、因特网、局域网等。

处理服务器102可以是一个或多个固定或移动计算装置。移动装置114可以被配置为经由处理服务器102通过例如地图应用来访问地图数据库108，使得用户设备可以向用户提供导航辅助以及通过访问地图服务提供商116而提供的其它服务。

地图数据库108可包括节点数据、路段/链路数据、兴趣点(POI)数据等。地图数据库108还可包括地图数据、路线数据和/或操纵数据。根据一些示例实施例，路段/链路数据记录可以是表示道路、街道或路径的链路或段，如可以在计算路线或记录的路线信息以确定一个或多个个性化路线时使用的。链路或道路可以由折线表示，其中每条折线包括建立道路几何形状的路径的多个顶点。节点数据可以是与路段数据的各个链路或段相对应的端点。道路链路数据和节点数据可以表示道路网络，例如由车辆、汽车、卡车、公共汽车、摩托车和/或其它实体使用的道路网络。可选地，例如，除了或代替车辆道路记录数据，地图数据库108可包含路径段和节点数据记录或可表示行人路径或区域的其它数据。道路链路/路段和节点可以与属性以及POI相关联，所述属性诸如地理坐标、街道名称、地址范围、速度限制、路口处的转弯限制和其它导航相关属性，所述POI诸如加油站、旅馆、餐馆、博物馆、体育场、办公室、汽车修理店、建筑物、商店、公园等。地图数据库108可包括关于POI及其在POI记录中的相应位置的数据。地图数据库108可包括关于诸如城市、城镇或其它社区的地点的数据，以及诸如水体、山脉等的其它地理特征。这种地点和特征数据可以是POI数据的一部分或可以与POI或POI数据记录(诸如，用于显示或表示城市位置的数据点)相关联。另外，地图数据库108可包括与地图数据库108的POI数据记录或其它记录相关联的事件数据(例如，交通事故、施工活动、预定事件、非预定事件等)。

地图数据库108可由内容提供商(例如，地图服务提供商)维护，且可基于新道路、现有道路的重新规划路线、兴趣点的改变等而周期性地更新。以示例的方式，地图服务提供商可以收集地理数据以生成并增强地图数据库108。根据一些实施例，地图数据库108可以将地图生成和修正委托给诸如移动装置114的其它装置。可以存在由地图服务提供商用来收集数据的不同方式。这些方式可以包括从诸如市政当局或相应地理当局的其它源获得数据。此外，例如，地图服务提供商可以雇佣现场人员沿着整个地理区域的道路乘车辆行进，以观察特征和/或记录关于它们的信息。此外，可使用远程感测(例如，航空或卫星摄影)来直接或通过如本文所描述的机器学习生成地图几何形状。从各种源中收集的地图数据可被编译成可周期性地或按需发生的地图更新，从而产生动态地图数据库108，其被例行地改变和更新以反映道路的最准确表示和区域的特征。

地图数据库108可以是以便于更新、维护和开发的格式存储的主地图数据库。例如，主地图数据库或主地图数据库中的数据可以是Oracle空间格式或其它空间格式，例如以用于开发或生产目的。Oracle空间格式或开发/生产数据库可以被编译成递送格式，例如地理数据文件(GDF)格式。可以对生产和/或递送格式的数据进行编译或进一步编译，以形成地理数据库产品或数据库，其可以用于终端用户导航装置或系统中。

例如，可编译地理数据(例如，编译成平台规范格式(PSF))以组织和/或配置数据，以用于由导航装置(例如，移动装置114)执行导航相关功能和/或服务，例如路线计算、路线引导、地图显示、速度计算、距离和行进时间功能和其它功能。导航相关功能可以对应于车辆导航、行人导航或其它类型的导航。虽然本文描述的示例实施例总体上涉及沿着道路的车辆行进，但是示例实施例可以被实施用于沿着人行道的行人行进、沿着自行车路径的自行车行进、沿着海上导航路线的船只行进等。产生终端用户数据库的编译可以由与地图服务提供商分离的一方或实体来执行。例如，地图服务提供商的客户，诸如导航装置开发者或其它终端用户装置开发者，可以以递送格式对所接收的地图数据库执行编译，以产生一个或多个编译的导航数据库。

如上所述，服务器侧地图数据库108可以是主地理数据库，但是在替代实施例中，客户端侧地图数据库108可以表示编译的导航数据库，该编译的导航数据库可以在终端用户装置(例如，移动装置114)中使用或者与终端用户装置一起使用以提供导航和/或地图相关的功能。例如，地图数据库108可与移动装置114一起使用以向最终用户提供导航特征。在这种情况下，例如，地图数据库108可以被下载或存储在终端用户装置(移动装置114)上，该终端用户装置可以通过无线或有线连接(例如经由处理服务器102和/或网络112)访问地图数据库108。可选地，地图数据库108的一部分，诸如关于特定道路的地图数据，可以被下载或临时存储在终端用户装置上，并且根据本文描述的各种实施例，移动装置114可以被配置为在将地图数据发送回地图数据库108之前修改关于道路的地图数据。

根据一些实施例，服务器侧地图数据库108和客户端侧地图数据库可以不同。例如，即使当两个地图数据库的地图数据都来自同一地图服务提供商116时，地图数据也可能在服务器侧与客户端侧之间不同。这可能是由于存在不同的地图版本并且以不同的周期速率对其进行更新而导致。此外，当所述地图数据源自不同来源时，客户端地图数据和服务器地图数据可不同。当移动装置114需要路线服务并且路线服务由地图服务提供商116提供时，客户端和服务器之间的不同地图数据和地图版本可能是有问题的。由服务器端地图数据库108中的唯一标识符标识的道路链路可能与客户端侧地图数据库的标识符或道路链路不兼容。这样，本文提供的实施例使用标识符独立的协议来向客户端提供服务器侧生成的路线。

在一个实施例中，移动装置114可为车辆内导航系统，例如ADAS、个人导航装置(PND)、便携式导航装置、蜂窝式电话、智能电话、个人数字助理(PDA)、手表、相机、计算机和/或可执行例如数字路线规划和地图显示等导航相关功能的其它装置。根据一些示例实施例，例如，提供了一种移动装置，以用于针对导航和地图功能(例如引导和地图显示)并且用于基于一个或多个计算和记录的路线来确定一个或多个个性化路线或路段。

处理服务器102可从移动装置114或与移动装置114通信的装置接收探测数据。移动装置114可以包括一个或多个检测器或传感器，作为构建或嵌入到移动装置114中或内的定位系统。可替代地，移动装置114使用通信信号来进行位置确定。移动装置114可以从定位系统(例如全球定位系统(GPS))、蜂窝塔定位方法、接入点通信指纹等接收位置数据。服务器102可接收被配置为描述移动装置的位置的传感器数据，或移动装置114的处理器可从移动装置114的定位系统接收传感器数据。移动装置114还可包括用于跟踪移动装置移动(例如，旋转、速度或加速度)的系统。还可以使用定位系统来确定移动信息。移动装置114可以使用检测器和传感器来提供指示车辆的位置的数据。此车辆数据(本文也称为“探测数据”)可由能够确定必要信息且将必要信息提供到远程实体的任何装置收集。移动装置114是可用作用于收集车辆的探测数据的探测器的装置的一个示例。

更具体来说，(例如，由移动装置114收集的)探测数据表示车辆在相应时间点处的位置，且可在车辆正沿着路线行进时被收集。虽然探测数据在本文中被描述为车辆探测数据，但可用行人探测数据、海运交通工具探测数据或非机动交通工具探测数据(例如，来自自行车、滑板、马背等)来实施示例实施例。根据以下描述的探测数据来自沿道路行进的机动车辆的示例实施例，探测数据可以包括但不限于位置数据(例如，纬度和经度位置、和/或高度、GPS坐标、无线网络定位(诸如Wi-Fi/Bluetooth

处理服务器102的示例实施例可体现于如图2中所示的设备中。即使在服务器侧地图数据不同于客户端侧地图数据时，诸如如图2所示的设备可根据本发明的示例实施例而经特定配置以用于将沿着起点与目的地之间的路段的服务器生成的路线连接到客户端装置地图数据。该设备可以包括处理器202、存储器装置204、通信接口206和用户接口208，或者以其它方式与它们通信。在一些实施例中，处理器(和/或协处理器或辅助处理器或以其它方式与处理器相关联的任何其它处理电路系统)可以经由总线与存储器装置通信，以用于在设备的组件之间传递信息。存储器装置可以是非暂时性的，并且可以包括例如一个或多个易失性和/或非易失性存储器。换言之，例如，存储器装置可以是包括门的电子存储装置(例如，计算机可读存储介质)，所述门被配置为存储可以由机器(例如，类似处理器202的计算装置)检索的数据(例如，比特)。存储器装置可以被配置为存储信息、数据、内容、应用、指令等，以使得设备能够根据本发明的示例实施例执行各种功能。例如，存储器装置可以被配置为缓冲用于由处理器处理的输入数据。另外或可替代地，存储器装置可经配置以存储由处理器执行的指令。

处理器202可以以多种不同的方式来实现。例如，处理器可以被实现为各种硬件处理装置中的一个或多个，诸如协处理器、微处理器、控制器、数字信号处理器(DSP)、具有或不具有附带DSP的处理元件、或各种其它处理电路系统，包括集成电路，诸如例如ASIC(专用集成电路)、FPGA(现场可编程门阵列)、微控制器单元(MCU)、硬件加速器、专用计算机芯片等。因此，在一些实施例中，处理器可以包括被配置为独立地执行的一个或多个处理核。多核处理器可以在单个物理封装内实现多处理。另外或可替代地，处理器可包括经由总线串联配置以实现指令、管线操作和/或多线程的独立执行的一个或多个处理器。

在示例实施例中，处理器202可以被配置为执行存储在存储器装置204中的指令或者处理器可访问的指令。可替代地或另外地，处理器可经配置以执行硬编码功能性。这样，无论是通过硬件或软件方法配置的，还是通过其组合配置的，处理器可以表示能够在被相应地配置时执行根据本发明实施例的操作的(例如，物理地实现在电路系统中的)实体。因此，例如，当处理器被实现为ASIC、FPGA等时，处理器可以是用于进行本文描述的操作的专门配置的硬件。可替代地，作为另一示例，当处理器实现为软件指令的执行器时，指令可特定地配置处理器以在执行指令时执行本文描述的算法和/或操作。然而，在一些情况下，处理器可以是处理器专用装置(例如，移动终端或固定计算装置)，其被配置为通过由用于执行本文描述的算法和/或操作的指令对处理器的进一步配置来采用本发明的实施例。此外，处理器还可以包括时钟、算术逻辑单元(ALU)和被配置为支持处理器的操作的逻辑门。

示例实施例的设备200还可以包括通信接口206，其可以是任何装置，诸如以硬件或硬件和软件的组合实现的装置或电路系统，其被配置为从与设备通信的通信装置接收数据和/或向与设备通信的通信装置发送数据，诸如以促进与一个或多个移动装置114等的通信。在这点上，通信接口可以包括例如用于实现与无线通信网络的通信的天线(或多个天线)和支持硬件和/或软件。附加地或可替代地，通信接口可以包括用于与(一个或多个)天线交互以促使经由(一个或多个)天线的信号的传输或处理经由(一个或多个)天线接收的信号的接收的电路系统。在一些环境中，通信接口可以可替代地或还支持有线通信。这样，例如，通信接口可以包括通信调制解调器和/或用于支持经由电缆、数字用户线(DSL)、通用串行总线(USB)或其它机制的通信的其它硬件和/或软件。

设备200还可以包括用户接口208，其可以进而与处理器202通信以向用户提供输出，并且在一些实施例中，接收用户输入的指示。这样，用户接口可以包括显示器，并且在一些实施例中，还可以包括键盘、鼠标、操纵杆、触摸屏、触摸区域、软键、一个或多个麦克风、多个扬声器或其它输入/输出机制。在一个实施例中，处理器可以包括用户接口电路系统，其被配置为控制一个或多个用户接口元件(如，显示器，以及在一些实施例中，为多个扬声器、振铃器、一个或多个麦克风等)的至少一些功能。处理器和/或包括处理器的用户接口电路系统可以被配置为通过存储在处理器可访问的存储器(例如，存储器装置204等)上的计算机程序指令(例如，软件和/或固件)来控制一个或多个用户接口元件的一个或多个功能。

本发明的示例实施例可以提供一种机制，用于识别可能具有不同链路标识符的两个不同地图版本之间的道路链路，以便识别从第一系统到第二系统的路线、地址、交通或其它信息，该第一系统和第二系统以不同的地图版本操作。根据示例实施例，可以将诸如道路的路径、所述道路上的交通方向、路口等的地图信息存储在例如服务器侧地图数据库108上。由于道路基础设施随着时间的推移而退化，因此现有道路上的道路建设是将至少暂时改变道路的不可避免的事件。此外，人口和车辆交通的增加导致需要新的或扩展的道路，而其它道路可以被移除或替换。如本文所使用的术语“道路”可以指车辆在从一个地方移动到另一个地方时可以采取的任何路径。道路可以是铺设的、改进的道路、砾石道路、泥土小径等，使得道路不暗示绘制的道路必须被标识为县、州或联邦维护的道路，并且可以包括私人道路，诸如进口道路、邻近街道等。由于这些道路可能随着时间的推移而改变，因此与这些道路相关的地图信息可能需要修正以跟上对道路路径的改变。另外的地图更新触发可以包括与道路相关的变化，例如道路上的速度限制变化，这也可以促使道路链路的分割，这例如得到具有新道路链路标识符的新道路链路。

服务器侧地图数据库108可通过用于唯一地识别道路链路的道路链路标识符来识别道路链路，其中所标识的路段序列可用作起点与目的地之间的路线。然而，客户端侧地图数据可能不如服务器侧地图数据新。客户端侧地图数据可以是提供有导航系统或应用的地图数据，并且可以不接收提供给服务器侧地图数据库108的周期性更新。因此，客户端地图数据可能不匹配服务器侧地图数据，且用于识别服务器侧地图数据中的道路链路的唯一标识符可能不对应于客户端地图数据中的对应道路链路的唯一标识符。此外，道路可通过新建、通过增加或拆除道路、通过道路的重新规划路线和交通模式等而改变。因此，由服务器侧地图服务提供商116生成的路线可以通过唯一标识符来参考道路链路，所述唯一标识符不对应于客户端侧地图数据上的等效路线。

虽然本文描述的示例实施例一般涉及为了路线引导的目的而关联服务器和客户端之间的道路链路，但是可以出于各种原因执行两个不同系统之间的道路链路的关联。例如，服务器可以将关于地理区域的信息传送给客户端，诸如交通事件、道路封闭、或用户可能感兴趣的其它因素。在传送该信息时，服务器可以识别事件正在沿着其发生或者其信息可用的道路链路。客户端可以具有不同的地图版本，使得在地图版本之间正确地转换道路链路标识是重要的。因此，可以出于多种原因中的任何原因执行地图版本之间的道路链路的关联。此外，例如，虽然本文描述的示例实施例可以主要涉及服务器侧和客户端侧地图版本和转换，但是实施例可以在客户端装置之间采用，例如两个用户在彼此之间通信以识别路段。

本文描述的示例实施例提供了一种机制，以可靠地且可重复地使不同地图版本之间的道路链路相关。根据示例实施例，为了使客户端侧装置正确地接收、解释和呈现由服务器侧地图服务提供商116生成的路线引导或导航，服务器和客户端需要能够将服务器侧地图版本和客户端侧地图版本之间的道路链路关联，以用于在服务器侧计算的诸如到目的地的路线之类的信息，所述信息可以被传送到客户端并且被正确地理解/转换。用于描述路线中的道路链路序列的地图路段/链路的唯一标识符或用于向用户提供信息的地图道路链路的唯一标识符必须在相同地图数据和版本中匹配以用于服务器与客户端之间的常规路线传送。然而，本文描述的示例实施例可以将两个不同地图版本之间的道路链路相关，以使得即使当道路链路标识符不匹配时也能够在两个不同地图版本之间传送道路链路相关的信息(例如，路线引导、兴趣点信息等)。

例如，如果地图服务提供商维护地图支持达四年，并且每季度发布新的地图更新/版本，并且具有在现场使用的四种不同的地图格式版本，则地图服务提供商将需要为四种地图格式(4)保持四年(4)的四个季度(4)，总共64个地图版本将必须同时在服务器上维护，以预期具有64个变体中的任何一个的某个装置可以从地图服务提供商请求路线。由于需要维持的地图变体的不可持续的生长，这种方法不能如所说明的那样针对快速刷新(例如，每周/每天发布)进行缩放。所需的地图变体越多，导致存储器消耗越大且处理性能越低。本文描述的实施例定义了路线以及客户端和服务器之间的工作流，其基于在经由路线的点之间折回路线并验证路线的片段的指纹，从而避免了在服务器和客户端之间具有相同版本的地图的需要。

本文描述的实施例定义了地图服务提供商116的方案，诸如在由处理服务器102执行的地图编辑软件中或者在地图编译期间，其以标识符在两个不同地图版本之间的对应地图元素之间清楚地相关的方式生成地图元素(例如，路段或链路)标识符。本文描述的实施例可以用于真实世界的所有图形表示。然而，用于二维地图的常规稳定拓扑链路可用于表示道路网络。二维地图可以被建模为节点和链路。链路在节点之间跨越，并且节点连接一个或多个链路。节点的度是它连接的链路的数量。如果节点正好连接两个链路，则该节点被称为二价。单价节点是道路的端点，例如死胡同(dead end)或尽头路(cul-de-sac)。如果本文定义的地图不包含任何二价节点，则它可以是稳定的拓扑地图。然后，链路被认为是稳定的拓扑链路。稳定的拓扑链路通常是稳定的，因为它们通常仅在建立新道路时改变。

图3示出响应于稳定拓扑地图的改变而改变的链路标识符的示例实施例。如图所示，链路A是两个端节点302和304之间的单个链路。新的道路，链路D，被构建并被添加到在新节点306处加入先前链路A的拓扑。需要节点306，因为道路之间的任何路口都在节点处。新节点306的插入将链路A分成两个段，链路B和链路C。链路B和链路C每个都被分配一个新的标识符，该标识符不同于它们所形成的链路A。这种改变对于传统的地图系统可能是有问题的。两个不同版本的地图在节点和链路标识符方面可能不同。一个版本的地图可以包括链路A，而另一个版本的地图包括新的链路D，因此包括链路B和C而不包括链路A。传统的地图软件可能不能解决由于不同的链路标识符而引起的差异。例如，如果从包括链路B和链路C的新版本的地图生成路线，则采用旧版本的地图的车辆的导航系统可能不能在它们的地图上找到链路B和C，使得路线不被导航系统理解并被拒绝。本文描述的实施例通过将地图的版本之间能够相关以从链路A识别链路B和C以使得地图版本兼容来解决该问题。

本文描述的实施例采用异或(XOR)函数或异或逻辑门。异或函数是当真输入的数量为奇数时给出“真”输出的逻辑门。如果到函数的输入中的一个且仅一个为真，则有时被称为“异或”的异或函数提供“真”输出。异或函数表示不等式函数，其中如果输入不相似，则输出为真，否则输出为假。当两个输入中的一个或另一个为真而不是两个都为真的逻辑问题时，异或提供真输出。n位异或函数由n个门构成。例如，语句x_1XOR x_2指的是ID＝x的第一位和第二位之间的异或。按位的异或涉及来自两个标识符(例如，6位标识符)的对应位被进行逻辑异或处理以形成第三标识符中的对应位。示例可以包括6位标识符，包括标识符A＝011101和标识符B＝001011。应用于标识符A和B的异或标识符将得到标识符C＝010110，其中当异或为假(位相等)时呈现零，而当异或为真(位不相等)时呈现1。

根据本文描述的示例实施例，XOR(x_1,…，x_n)表示顺序应用的按位的异或函数，或者表示为x_1XOR…XOR x_n。异或函数与任意分组的可能性相关联。作为示例：

如果z＝x XOR y，则x XOR(y XOR z)＝(x XOR y)XOR Z(1)

异或函数在此被应用以将不同地图版本之间的链路标识符相关，从而使得能够将一个版本的地图的地图标识符转换为另一版本中的地图中的不同标识符或多个标识符。根据示例实施例，可以使用128位或64位链路标识符。参考图3的示例性说明，链路A具有分配给它的128位数字标识符。当新链路添加到地图并与链路A相交时，如在节点306处与先前链路A相交的链路D所示，链路B、C和D中的每一个都需要新的唯一128位数字标识符。由于新的链路D的添加，来自先前版本的地图的链路A被分割成新版本的地图中的链路B和C。可以将随机的128位数字标识符分配给链路D，作为表示为ID_D的数字标识符，并且可以将随机的128位数字标识符分配给链路B，表示为ID_B。原始链路A具有表示为ID_A的数字标识符。

根据本文描述的示例实施例，用于链路C的数字标识符被设置为ID_C＝XOR(ID_A,ID_B)。基于上述，链路B被分配标识符ID_B，链路C被分配标识符ID_C。由于当创建链路A时，ID_A被选为随机数，并且ID_B是随机数，所以ID_C也可以被看作随机数。在128位标识符之间或者甚至在64位标识符之间的这些随机数的冲突风险很低。对于128位标识符的情况，假设每年创建2^32(四十亿)个新链路，这高得不切实际，在128年之后，将已经创建了2^39个新链路。在该时间期间两个标识符相同的风险在2*10^15之一。这是极不可能发生的极小风险。虽然上面描述了128位和64位标识符，但是特别是当全局地图被分段并且可以在不同段之间复制标识符时，可以使用较短的标识符。

由于异或函数的属性，ID_C＝XOR(ID_A,ID_B)还意味着基于关联属性有ID_A＝XOR(ID_B,ID_C)。因此，在链路A的旧链路标识符(ID_A)和链路B和C的新链路标识符(分别为ID_B和ID_C)之间存在清楚的关系。因此，如果路径引用了在新地图中不能找到的来自旧地图的标识符(ID_A)，则系统仅必须检查在新地图中是否存在两个相邻链路的两个标识符(ID_1和ID_2)，其中ID＝XOR(ID_1,ID_2)。这样，来自具有已被分割的链路的旧版本的路径可以被唯一地和安全地映射到新版本。

本文将针对由地图服务提供商116使用最近的、最新的可用地图沿着多个路段或链路在起点与目的地之间计算的路线400来描述示例实施例。图4示出节点310处的起点和节点312处的目的地之间的路线。起点和目的地不需要在节点处，并且可以沿着道路链路；然而，为了易于说明，将起点和目的地示为节点。图4所示的路线包括从起点到目的地的道路链路，包括具有链路标识符ID_X的道路链路314和具有链路标识符ID_Y的链路316。具有链路标识符ID_Z的链路318被图示为最近添加的道路链路，其不存在于先前版本的地图中。图5提供可在用户的导航装置处维持的先前版本的地图中的图4的道路链路的指示。响应于用户请求在起点和目的地之间的路线，可以提供包括链路314和316(分别为ID_X和ID_Y)的路线。可以以用于导航系统的链路标识符序列的形式向用户提供路线，以与地图相关，从而向用户提供路线引导。然而，链路314和316不存在于导航装置的地图版本中，使得路线不对应于导航装置的地图且在没有本文所描述的实施例的情况下不能被生成。

可被示出为包括处理器202的设备200的示例实施例的导航装置可识别：由地图服务提供商116所提供的路线包括不对应于导航装置地图的链路的链路。作为响应，导航装置可使用本文所述的方法分析链路的组合，以确定旧版本的地图的任何现有链路是否对应于新地图版本的新链路。所述处理可在导航装置未识别的第一链路处开始。在所示实施例中，在导航装置的地图中未找到具有标识符ID_X的道路链路314。导航装置接着可使用异或函数来取得连续链路的组合以建立对应关系。在所说明的实施例中，由设备200使用处理器202实现的导航装置可将ID_X设定为等于XOR(ID_W、ID_Y)。选择具有标识符ID_W的链路320，因为它是来自最后节点的对应于地图服务提供商116提供的路线的道路链路。选择具有标识符ID_Y的链路316，因为它是与具有标识符ID_X的链路314连续的道路链路。函数ID_X＝XOR(ID_W,ID_Y)将返回真响应，因为具有标识符ID_W的链路320被分成具有标识符ID_X的链路314和具有标识符ID_Y的链路316。

尽管通过上述实施例找到了正确的链路对应关系，但是实施例还将考虑具有标识符ID_W的链路320是否对应于具有标识符ID_X的链路314和具有标识符ID_Z的链路318。这是因为具有标识符ID_W的链路320是来自最后节点的对应于地图服务提供商116提供的路线的道路链路，因此选择它。选择具有标识符ID_Z的链路318，因为它是与具有标识符ID_X的链路314连续的道路链路。函数ID_X＝XOR(ID_W,ID_Z)将返回假响应，因为具有标识符ID_W的链路320没有被分成具有标识符ID_X的链路314和具有标识符ID_Z的链路318。

尽管上述实施例涉及道路链路被分割或分成较小的道路链路，但是实施例还可以包括诸如在道路从路口被移除的情况下合并的道路链路。返回参考图3，原始地图可以包括具有标识符ID_B、ID_C和ID_D的道路链路。然而，新地图可以包括具有标识符ID_A的道路链路。在这种情况下，可以生成在节点302和节点304之间的道路链路的标识符。在新版本的地图中，ID_A被设置为等于XOR(ID_B,ID_C)，并且ID_A被分配给节点302和节点304之间的链路。

本文描述的实施例提供了地图版本之间的旧道路链路标识符和新道路链路标识符之间的清楚关系。因此，如果路径引用了在新地图中不能找到的来自旧地图的两个连续的标识符ID_1和ID_2，则用户可以检查新地图是否包含满足XOR(ID_1,ID_2)的链路标识符。以这种方式，来自旧版本的地图的路径被唯一且安全地映射到修正的地图的合并的链路。

本文提供的实施例在可以集成到地图编辑软件中的公共地图编辑操作下生成链路标识符。链路标识符可以完全替代现有的标识符方案，或者作为属性添加到链路以避免剧烈的改变。使用上述方法使得能够在通过比较地图的事实之后生成这些标识符，从而代替扩展地图编辑，可以在将原始地图数据编辑为目标格式期间进行。例如，实施例可以作为各种地图格式(如高分辨率(HD)地图、导航数据标准(NDS)地图、RDF映射语言等)的附加属性来承载。

本文描述的实施例提供了对较长链的链路的特性的保存。给定非周期的路径作为在一个地图版本中的标识符ID_1,…,ID_N序列以及在另一地图版本中的标识符ID’_1,…ID’_M的对应序列，则其保存该XOR(ID_1,…,ID_N)＝XOR(ID’_1,…ID’_M)。这样，通过将异或函数应用于所有地图链路ID，可以在所有地图版本上唯一地标识相同路径。

虽然上述示例已经相对简单化以便于理解，但是实施例可以被外推以建立在旧地图版本和新地图版本之间的对应关系时包括明显更多的道路链路选项。图6示出外推的示例实施例，其中具有标识符ID_E的道路链路在旧地图版本中的节点402和404之间延伸。这部分地图可能在郊区，在那里正在建设新的住宅开发，使得在图7中示出了新的地图版本。对于用来找到相应的链路组合的具有标识符ID_E的道路链路，可以使用异或函数尝试许多排列。

ID_E＝XOR(ID_F,ID_Q)：FALSE

ID_E＝XOR(ID_F,ID_J)：FALSE

ID_E＝XOR(ID_F,ID_G)：FALSE

ID_E＝XOR(ID_FG,ID_H)：FALSE

ID_E＝XOR(ID_FJ,ID_K)：FALSE

ID_E＝XOR(ID_FJ,ID_L)：FALSE

ID_E＝XOR(ID_FQ,ID_S)：FALSE

ID_E＝XOR(ID_FQ,ID_R)：TRUE

当对应关系的搜索沿着路径进行并添加如ID_FQ所示的链路时，可以连接连续的链路，其中，ID_FQ所示的链路对应于具有标识符ID_F和ID_Q的链路。如图所示，异或函数可以用于沿着一系列连续链路爬行(crawl)以建立链路之间的对应关系。在指示尝试失败之前，这种爬行可以被限制到预定数量的组合或前进程度(例如，尝试组合多少个连续链路)。

解析不同地图版本之间的路线

区域中的道路网络可包括多个路段或道路链路，其结合在一起以形成道路网络。每个路段可以包括参考点或“中点”，其可以接近路段长度的中间。路线包括在起点与目的地之间在一个序列中的多个路段，而路线片段包括沿着路线的中间路段之间的路线的路段组。例如，路线可包括路段A、B、C、D和E。其中A是起点沿着其定位的起始路段，且E是目的地沿着其定位的目标路段。

根据本文描述的示例实施例，基于服务器的地图服务提供商116可以仅使用地图数据库108中的地图数据的单个变体，从而仅维护最新的、最近的和准确的地图。诸如移动装置114的客户端可以是预先安装的、可能过时的地图。例如，移动装置可以被实现为车辆中的导航系统，其中移动装置上的地图数据可以在车辆组装时被安装，并且因此可能是停滞的并且容易变得过时。使用地图匹配技术，移动装置114可以将“START_SEGMENT”识别为过时地图中的与移动装置114相关联的车辆所位于的路段。“TARGET_SEGMENT”是由用户在移动装置114的过期地图中识别为要到达的目的地的路段。例如，可以通过对目标地址进行地理编码来确定该目的地。

服务器侧路线计算和编码

为了生成服务器侧路线，可定义道路网络的特定数据点，无论是在过时的地图变体上还是在当前版本的地图上。路段的中点可为在路段的中途点处或接近中途点的点的坐标。例如，在两个路口或节点之间延伸并且是半英里长的路段的中点可以是距每个路口或节点四分之一英里。海拔可可选地被定义为路段的“z水平”。路段的“z水平”或海拔可通常为零，但隧道中的路段可具有负z水平，而桥梁和立交中的堆叠道路可具有正z水平。z水平海拔描述路段在正交于地面的垂直方向上的相对位置。散列函数可以由本文描述的实施例使用。散列函数可以是任何散列函数(例如MD5、SHA)，尽管在路线编码和解码过程的服务器侧和客户端侧上都将使用相同的散列函数。

客户端(例如，移动装置114)可以通过编码起始点来向服务器发送路线请求。起始点可以被编码为移动装置114的当前路段或“START_SEGMENT”的中点+z水平。目的地可以被编码为“TARGET_SEGMENT”的中点+z水平。客户端还可以发送START_SEGMENT和TARGET_SEGMENT的异或稳定标识符。异或稳定标识符可以是客户端的地图版本内的道路链路的标识符，其已经如上所述使用异或函数针对道路更新进行了处理，使得对地图数据的未来更新可以与地图数据的先前迭代正确地相关。

基于所提供的起点(START)和目的地(目标)，服务器(例如，地图服务提供商116)可以在最新地图版本中找到适当的段。服务器可以以诸如几米的容差处理输入数据，由此客户端提供的中点的误差可能与服务器标识的相应中点不同达该容差。此外，在隧道、桥梁或立交沿着由中点标识的路段定位的情况下，z水平可用于澄清或“平局决胜”选定路段。可选地，如果存在START和TARGET的多个候选，则服务器可以使用START_SEGMENT和TARGET_SEGMENT的异或稳定标识符来找到适当的链路。

如果地图服务提供商不能将START精确地匹配到其地图，则将在响应于客户端时标记警告。在此情形中，当用户处于未定义的位置时可警告用户他们需要移动位置(例如，沿着路段前进或到达新路段)。类似地，如果TARGET没有被地图服务提供商正确地识别，则可以向用户提供根据当前地图数据不能到达TARGET且应当选择修正的TARGET目的地的警告。

一旦服务器充分地识别了START和TARGET位置，就可以使用最新地图版本生成路线。可以使用用于在起点和目的地之间的每个路段的成本函数基于最短路线来建立路线，目的是最小化用于最短路线的成本函数。虽然一些实施例可以找到在起点和目的地之间的最短路线，但是实施例可以可选地识别最快路线或花费最少时间量的路线。在计算最快路线时，可基于实时数据且可选地并入历史交通速度数据来使用沿着为所述路线考虑的每一路段的预期交通速度。以此方式，成本函数可用于在考虑沿着每一路线的交通的影响的同时建立在起点与目的地之间具有最低时间成本的路线。

一旦在START和TARGET之间建立了路线，服务器就可以向客户端提供异或稳定道路链路标识符的顺序列表，以便客户端用作起点和目的地之间的路线。

利用鱼骨惩罚的服务器侧路线计算

虽然路线生成的上述实施例建立了START和TARGET之间的最快时间或最低成本路线，但是本文描述的实施例也可以考虑偏离最快或最低成本路线的因素。请求路线的客户端可能想要来自服务器的交通感知最快路线。然而，客户端也可能有兴趣对于沿着将离开路线的路线的每条道路，在此被称为鱼骨，理解替代路线将花费多长时间。由于客户端和服务器可能在不同的地图版本上操作，使用简单的道路链路标识符来编码路线可能是不可行的，因为道路链路标识符需要在两个地图版本上解析。

根据这样的实施例，来自客户端的路线请求可以包括被编码为START_SEGMENT的中点和z水平的起点或START，以及被编码为TARGET_SEGMENT的中点和z水平的目的地或TARGET。客户端还可以在路线请求中向服务器发送START_SEGMENT和TARGET_SEGMENT的异或稳定标识符。根据本文描述的实施例，客户端还可以发送用于“鱼骨惩罚”的桶的数量“N”。

路线服务器将使用所提供的START和TARGET来在最新的地图版本中找到适当的道路链路，并且可以容忍中点中的几米的误差，并且使用z水平来进行平局决胜，如上所述。如果存在START和/或TARGET的多个候选，则服务器可以使用START_SEGMENT和TARGET_SEGMENT的异或稳定标识符来找到适当的道路链路。服务器可计算道路网络上的路线，其中从实时和历史交通模式计算路段遍历成本以估计当前行进时间。然后，路线服务器可以使用最新的地图计算START和TARGET之间的最快路线。可选地，如上所述，服务器可以计算最低成本路线，其可以与最快路线一致。可至少部分基于客户端偏好来建立提供到客户端的所识别的路线，所述客户端偏好例如为避开通行费、避开高速公路(包括高承载车辆(HOV)车道)等，因为这些偏好可影响路线选择。

对于路线中的每条道路链路，路线服务器可识别异或稳定链路标识符。然后，服务器可以将道路链路标识符序列作为服务器生成的路线发送到客户端。对于离开服务器提供的路线的每一路段，可计算服务器提供的路线与包括离开服务器提供的路线的段的路线之间的差。这被计算为离开服务器提供的到TARGET的路线的惩罚。这种偏离成为来自服务器提供的路线的鱼骨。

鱼骨中的段可以被分桶(bucketized)成“N”个桶，B_0到B_N。对于桶i＝0…N-1：将来自鱼骨的道路链路利用以分钟为单位的惩罚“D”添加到B_i，其中i<＝D

本文描述的实施例减少了地图版本之间的冲突，由此在第一版本的地图中生成的路线不能与第二版本的地图中的路线正确地相关，从而导致路线错误或不能生成路线。此外，通过仅从服务器向客户端发送中间点，可以最小化带宽，同时向客户端提供足够的信息以验证中间点之间的片段。执行类似任务的先前机制使用中点搜索匹配链路，其涉及计算密集的路线的所有链路的空间地图匹配搜索。使用本文描述的路线片段指纹的示例实施例，大大降低了现有方法的带宽和处理要求。

虽然上述实施例找到了起点和目的地之间的路线，生成异或稳定链路标识符的顺序列表，但是本文描述的实施例可以用于复杂度更高的路线。例如，路线可以包括必须沿着路线包括的路点。在这样的实施例中，除了对应于起点的START和对应于目的地的TARGET之外，还可以从客户端接收一个或多个STOP位置。这些路点可以被指定为“STOP_i”，其中“i”表示路线序列中的站点的编号。根据包括路点的实施例，START、TARGET和所有STOP_i可以被编码为START_SEGMENT、TARGET_SEGMENT和所有STOP_SEGMENT_i的中点和z水平。

包含路点的示例实施例与上述缺少路点的实施例类似，因为地图服务提供商116可以计算包含路点的路线。以这种方式，地图服务提供商116可以建立START和每个路点STOP_i之间的路线，表示为ROUTE_S_i。路线也可以在每个STOP_i和TARGET之间建立，表示为ROUTE_i_T。最后，可以在每个STOP_i和STOP_j之间建立路线(其中i不等于j)，表示为ROUTE_i_j。这在由客户端识别的每个点之间产生多条路线。

地图服务提供商116或其它路线服务器然后可以计算中间站点或路点的最佳顺序，使得从START到顺序中的第一站点、在顺序中的站点之间、以及从顺序中的最后站点到TARGET的总行进距离或总行进时间最小。然后使用计算的ROUTE。

可以基于使用用于起点和目的地之间的每个路段的成本函数的最短路径，在每对点(START、TARGET和STOP_i)之间建立路线，目的是最小化最短路径的成本函数。虽然一些实施例可以找到每对点之间的最短路线，但是实施例可以可选地识别最快路线或点之间花费最少时间量的路线。在计算最快路线时，可基于实时数据且可选地并入历史交通速度数据来使用沿着针对所述路线考虑的每个路段的预期交通速度。这样，可以使用成本函数来建立具有点之间的最低时间成本的路线，同时考虑沿着每条路线的交通影响。

无论使用最短距离、最短时间、避开高速公路或任何其它用于生成序列的参数，计算的序列可用于对STOP_i路点重新排序，以使STOP_i是序列中的第i个站点。这导致到达每个所需的路点或“旅行线路”的路线序列。旅行线路可以包括枚举为ROUTE_S_1,ROUTE_S_2,…,ROUTE_K_T的路线，以形成最佳旅行线路。该序列可以在对客户端的路线响应时提供，因此客户端基于客户端对路点的选择理解旅行线路中的中间路点的顺序。

本公开的上述示例实施例描述了将包括在路线或旅行线路路线中的明确目的地和路点。然而，根据本文描述的一些示例，实施例可包括提供路线到尚未被建立为明确目的地的潜在目的地。例如，用户可以在客户端装置上搜索区域内诸如餐馆之类的兴趣点。搜索的结果可以识别多个潜在目的地。虽然用户可能具有关于搜索结果的某些偏好，但是可能希望用户识别出到达各个兴趣点的路线和行进时间，以帮助用户做出完全明智的决定。

根据本文描述的示例，用户可以进行对一类兴趣点的搜索。可以返回多个搜索结果。可以以多种方式限制结果。搜索可以被限制在距用户一定距离处，搜索可以基于搜索参数来限制，并且可选地，搜索可以由最大数量的结果来限制。可以基于地图变得拥挤的数目或者用户被选项淹没的数目来建立该最大数量“K”的结果。无论如何，数量“K”可以是返回给用户的结果的最大数量。

示例实施例的地图服务提供商116可以使用所提供的起点或START来找到最新版本的地图上的适当的段。地图服务提供商可以容忍地图中几米的误差，将START与START_SEGMENT的路段的中点相匹配，并且使用z水平来打破可能在彼此之上或之下通过的道路之间的平局。如果地图服务提供商不能将START与START_SEGMENT匹配，则可以为用户生成用户的当前位置不对应于最新版本的地图的路段的警告，鼓励用户移动到可以用于与START_SEGMENT进行适当地图匹配的位置。

使用限于“K”个结果的搜索结果，地图服务提供商116或另一服务器可以运行算法以找到到搜索结果的最短路径。例如，服务器可以运行在START_SEGMENT开始的Dijkstra算法，其具有基于本公开的修改。每当所选择的算法扩展段S时，可以针对相应类别的兴趣点来检查段。如果在段S处找到所请求类别的一个或多个兴趣点，则段S的中点和z水平可以存储为POI_i。从START_SEGMENT到该兴趣点的最短路径ROUTE_i可以从Dijkstra的状态中提取。一旦找到K个兴趣点，算法可以停止。虽然描述了Dijkstra算法，但是可以使用产生到K个最近兴趣点的K条最短路径的任何类似算法。使用经修改的Dijkstra算法的益处在于其不返回N个蜂线最接近(bee-line-closest)(例如，直线最短距离)的兴趣点，而是返回K个行进时间最接近的兴趣点。

到不同兴趣点的每个上述潜在路线可以如上所述被生成为START_SEGMENT和相应兴趣点之间的异或稳定链路标识符的序列。该标识符列表提供了在每条路线的起点和目的地之间传送路线的简明、低带宽的方式。

客户端侧路线计算及解码/验证

如上所述，诸如地图服务提供商116的服务器可以生成路线作为提供给客户端的异或稳定道路链路标识符的顺序列表。将路线编码为用于客户端解码和解释的链路标识符的顺序列表允许以地图版本不可知的方式生成路线，同时将关键信息传达给客户端。

可以被实现为移动装置114(例如，蜂窝电话、平板计算机、导航装置等)或被实现为车载导航系统的示例实施例的客户端可以经由网络112与诸如地图服务提供商116及其处理服务器102的服务器通信。服务器向客户端提供异或稳定道路链路标识符的顺序列表。客户端可以对服务器进行一次或多次往返，以便重建异或稳定链路标识符的列表中由服务器提供的路线。路线可以包括起点和目的地之间的路线、起点和目的地之间的具有一个或多个路点的路线、或者起点和多个目的地(例如，兴趣点)之间的路线。服务器和客户端上的地图可能不同，从而可能发生不匹配。如果客户端检测到地图差异严重到其不能安全地重建路线，则客户端可以请求地图更新或者拒绝路线并请求不同的路线。

根据示例实施例，客户端可以将起点和目的地之间的路线请求发送到服务器，可选地包括用于与起点对应的START_SEGMENT和与目的地对应的TARGET_SEGMENT的异或稳定链路标识符。作为响应，客户端可以接收用于将起点连接到目的地的道路链路的异或稳定道路标识符的顺序列表。如果客户端检测到所提供的异或稳定链路标识符的序列不能与客户端侧地图上的道路链路的序列正确地相关，例如如果客户端侧地图中的链路标识符不是异或稳定的或者没有导致与服务器提供的链路匹配，则可以拒绝该路线。

如果拒绝该路线，则客户端可以请求服务器重新计算路线。在请求服务器重新计算路线时，客户端可向服务器提供客户端无法匹配到客户端侧地图中的道路链路的“不可匹配链路”。客户端可以使用服务器提供的异或稳定标识符向服务器提供不匹配链路，并且请求避开该不匹配链路的另一路线。这些可能变成用于路线生成的“禁止链路”。该处理可以被执行多于一次，其中客户端可以识别其请求服务器禁止所生成的后续路线的不可匹配链路。不可匹配链路可能相对不常见，使得此处理可能不被频繁实施。地图改变通常有点微不足道，并且仅非常少量的道路更新将破坏连通性，诸如当桥梁被拆除或为新的时，当高速公路立交改变模式时，或当建造新道路时。此外，在两个连续的路线中存在不可匹配链路的可能性相当小，并且通常不应干扰用户满意度。

当客户端接收到由可以在客户端处进行适当地图匹配的链路标识符的顺序列表所表示的路线时，客户端可以呈现一条或多条路线，并且开始到目的地、兴趣点或路点的导航。示例实施例的服务器(如地图服务提供商116)可以向客户端(如移动装置114)提供在距离或时间上或者根据其它客户端定义的偏好优化效率的一条或多条路线。当客户端请求起点和目的地之间的路线时，服务器可以提供一条路线，当客户端请求一个或多个路点时，提供路线序列，其中路线序列在起点和第一路点之间、在路点之间、以及在最终路点和目的地之间。服务器可以可选地提供多条路线，例如当对多个兴趣点进行搜索并且生成从起点到不同兴趣点中的每一个的路线时。

客户端侧路线重建

在客户端处的路线重构可以依赖于在路径上保存异或和的异或稳定链路标识符。在接收到服务器生成的异或稳定链路标识符的顺序列表形式的路线时，异或中的任何差异，客户端可以执行重构算法以解码所接收的路线。为了执行该算法，客户端可以执行以下：

-将RESULT设置为道路链路的空列表

-将CANDIDATES设置为包含START_SEGMENT的异或稳定链路标识符的单个元素

-调用DECODE(ROUTE，CANDIDATES)以解码路线

-如果结果为TRUE：提供沿该路线的路线引导

-如果结果为FALSE：拒绝路线

根据上述算法，客户端确定是否可以从异或稳定链路标识符的顺序列表中正确地解码路线。如果路线可以由客户端基于异或稳定链路标识符的顺序列表来解码，则可以开始沿着服务器提供的路线的路线引导。如果路线不能被解码，则拒绝服务器提供的路线。客户端侧解码子例程可以执行以下算法：

-FIRST＝ROUTE的第一元素

-如果CANDIDATES包含FIRST

ο向RESULT中添加由FIRST表示的段

ο从ROUTE中移除第一元素

ο令CANDIDATES现在包含与FIRST连接的所有链路的异或稳定链路标识符

ο RETURN DECODE(ROUTE,CANDIDATES)，以解码路线的剩余部分。

-否则如果DECODE_MERGE(ROUTE，CANDIDATES)为真：

οRETURN TRUE

-否则如果DECODE_SPLIT(ROUTE，CANDIDATES)为真：

οRETURN TRUE

-RETURN FALSE

上面详述的客户端侧解码子例程从客户端的本地地图中的路线识别第一元素或道路链路/段。如果本地地图版本包括与路线的第一元素相对应的标识符，则匹配该道路链路，并将其从服务器提供的路线的元素的列表中移除。从第一道路链路，标识异或稳定链路标识符的顺序列表中的元素列表，该异或稳定链路标识符对应于与第一元素连接的链路，并且只要在客户端处在地图版本内找到服务器提供的链路标识符，就继续解码路线。如果在客户端地图版本中没有找到来自服务器的路线的道路链路标识符，则DECODE算法根据需要进入子算法DECODE_MERGE和DECODE_SPLIT，以分别确定是否由于道路链路合并或分割而在客户端侧地图版本中没有找到链路。

解码道路链路的合并如图3所示发生，其中旧版本的地图可以包括道路链路A，并且新地图版本包括道路链路B和C，其中添加了节点306和道路链路D。运行DECODE_MERGE子算法以查看是否可以合并路线的第一和第二道路链路元素，以通过将异或函数应用于路线的第一和第二道路链路来找到地图的客户端侧版本上的道路链路，从而将路线的第一和第二道路链路与地图的本地版本中的已知道路链路本地相关。注意，“路线的第一和第二路径链路”不一定包括START_SEGMENT，因为DECODE算法从顺序列表中移除道路链路元素，因为它们被本地客户端侧版本的地图确认。以此方式，DECODE算法继续通过顺序列表以将路线的每一道路链路与本地地图版本相关。DECODE_MERGE子算法可以如下进行：

-FIRST,SECOND＝来自服务器的ROUTE的第一和第二道路链路元素

-从ROUTE中移除第一元素和第二元素

-将XOR(FIRST,SECOND)添加到ROUTE的开始

-RETURN DECODE(ROUTE，CANDIDATES)

该处理将识别被分割成两个道路链路的道路链路，如图3所示。在异或函数中使用路线的第一和第二道路链路元素来替换路线的第一和第二道路链路元素，然后返回到上述DECODE算法，其中客户端确定异或的第一和第二道路链路元素是否在客户端侧版本的地图上被识别。如果是，则DECODE算法继续。

如果DECODE_MERGE子算法没有识别出客户端侧地图版本中被分割成服务器侧路线的两条道路链路的道路链路，则可以执行第二子算法以确定客户端侧地图版本中的道路链路是否被合并成服务器侧路线的另一连续路段。可以运行DECODE_SPLIT子算法以确定这是否发生。该子例程通过枚举CANDIDATES的异或稳定链路标识符及其连接的链路并对它们应用异或函数，来检查来自服务器提供的ROUTE的第一(即下一个)道路链路元素是否对应于两个本地连接的道路链路元素。子算法如下进行：

-初始化新的空集CANDIDATES2

-对于CANDIDATES中的每个CANDIDATE：

ο对于与CANDIDATE连接的每个链路的异或稳定链路标识符：

将XOR(CANDIDATE，ID)添加到CANDIDATES2

-RETURN DECODE(ROUTE,CANDIDATES2)

上述DECODE_SPLIT子算法使用服务器提供的路线中的下一个候选以及异或函数中的路线中的后续道路链路元素，以确定组合的那些道路链路是否对应于客户端的单个道路链路。如果是，则子算法已经匹配了路线的该部分，并且返回到DECODE算法以继续进行将服务器提供的路线的下一道路链路元素匹配到客户端侧地图。

利用鱼骨惩罚的客户端侧路线计算和解码/验证

根据示例实施例，其中由客户端请求路线且其有兴趣针对沿着将离开路线的路线的每条道路，在此被称为鱼骨，理解替代路线将花费多长时间。由于客户端和服务器可能在不同的地图版本上操作且如上所述，使用简单的道路链路标识符来编码路线可能是不可行的，因为道路链路标识符需要在两个地图版本上解析。客户端可以提供数字“N”以从服务器接收鱼骨作为在从零到N的桶中的并且至少N分钟的异或稳定链路标识符。路线服务器将以异或稳定链路标识符的顺序列表进行响应，异或稳定链路标识符表示服务器地图中的交通感知最快或成本最低的路线。此外，当请求包括鱼骨惩罚的路线时，服务器可以向桶B_0至B_N发送来自服务器地图的异或稳定链路标识符。

客户端可以执行如上所述的路线解码，初始地将RESULT设置为段的空列表，并将CANDIDATES设置为包含START_SEGMENT的异或稳定链路标识符的单个元素。然后，使用如上所述的DECODE(ROUTE,CANDIDATES)来调用DECODE算法。当结果是合法路线时，则提供路线以用于导航辅助或路线引导。如果算法的结果是错误，则拒绝该路线。路线的解码可以包括上述合并和分割子算法。

虽然可以如上所述执行路线的解码而不考虑鱼骨惩罚，但是当采用鱼骨惩罚考虑时，可以执行路线的附加处理。为了解码鱼骨，可以采用以下算法：

-针对ROUTE的路线中的每个SEGMENT

ο将不是ROUTE的一部分的离开SEGMENT的所有连接链路的异或稳定链路标识符添加到CANDIDATES

-CANDIDATES现在包含离开ROUTE的所有链路的集合

-针对每个桶B_0…B_N中的每个异或稳定链路标识符：

ο尝试利用DECODE算法本地查找链路标识符

ο如果RESULT＝DECODE(ID,CANDIDATES)不是“ERROR”

则将RESULT中的第一元素的相应段添加到至其桶所引用的惩罚的FISHBONE映射。

用于建立上述鱼骨惩罚的这种算法基本上使用上述解码算法来建立每个鱼骨桶或分支远离主路线的路径。这使得路线引导或导航辅助能够向用户识别偏离路线的额外时间惩罚。偏离路线的道路链路可以用相对于原始路线的到达时间延迟来注释。当用户沿着路线以各种方式行进时，可以向用户呈现该信息。例如，可以在显示器上向用户呈现替代路线，其中添加的时间延迟叠加在该路线上。可选地，时间惩罚可以响应于自然语言问题而被传达给用户。例如，用户可以发出“如果我现在右转还要走多久？”的请求。路线引导可以提供文本或自然语言响应，其指示“它将花费五分钟。”。

基于路线偏离提供给用户的额外信息可向用户提供探索到其目的地的其它路线同时理解其将招致的延迟的额外自由。这允许用户在以通知的结果决定到其目的地的替代路线时权衡其选项。

使用上述技术，客户端基于为起点和目的地之间的道路链路建立的异或稳定链路标识符递归地尝试将生成的路线与服务器生成的路线进行匹配。在这种情况下，地图可以是不同版本，因为客户端试图将具有异或稳定标识符的道路链路与可以在服务器侧地图中合并或分割的道路链路进行匹配，但是继续异或稳定标识符，使得地图版本不需要完全匹配。

本文描述的实施例的结果是客户端中的有效路线，因为算法中的规则仅遍历合法策略。该算法通过仅询问关于其中异或稳定链路不能在地图版本之间相关的片的细节来最小化客户端与服务器通信并因此最小化带宽。示例实施例的算法发现需要地图更新的区域，并且如果用户不想更新地图，或者如果他们处于较差信号接收的区域中，由此地图更新是不实际的，则算法可以提供后退。

无论客户端是对从起点到目的地的单条路线、起点和多个兴趣点中的每一个之间的多条路线进行解码，或路线是否是路点之间的路线序列，路线的客户端侧解码可以基本上相同。

图8是示出根据本发明的示例实施例的方法的流程图。将理解，流程图的每个框和流程图中框的组合可以通过各种装置来实现，诸如硬件、固件、处理器、电路系统和/或与包括一个或多个计算机程序指令的软件的执行相关联的其它通信装置。例如，上述过程中的一个或多个可以由计算机程序指令来实现。在这点上，实现上述过程的计算机程序指令可以由采用本发明实施例的设备的存储器装置204存储，并且由该设备的处理器202执行。如将理解的，任何这样的计算机程序指令可以被加载到计算机或其它可编程设备(例如，硬件)上以产生机器，使得所得到的计算机或其它可编程设备实现流程图方框中指定的功能。这些计算机程序指令还可以存储在计算机可读存储器中，该计算机可读存储器可以引导计算机或其它可编程设备以特定方式工作，使得存储在计算机可读存储器中的指令产生一种制品，该制品的执行实现流程图方框中指定的功能。计算机程序指令还可以被加载到计算机或其它可编程设备上，以促使在计算机或其它可编程设备上执行一系列操作，以产生计算机实现的过程，从而在计算机或其它可编程设备上执行的指令提供用于实现流程图的块中指定的功能的操作。

因此，流程图的框支持用于执行指定功能的装置的组合以及用于执行指定功能的操作的组合，以执行指定功能。还将理解，流程图的一个或多个框以及流程图中的框的组合可以由执行指定功能的基于专用硬件的计算机系统或者专用硬件和计算机指令的组合来实现。

图8示出描述基于来自不同版本的地图的编码的道路链路和解密的道路链路来生成路线的方法的流程图。在410，提供在起点与目的地之间的路线请求的指示。在420，响应于路线请求接收道路链路标识符列表。在430，识别列表的第一道路链路标识符。在440，确认列表的第一道路链路是否对应于道路链路标识符网络的道路链路标识符。如果存在对应关系，则在450，将第一道路链路标识符添加到路线。在460，从列表中移除该道路链路标识符，因为它现在是确认的路线的一部分，并且确定该列表是否包括任何附加的链路标识符。如果是，则该方法返回到430以识别该链路。如果在440，第一道路链路标识符不对应于道路链路标识符网络的道路链路标识符，则表示客户端不能在其版本的地图上找到该链路。在470，将异或函数应用于列表中的第一道路链路标识符和随后的道路链路标识符。如果应用于第一道路链路标识符和随后的道路链路标识符的异或函数对应于道路链路标识符网络中的道路链路标识符，则在480，进行路线和客户端版本的地图之间的对应关系。方法返回到460，其中，确认路线是否包括列表中的任何附加链路。如果不是，则在490，在道路链路标识符网络内建立路线，因为该方法能够将列表的所有链路与客户端处的地图版本的链路标识符相关。

在示例实施例中，用于执行上述图8的方法的设备可以包括处理器(例如，处理器202)，其被配置为执行上述操作(410至490)中的一些或每一个。处理器例如可以被配置成通过执行硬件实现的逻辑功能和/或执行用于执行每个操作的存储指令来执行操作(410至490)。可替代地，所述设备可包括用于执行上述操作中的每一者的装置。就这一点而言，根据示例实施例，用于执行操作410至490的装置的示例可以包括例如处理器202和/或用于执行如上所述的用于处理信息的指令的装置或电路。

受益于在前述描述和相关附图中呈现的教导，本发明所属领域的技术人员将想到本文阐述的本发明的许多修改和其它实施例。因此，应当理解，本发明不限于所公开的具体实施例，并且修改和其它实施例旨在包括在所附权利要求的范围内。此外，虽然前面的描述和相关联的附图在元件和/或功能的某些示例性组合的上下文中描述了示例性实施例，但是应当理解，在不脱离所附权利要求的范围的情况下，可以通过替代实施例来提供元件和/或功能的不同组合。在这方面，例如，与上文明确描述的那些不同的元件和/或功能的组合也被预期为可以在所附权利要求中的一些中阐述。尽管在此使用了特定术语，但是它们仅在一般和描述性意义上使用，而不是为了限制的目的。