巨型网络上的距离查询

摘要

提供了对规模为大型和巨型网络的网络结构稳健并且是快速、直接和高效的距离查询技术。描述了用于确定网络上的两个节点或顶点之间的距离的分层枢纽标记(HHL)技术。该HHL技术通过依据重要性对顶点进行排序，随后将该排序变换成索引来提供索引，这允许快速的确切最短路径距离查询。索引可被压缩，而不牺牲其正确性。

说明书

背景

以图回答点对点距离查询是诸如社交网络、搜索、生物计算、计算机网络和道路网络之类的域中的许多应用的基础构建块。虽然距离查询可通过归因于Dijkstra的公知方法以几乎线性的时间回答，但在大型图上，这可花费若干秒。这对于可能需要运行上千或甚至上百万的距离查询的大多数应用而言太慢了。出于这个理由，在更高效技术的设计中已存在稳定进程。通用方法是从输入图构建索引以使加速在线查询。对于复杂的网络，确切算法和近似算法两者都已被开发。

作为一示例，在道路网络上，大多数新近算法都是确切的。被称为道路映射程序的现有计算机程序提供数字地图，通常拥有直到城市-街道级别的详尽道路网络。典型地，用户可以输入一个位置，并且道路映射程序将显示所选位置的屏上地图。几个现有的道路映射产品通常包括计算两个位置之间最佳路线的能力。换句话说，用户可以输入两个位置，并且道路映射程序将计算从源位置到目的地位置的行进方向。方向通常基于距离、行进时间和某些用户偏好，诸如用户喜欢用来驾驶的速度、或者沿着该路线的风景程度。计算各位置之间的最佳路线可能要求大量的计算时间和资源。

一些程序使用Dijkstra方法的变体来计算最短路径。注意，在此意义上，“最短”意味着“最低成本”，因为每一段(例如，道路段)都被分配了成本或权重，该成本和权重不必与该段的长度直接相关。通过改变计算每一段的成本的方式，可以为最快、最短或偏好的路线生成最短路径。然而，由于被扫描的位置和可能路径的数目大，Dijkstra的原始方法在实际应用中也不总是有效。相反，许多公知程序使用Dijkstra方法的试探变体。

较新近的开发利用包括预处理阶段和查询阶段的双阶段过程。在预处理阶段期间，图或地图经历离线处理，使得稍后的在图上的任意两点(例如，目的地)之间的实时查询可被更高效地作出。已知的预处理算法的示例使用几何信息、分层分解以及A*搜索。

虽然存在专用于一些类型的输入的许多技术，但这些技术对于规模为大型或巨型且为快速、直接和高效的网络结构而言都不稳健。

概述

提供了对规模为大型和巨型网络的网络结构稳健且为快速、直接和高效的距离查询系统和方法。描述了分层枢纽标记(HHL)技术。在一实现中，该HHL技术通过依据重要性对各顶点进行排序，随后将该排序变换成索引(标记)来提供索引，这允许快速、确切的最短路径距离查询。在一实现中，索引可被压缩，而不牺牲其正确性。

在一实现中，包括多个顶点的图被接收作为计算设备处的输入。针对该图的每一顶点的多个标记被计算设备生成，其中对于每一顶点，每一标记包括被称为枢纽的顶点的集合以及在该标记中的各枢纽与该顶点之间的距离两者。分层枢纽标记处理被执行以生成标记，对应于顶点和标记的数据作为经处理的图数据被存储在与该计算设备相关联的存储中。经处理的图数据可响应于后续查询被使用，以确定网络(例如，与社交网络、搜索、生物计算、计算机网络和/或道路网络相关联的巨型网络上)的两个节点(或顶点)之间的距离。

在一实现中，执行分层枢纽标记处理包括：确定图中的顶点的次序，基于该次序来确定索引，以及可选地对索引执行压缩以降低索引的尺寸。

在一实现中，确定巨型网络上的两个节点(或顶点)之间的距离包括：在计算设备处对包括多个顶点和弧的图进行预处理以生成经预处理的数据，经预处理的数据包括针对该图的每一顶点的多个标记，其中对于每一顶点，每一标记包括顶点集合以及该顶点集合中的顶点与该顶点之间的距离，其中该预处理包括确定该图中的顶点的次序，以及基于该次序来确定索引。查询在计算设备处被接收，并且源顶点和目的地顶点由计算设备基于该查询来确定。计算设备对经预处理的数据执行与源顶点和目的地顶点有关的距离计算以确定源顶点和目的地顶点之间的距离，并输出该距离。

提供本概述以便以简化的形式介绍将在以下的详细描述中进一步描述的一些概念。本概述并不旨在标识出所要求保护的主题的关键特征或必要特征，也不旨在用于限定所要求保护的主题的范围。

附图简述

当结合附图进行阅读时，可以更好地理解以上概述以及以下对说明性实施例的详细说明。出于解说各实施例的目的，在附图中示出各实施例的示例构造；然而，各实施例不局限于所公开的具体方法和手段。在附图中：

图1示出了其中各方面和各实施例可能被利用的计算环境的示例；

图2是使用标记技术来确定两个位置(诸如两个节点或两个顶点)之间的最短路径的长度的方法的实现的操作流程；

图3是使用分层枢纽标记技术来对要在后来接收到的距离查询中使用的数据进行预处理的方法的实现的操作流程；

图4是使用可用于确定两个位置之间的距离的基于枢纽的标记技术的方法的实现的操作流程；

图5是使用可用于大得多的图的涉及采样和估计的基于枢纽的标记技术的方法的实现的操作流程；

图6是使用增量表示技术来进行标记压缩的方法的实现的操作流程；

图7是使用高级重排序技术来进行标记压缩的方法的实现的操作流程；

图8是使用掩码令牌来实现标记压缩的方法的实现的操作流程；以及

图9示出了一示例性计算环境。

详细描述

图1示出了其中各方面和各实施例可能被利用的计算环境的示例。计算设备100包括便利于在通信介质上通信的网络接口卡(未具体示出)。示例计算设备包括个人计算机(PC)、移动通信设备等。在一些实现中，计算设备100可以包括台式个人计算机、工作站、膝上计算机、PDA(个人数字助理)、智能电话、蜂窝电话或任意启用WAP的设备或能够直接或间接与网络对接的任意其它计算设备。例如，相对于图9的计算设备900描述了一个示例的计算设备100。

计算设备100可以通过物理连接与局域网102通信。或者，计算设备100可以通过无线广域网或无线局域网介质或通过其它通信介质与局域网102通信。虽然被示为是局域网102，但网络可以是包括公共交换电话网络(PSTN)、蜂窝电话网络(例如3G、4G、CDMA等)以及分组交换网络(例如因特网)的各种网络类型。任何类型的网络和/或网络接口都可用于网络。

作为所支持的网络介质的结果，计算设备100的用户能通常通过使用在计算设备100上运行的浏览器应用104来访问网络资源。浏览器应用104促成通过例如因特网105与远程网络的通信。一个示例性网络资源是在查询处理服务器108上运行的查询处理服务106。查询处理服务器108托管节点(在一些实现中也可被称为顶点)的数据库110，涉及诸如社交网络、搜索、生物计算、计算机网络和道路网络之类的领域以及所存储的节点或节点之间的关系。

计算设备100的用户通常通过浏览器应用104输入起始和目的地节点(或例如位置、顶点、或两个点)作为查询请求。查询处理服务器108接收该请求，并产生存储在数据库110中的节点或顶点之间从起始节点(或顶点)到达目的地节点(或顶点)的距离(即，确切距离)。查询处理服务器108随后将那个确切距离发送回给作出请求的计算设备100。替换地，查询处理服务106被托管在计算设备100上，并且计算设备100不需要与局域网102进行通信。

点对点(P2P)最短路径问题是许多应用的典型问题。在给定具有非负弧长度以及顶点对(s,t)的图G的情况下，目标是找到从s到t的距离，即从s到t的最短路径的长度。例如，该图可表示道路地图。例如，道路网络中的路线规划解决该P2P最短路径问题。然而，存在对解决该P2P最短路径问题的算法的许多使用，并且本文中描述的技术、过程和系统不旨在限于地图，而可被用于任何大型或巨型网络，诸如社交网络、搜索、计算生物学、计算机网络和道路网络。

由此，解决P2P最短路径问题的P2P算法旨在找到图中的任何两个点之间的最短距离(或确切距离或其他距离，这取决于实现)。这样的P2P算法可包括若干阶段，包括预处理阶段和查询阶段。预处理阶段可取有向图作为输入。这样的图可通过G＝(V,A)来表示，其中V表示该图中的顶点的集合，并且A表示该图中的边或弧的集合。该图包括若干顶点(点)以及若干边。预处理阶段可例如用于改善稍后的查询阶段的效率。

在查询阶段期间，用户可希望找到两个特定节点之间的最短路径。始发节点可被称为源顶点(被标记为s)，而目的地节点可被称为目标顶点(被标记为t)。例如，P2P算法的应用可以是找到道路地图上的两个位置之间的最短距离。地图上的每一目的地或交点可由节点之一来表示，而具体的道路和公路可由边来表示。用户可随后指定其起始点s和其目的地t。

由此，为了可视化并实现路线制定方法，将位置和连接段表示为具有顶点和有向边的抽象图是有帮助的。在该示例中，顶点对应于位置，并且边对应于各位置之间的道路段。边可根据行进距离、经过时间和/或关于对应道路段的其他准则来加权。通用术语“长度”和“距离”在上下文中用于涵盖用于测量边的权重或成本的度量。路径的长度或距离是该路径中包含的各边的权重之和。对于通过计算设备的操纵，图可作为记录的集合被存储在计算机存储器的连续块中，每一记录表示单个图节点(顶点)或边以及相关联的数据。

标记技术可在点对点最短路径的确定或任何其他距离查询(诸如大型或巨型网络上的距离查询)中被使用。图2是使用标记技术来确定两个位置(例如，两个节点或两个顶点)之间的最短路径的长度的方法200的实现的操作流程。顶点v的标记是顶点v存储其距离的枢纽集合。标记使得任何两个顶点s和t共享最短s-t路径上的至少一个枢纽。

在预处理阶段期间，在210，该标记方法为每一顶点v确定前向标记L_f(v)和反向标记L_r(v)。每一标记包括顶点w的集合以及顶点w从顶点v起的(在L_f(v)中)或到顶点v的(在L_r(v)中)相应距离。由此，前向标记包括顶点w的集合以及各顶点w距v的相应距离d(v,w)。类似地，反向标记包括顶点u的集合，每一顶点u具有其到v的距离d(u,v)。如果标记具有对于每一对顶点s和t，L_f(s)∩L_r(t)包含在从s到t的最短路径上的顶点u(即，对于每一对不同的顶点s和t，L_f(s)和L_r(t)都包含在从s到t的最短路径上的公共顶点u)的覆盖属性，则该标记是有效的。

在查询时间，在220，用户(例如使用计算设备100)分别输入起始和目的地位置(或，网络或图上的两个点、顶点或节点)即s和t，并且在230，查询(例如，涉及该s和t顶点的信息)被发送给查询处理服务(例如，查询处理设备106)。s-t查询是在240处通过找到使距离(dist(s,u)+dist(u,t))最小化的顶点u∈L_f(s)∩L_r(t)来处理的。在250相应的路径被输出给用户作为最短路径或距离。

在一实现中，标记技术可使用基于枢纽的标记。回想P2P最短路径算法的处理阶段可取图G＝(V,A)作为输入，其中|V|＝n，|A|＝m并且对于每一弧a，长度>0G中的路径P的长度为其弧长度之和。最短路径算法的查询阶段取源(或起始)s和目标(或目的地)t作为输入，并返回它们之间的距离dist(s,t)，例如图G中的源s和目标t之间的最短路径的长度。如上所述，该问题的标准解决方案是Dijkstra算法，该算法以从源s起的距离递增的次序处理各顶点。对于每一顶点v，其保持至此找到的最短s-v路径的长度d(v)以及该路径上顶点v的前导者(也被称为父)p(v)。最初，对于所有其他顶点，d(s)＝0,d(v)＝∞，并且对于所有v，p(v)＝空。在每一步骤，具有最小d(v)值的顶点v被从优先级队列中提取出，并被扫描：对于每一弧(v,w)∈A，如果则设定并且p(v)＝w。当目标t被提取出时，该过程终止。

基于枢纽的标记技术可使用各种技术来改进，诸如包括排序的分层枢纽标记和压缩。

由此，综上所述，到距离查询问题的输入是采用以下正长度函数的有向图G＝(V,A)：A→R+,其中n＝|V|且m＝|A|。从顶点v到顶点w的最短路径(或距离)的长度由dist(v,w)来表示。距离查询取一对顶点(s,t)作为输入，并输出dist(s,t)。

标记算法对该图进行预处理以计算每一顶点的标记，使得s–t查询可仅使用s和t的标记来回答。已知的枢纽标记算法可与每一顶点v的以下两部分标记L(v)一起使用：前向标记L_f(v)和反向标记L_r(v)。对于无向图，仅这些标记之一满足。前向标记L_f(v)包括一系列对(w,dist(v,w))，其中w∈V；类似地，L_r(v)具有对(u,dist(u,v))。顶点w和u被称为v的枢纽。为了简化符号，各标记可被解释为枢纽集合；符号v∈L_f(u)由此意指标记L_f(u)包含对(v,dist(u,v))。前向或反向标记的尺寸(由|L_f(v)|或|L_r(v)|表示)是其包含的枢纽的数目。标记是所有顶点v∈V的所有标记的设置。图的平均标记尺寸是标记中的枢纽的数目除以标记的数目(对于无向图的情况其为n，而对于有向图的情况其为2n)。标记遵守覆盖属性：对于任何两个顶点s和t，集合L_f(s)∩L_r(t)包含在最短s-t路径上的至少一个枢纽v。

在给定这些标记的情况下，枢纽标记查询是直接的：为了找到dist(s,t)，找到使dist(s,v)+dist(v,t)最小化的枢纽v∈L_f(s)∩L_r(t)。如果每一标记中的条目依据枢纽ID来排序，则这可通过两个标记上的协同扫掠来完成。不必假设最短路径是唯一的；为了避免混淆，引用对[u,w]而非路径u–w。如果dist(u,v)+dist(v,w)＝dist(u,w)，即如果至少一个最短u–w路径包含v，则顶点v覆盖(或命中)对[u,w]。注意，对于有向图，对被排序，即[u,v]不与[v,u]相同。

枢纽标记技术可在使用分层枢纽标记(HHL)技术后被改善，分层枢纽标记(HHL)技术中的一些在本文中被描述。图3是使用HHL技术来对要在后来接收到的距离查询中使用的数据进行预处理的方法300的实现的操作流程。方法300可由查询处理服务器和/或服务(诸如包括查询处理服务106的查询处理服务器108)来执行。

在310，在预处理阶段期间，例如从存储或从用户处获得图。在320，该图中的顶点的次序是针对输入图使用本文中进一步描述的技术计算或以其他方式确定的。在330，该次序被用于计算或确定将在后来接收到的距离查询中使用的索引(标记)。在340，可选的压缩步骤(各技术在本文中被进一步描述)减少了该索引的空间消耗。该索引在350被存储在存储中，并在对后来接收到的距离查询(诸如巨型网络上的确切距离查询)的处理中被使用。

更具体地，在给定标记的情况下，如果w是L(v)的枢纽，则令如果是局部有序，枢纽标记被定义为分层的。直观地，如果w比v“更重要”，则在该意义上，v可知道w，但反过来并不如此。用于寻找标记的神经试探法产生分层的标记。

已示出，在给出关于各顶点的排序排名(·)的情况下，可使用对各算法的某选择，在多项式时间内计算出与该排序一致的最小HHL。这一规范的标记具有以下属性：当并且仅当存在w使得v是覆盖[u,w]的最高排名的顶点时，顶点v才属于L_f(u)。类似地，仅当存在u，使得v是覆盖[u,w]的最高排名的顶点时，顶点v才属于L_r(w)。

关于如上所述被变换为分层标记的排序，寻找出良好排序(即，导致小标记的排序)现在被描述。在一实现中，基本算法贪婪地定义该次序。该方法将命中图中最多最短路径的顶点选为最高排名的顶点。一般来说，第i个最高排名的顶点(枢纽)是命中最多先前未覆盖的路径(即，没有被已经选取的i-1个枢纽覆盖)的顶点。

图4是使用可用于确定两个位置、节点或顶点之间的距离的基于枢纽的标记技术的方法400的实现的操作流程.方法400可由查询处理服务器和/或服务(诸如包括查询处理服务106的查询处理服务器108)来执行。

方法400在410通过构建n个完整的最短路径树(即以该图中的每一顶点为根的树)开始。以起始或源节点s为根的树T_s表示从s开始的所有未覆盖的最短路径。这假设最短路径是唯一的(并且由这些树给出)：在该算法内，仅T_s中的s-t路径上的顶点可覆盖对[s,t]。

在420，确定顶点v在T_s中的派生的数目，该数目对应于包含v的从s开始的未覆盖的最短路径的数目。在430，确定v在所有树上的派生的数目之和(由σ(v)表示)，该和对应于在顶点v被选为次重要的枢纽的情况下将命中的最短路径的总数。

在440，处理以针对每一顶点运行的迭代继续。该算法的每一迭代选取顶点v*作为下一枢纽，针对顶点v*的σ(v*)为最大值。为了准备好下一迭代，该算法从每一树中移除以v*为根的子树，并更新v*的所有派生和先辈的σ(·)值。更具体地，在440，选择使值σ(v*)最大化的顶点v*。在450，将v*添加到相关标记。在460，从每一树中移除以v*为根的子树，更新其派生的σ值。处理返回到440。

图5是使用可与大得多的图一起使用的涉及采样和估计的基于中枢的标记技术的方法500的实现的操作流程。方法500在510处通过从图中的k个顶点的随机样本构建k<<n个完整的最短路径树开始。以起始或源节点s为根的树T_s表示从s开始的所有未覆盖的最短路径。这假设最短路径是唯一的(并且由这些树给出)：在该算法内，仅T_s中的s-t路径上的顶点可覆盖对[s,t]。在520，确定顶点v在T_s中的派生的数目作为包含v的从s开始的未覆盖的最短路径的数目。

在530，计算v在样本中的所有树上的派生的数目之和(由σ’(v)表示)。采样被用来计算关于σ(·)值(在所有树上的派生的总数)的这些估计σ’(·)，从而节省了时间和空间。这些估计对于将重要的顶点(即其σ(·)为大的那些顶点)与不重要的顶点区分开而言足够精确。一旦顶点被选取(在一实现中，这可使用优先级队列高效地完成)，计数值可被更新，其中顶点从采样树中被移除。对于一些图类，这给出了合理的结果，但当k为小之时会引起一些问题。估计对于非常重要的顶点(在大多数树中具有许多派生)相当准确，而对于越不重要的顶点则越不准确。随着采样树变得越来越小，没有足够的信息来评估较不重要的顶点。因此，σ’(v)确切地计数v在构建的树中有多少派生。σ’(v)被用来估计σ(v)，σ(v)是在所有树(包括没有被构建的那些树)上的派生的总数。换言之，一些树被构建以估计在所有树(包括没有被构建的那些树)中的派生的数目。

这可通过随着该算法在540处理而生成更多的树来解决。这些是最短路径树，但不必是完整的：其可排除在该算法的先前迭代中已经被选为枢纽的顶点的派生。这节省了时间和空间。在一实现中，可使在树生成上所花费的工作与将枢纽添加到标记所花费的工作大略平衡。令c_t为在种新树时扫描的弧和触摸的枢纽的总数(原始的k个树是自由的)；对于标记生成期间的操作，类似地定义c_l。在确定排序中的下一顶点之前，检测c_t<βc_l是否满足；如果如此，则从尚未为选取的随机根生成新树，直到c_t超过βc_l。输入参数β控制标记计算和树生成之间的平衡(例如，使用β＝1，但可取决于实现使用任何值)。此外，维护至少一个树，并且为了保持有限的空间使用，在所有树上的顶点的总数超过γkn的情况下(甚至在c_t<βc_l的情况下)，不要生成新树。作为示例，将γ设置到10，但是在由例如管理员或用户设置时可使用任何值。

在一实现中，对于大型和小型树，可使用不同的表示。(例如，具有至少n/8个顶点的)大型树被表示为尺寸为n的阵列；第i个位置包含顶点i的父，或者在该节点不在树中的情况下为空。每一较小的树被表示为将每一顶点与其父相关联的散列表；不在该树中的顶点不出现在该表中。注意，同一树可随着其在算法期间缩小而切换表示。

样本中的派生的总数可被用来估计在所有n个树上的总数。虽然这看似自然，但此估计值的方差可能很高。具体地，它可严重地过高估计在树之一的根处(或附近)的顶点的重要性。碰巧成为样本树的根的一不重要顶点，将表现为覆盖比其真正覆盖的多得多的路径。这可通过用更鲁棒的测量(诸如中值或任何固定的百分位数)替换该和(或平均)来补救。

在一实现中，取代维护每一顶点v的单个计数σ’(v)，对于某个常数c，维护c个计数σ’₁(v),σ’₂(v),...,σ’_c(v)。计数值σ’_i(v)是v在所有树t_j上的派生的数目之和，使得i＝(j模数c)注意，t_j是样本中的第j个树，而非以j为根的树。当新树被添加或子树被移除时，这些计数值可被更新。这些计数值可被用来在评估v的质量时消除异常值。一种方法是丢弃使σ_i(v)最大化的计数值，并取剩余计数值的平均值为估计值。此处以下直觉是直接的：如果v接近一个树的根，则仅一个计数值将受影响。一般来说，根据顶点来增加计数值的数目c会导致更小的标记，但会增加预处理时间，因为顶点的优先级是通过考虑所有c个计数值来评估的。

使用以上描述的技术，各种各样的图类的小标记可被快速确定。然而，在一些实例中，用于维护这些标记的空间可能是大的。现在描述用于紧凑地表示它们的实现。压缩可被使用，例如以独立地表示每一标记，但使用更少的位来表示其元素(例如，距离或ID)中的每一者。描述了实现甚至更低的空间使用而无需牺牲查询时间的技术。

对于基本压缩，每一标记L_f(u)可被看作对(v,dist(u,v))的阵列。首先表示所有枢纽随后(以相同的次序)表示相应的距离可能是有利的。由于在枢纽匹配时，各查询仅考虑距离，因此这可省去一些高速缓存未命中。节省空间的一种方式是使用更少的位来表示枢纽ID和距离。在一实现中，距离可取决于输入用8、16或32位来表示。

关于枢纽ID，典型方法使用32位来表示大多数枢纽ID，但仅8位用于枢纽0到255。虽然这表示所有n个枢纽中的非常小的部分，但枢纽可被重命名，使得ID0到255被分配给最重要(较高排名)的顶点。在道路网络上，每一标记中的顶点的大部分在该集合中。空间被减小了约10％，并且查询变的更快。描述了该方法的修改(包括增量表示和高级重排序)以使得其对更大范围的实例更有效。

图6是使用增量表示技术来进行标记压缩的方法600的一实现的操作流程。在该实现中，枢纽ID以不同的形式被存储在标记中。在610，获得标记群组中的一标记。可选地，取决于实现，在615，重命名顶点，如以下进一步描述的。在620，确定该标记的各枢纽的标识符(ID)。对于具有k个枢纽的标记，令其ID为h₁<h₂<...<h_k。在630，显式地存储ID>1，而对于每一i>1，存储Δ_i＝h_i–h_i-1–1。这允许表示1到256的差值。在640，对标记群组中的另一标记继续620处的处理。

通过这种方式，例如，具有枢纽(0 16 29 189 299 446 529)的标记被表示为(015 12 159 109 146 82)。由于查询总是按次序反转各标记，因此h_i可作为Δ_i+h_i-1+1被检索。由于Δ_i<h_i，这增加了可用更少的位表示的入目的范围。在以上示例中，8位满足所有条目。为了保持各条目是直接的，避免可变长度编码。相反，使用8位和32位表示将标记分割成两个块。一旦8位块被完成，对该标记的剩余部分使用32位。

另一技术是对顶点进行重命名以利用增量表示。直观地，可用8个位表示的枢纽条目的数目被最大化。一种方法是依据排名或依据频率来对各枢纽进行重排序，其中越小的ID被分配给在越多标记中出现的枢纽。

在一实现中，高级重排序技术可被用于该增量表示。图7是使用高级重排序技术来进行标记压缩的方法700的一实现的操作流程。

在710，一次性将ID 0分配给最频繁的顶点(在最多标记中出现的顶点)，并将各附加ID分派给一个顶点。在720，对于仍未分配的每一顶点v，令s(v)为其中v可用8位表示的标记的数目，假定v被给予最小可用ID。最初，s(v)是包含v的标记的数目，但其值可随着该算法进展而减小，因为更少的ID保持可用。

在730，运行多个迭代，其中每一迭代选取具有最大的s(v)值的顶点v，并将ID分配给它。如果多个可用ID同等地好(即，实现s(v))，则向v分配其中的最大ID，从而为其他顶点节省较小的ID。具体地，次频繁的顶点可具有1和256之间的任何ID，并且仍被表示为8位，因此将ID 256分配给它。

更具体地，对于每一标记L(前向或反向(即，后向))，令其水平h(L)为可向L中的枢纽分配并且仍用8位来表示的最大ID(这是已经在L中的最后一个8位条目的ID加上256)。如果存在至少一个自由ID i，使得i≤h(L)，则L被打开，否则L被关闭。注意，s(v)是包含v的打开标记的数目。令μ(v)是包含v的所有打开标记上的最小h(L)。如果v*具有最高s(v*)值，则向v*分配最大自由ID i≤μ(v*)。

对于潜在更高的压缩率，已知枢纽标签压缩(HLC)算法可被使用。该算法通过表示每一唯一的子树(其可在许多标记中出现)仅一次来将每一标记解释为树。更精确地，前向标记L_f(u)中的枢纽可被表示为以u为根的树。对于规范的分层标记，树中的w∈L_f(u){u}的父是命中[u,w]的最高排名的顶点v∈L_f(u){w}。类似地，表示反向标签L_r(u)的树以u为根，其中w∈L_b(u){u}的父是命中[w,u]的最高排名的顶点v∈L_b(u){w}。

相同的子树通常出现在若干不同顶点的标记中。每一唯一子树可被表示为由以下组成的令牌：(1)根顶点r；(2)子令牌的数目k；(3)指示具有ID i的子令牌的根在距r的距离d_i内的k个对(i,d_i)的列表。不具有孩子的令牌(k＝0)是平凡令牌，并且被隐式地表示。每一非平凡令牌仅被存储一次。除了令牌本身外，该数据结构还维护将每一顶点v映射到其两个锚令牌(即树的表示L_f(v)和L_r(v)的根)的索引。

通过该表示，s-t距离查询在两个阶段中起作用。第一(标记检索)阶段通过以广度优先搜索(BFS)次序遍历相应的树并适当地聚集距离来重构标记L_f(s)和L_r(t)。第二阶段执行标记之间的交集，从而找出使dist(s,v)+dist(v,t)最小化的顶点v∈L_f(s)∩L_b(t)。由于通过第一阶段产生的各标记中的条目不必依据枢纽ID来排序，因此交集通过散列而非合并来起作用。

在一实现中，增强的压缩方法使用掩码令牌。图8是使用掩码令牌来进行标记压缩的方法800的一实现的操作流程。掩码令牌表示唯一子树；因此，方法800可为每一子树运行。

在810，从多个子树中获得一子树。在820，确定该子树的参考令牌t’。参考令牌t’是与该子树及其孩子的超集具有相同根顶点的令牌(如上所述)。在830，确定指示t’的哪些孩子应当被当作t的孩子的关联(incidence)向量(位掩码)。随后在840生成掩码令牌t以包括参考令牌t’的ID以及关联向量。

注意t和t’具有相同的根。由于以同一顶点v为根的令牌具有相似的孩子集，间接地(作为其他的子集)表达一些令牌避免需要表示一些孩子多次。

在一实现中，可使用超级令牌。超级令牌具有与标准令牌相同的结构(具有根和孩子列表)，但它表示若干令牌的并集,其定义为其孩子的并集。在一实现中，对于每一顶点v，创建表示以v为根的所有标准令牌的并集。尽管超级令牌本身不必表示标记中出现的任何实际的子树，但这样的子树可使用作为参考的超级令牌被表示为掩码令牌。

由于超级令牌表示以v为根的所有令牌的并集，该超级令牌中孩子的数目k可能十分大。由于(潜在地众多)掩码令牌中引用这个令牌的每一者需要k位掩码，空间需求可能是大的。已观察到，以v为根的许多原始令牌趋于具有相对较小数目的孩子，从而导致该掩码中的大多数条目为零。更紧凑地表示这些掩码可导致大节省。一种方法是使用游程编码(而非关联向量)来表示该掩码。

替换地，两级方法可改为被使用。概念上，将k位掩码拆分成个桶，每一桶表示(多达)8个连续位的集合。例如，具有k＝45的标记可由六个8位桶表示。桶0表示位0到7，桶1表示位8到15，并以此类推，直到桶5(表示位40到44)。为了节省空间，仅非空桶被显式表示。例如，存储指示哪q个桶(其中1≤q≤b)为非空的索引阵列，按次序后面是表示非空桶的q个8位关联阵列。使用个字节来存储该索引；索引尺寸可在查询时间被计算，因为k被显式地存储在超级令牌中。

在一实现中，孩子可被重排序。该技术的有效性取决于平均存在很少的非空桶。注意，这不仅取决于每一位掩码中“1”条目的数目，还取决于其在各桶中的分布。在一实现中，这些条目将被聚类。由于孩子在超级令牌中出现的次序对于正确性而言不重要，引起孩子可被排列为使得“1”条目更集中。可使用以下启发式：对于v的每一孩子x，对其中出现x的以v为根的标准令牌的数目c_v(x)进行计数，随后对以v为根的超级令牌的孩子以c_v(x)的递减次序排序。

图9示出了在其中可实现各示例实现和各方面的示例性计算环境。计算系统环境只是合适的计算环境的一个示例，并非旨在对使用范围或功能提出任何限制。

可以使用很多其它通用或专用计算系统环境或配置。适合使用的公知的计算系统、环境和/或配置的示例包括但不限于PC、服务器计算机、手持式或膝上型设备、多处理器系统、基于微处理器的系统、网络PC、微型计算机、大型计算机、嵌入式系统、包括任何以上系统或设备的分布式计算环境等。

可以使用诸如程序模块之类的由计算机执行的计算机可执行指令。一般而言，程序模块包括执行特定任务或实现特定抽象数据类型的例程、程序、对象、组件、数据结构等。在任务由通过通信网络或其它数据传输介质链接的远程处理设备执行的情况下可使用分布式计算环境。在分布式计算环境中，程序模块和其它数据可位于包括存储器存储设备的本地和远程计算机存储介质中。

参考图9，用于实现此处所描述的各方面的示例性系统包括计算设备，诸如计算设备900。在其最基本的配置中，计算设备900通常包括至少一个处理单元902和存储器904。取决于计算设备的确切配置和类型，存储器904可以是易失性的(诸如随机存取存储器(RAM))，非易失性的(诸如只读存储器(ROM)、闪存等)，或两者的某种组合。该最基本配置在图9中由虚线906来例示出。

计算设备900可以具有附加特征/功能。例如，计算设备900还可包含附加存储(可移动和/或不可移动)，包括但不限于磁盘、光盘或磁带。这样的附加存储在图9中由可移动存储908和不可移动存储910来例示出。

计算设备900通常包括各种计算机可读介质。计算机可读介质可以是可由计算设备900访问的任何可用介质，并且包括易失性和非易失性介质、可移动和不可移动介质。

计算机存储介质包括用于存储诸如计算机可读指令、数据结构、程序模块或其它数据之类的信息的以任何方法或技术实现的易失性和非易失性、以及可移动和不可移动介质。存储器904、可移动存储908、以及不可移动存储910都是计算机存储介质的示例。计算机存储介质包括但不限于，RAM、ROM、电可擦除可编程只读存储器(EEPROM)、闪存或其它存储器技术、CD-ROM、数字多功能盘(DVD)或其它光存储、磁带盒、磁带、磁盘存储或其它磁性存储设备、或可用于存储所需信息且可以由计算设备900访问的任何其它介质。任何这样的计算机存储介质都可以是计算设备900的一部分。

计算设备900可包含允许该设备与其它设备通信的通信连接912。计算设备900也可包括输入设备914，如键盘、鼠标、笔、语音输入设备、触摸输入设备等等。也可包括输出设备916，如显示器、扬声器、打印机等等。所有这些设备在本领域是众知的并且不必在此详细讨论。

应该理解，本文描述的各种技术可以结合硬件或软件，或在适当时结合两者的组合来实现。因此，当前公开的主题的方法和装置或其特定方面或部分可采取包含在诸如软盘、CD-ROM、硬盘驱动器或任何其它机器可读存储介质等有形介质中的程序代码(即，指令)的形式，其中当程序代码被加载到诸如计算机等机器内并由其执行时，该机器成为用于实现当前所公开的主题的装置。

尽管示例性实现可涉及在一个或多个独立计算机系统的上下文中利用当前所公开的主题的各方面，但本主题不受此限制，而是可以结合任何计算环境，诸如网络或分布式计算环境来实现。此外，当前所公开的主题的各方面可在某一个或跨多个处理芯片或设备中实现，且存储可类似地被跨多个设备影响。这样的设备可包括例如PC、网络服务器、以及手持式设备。

尽管用结构特征和/或方法动作专用的语言描述了本主题，但可以理解，所附权利要求书中定义的主题不必限于上述具体特征或动作。更确切而言，上述具体特征和动作是作为实现权利要求的示例形式公开的。