共享界标以快速处理前K条最便宜路径查询的方法

摘要

本文是加速查找图的两个顶点之间的前几条最短路径的技术。在实施例中，对于包含包括界标顶点的顶点的图，计算机计算每个顶点与每个界标顶点之间的距离。基于从每个顶点到每个界标顶点的距离，计算从源顶点到目标顶点的前几条最短路径。在实施例中，三角测量建立从当前顶点的邻居顶点到查询的目标顶点的距离的下限。在实施例中，使用基于距离下限的距离预测来加速对前几条最短路径的K‑A星搜索。

说明书

技术领域

本发明涉及图路径搜索。本文是基于界标顶点进行三角测量以加速搜索源顶点和目标顶点之间的一些最短路径的技术。

背景技术

逻辑图是捕获数据实体之间关系的重要数据模型。各种实际领域中的许多应用都可以利用图模型进行数据分析和查询。在过去几年中，可用于处理的相关数据量呈指数增长。在许多或大多数情况下，许多有价值的信息隐藏在数据实体之间的关系中。图查询引擎旨在通过提供对现有未加工数据执行图查询的快速且可扩展方式来利用这些关系。

在数据库行业，图数据库是新兴领域，发展迅速且备受关注。图数据库是特殊种类的数据库，其底层数据集被建模为图。图数据库产品通常支持路径查询，作为图分析的一个重要特征以揭示图的远处片段之间的连接。但是，图数据库可以存在造成某些路径查询执行缓慢的可伸缩性问题，尤其是因为路径查找通常具有指数计算复杂度。

路径查询是图数据库的一种特殊查询。路径查询可以要求在源顶点和目标顶点之间找到一些或所有可能的路径。路径查询的结果是结果路径的集合。每条结果路径可以有一系列顶点和边。

Oracle Spatial和Oracle Graph产品支持可以受益于路径查询加速的图数据模型。现有图数据库中的路径查询引起了一些观察。图数据库中的图数据可以非常庞大并且涉及数百万个顶点和数十亿条边。即使是小图也可能在两个顶点之间具有指数数量的路径。

在实践中，典型的查询包括足够的约束以将检索到的结果路径限制到少量。不过，即使结果路径的数量小，现有图数据库中使用的方法也常常需要过多的执行时间。

在大量可能的图查询中，人们对前k条最便宜路径查询非常感兴趣，这些查询是检索给定源顶点和给定目标顶点之间的前k条最便宜路径的查询，诸如根据成本函数。

回答前k条最便宜路径查询的现有技术方法通常依赖于构建特定于给定目的地顶点的最短路径树(SPT)。这意味着为图中的每个顶点计算到给定目的地顶点的最短路径。第一条最便宜路径将是在SPT中为给定源生成的路径。下一条最便宜路径是通过偏离SPT并采用成本最低路径来计算的。这种算法表示现有算法背后的主要机制，诸如Martins-Santos算法、Eppstein算法、Jiménez和Marzal的惰性算法以及递归枚举算法。

在多用户图数据库系统的上下文中，快速回答前k条最便宜路径查询更具挑战性，尤其是在巨大的图和许多并发用户的情况下。例如，每个查询可以为每个给定的源/目的地顶点对构建SPT，这可以非常慢和/或存储器密集。

附图说明

在附图中：

图1是描绘示例计算机的框图，该计算机基于图的界标顶点进行三角测量以加速搜索源顶点和目标顶点之间的一些最短路径；

图2是描绘示例修剪的框图，该示例修剪需要应用使用界标距离来修剪死胡同顶点的修剪规则；

图3是描绘示例三角测量的框图，该三角测量计算可能是从当前的邻居顶点到目标顶点的最短中间路径的长度的最佳下限的相应值；

图4是描绘示例三角测量的框图，以基于给定邻居顶点的所有界标顶点计算准确的下界；

图5是描绘示例加速K-A星搜索的框图，这是使用优先级队列发现前几条最短路径的图搜索算法；

图6是描绘通过基于界标顶点进行三角测量来加速搜索源顶点和目标顶点之间的几条最短路径的示例过程的流程图；

图7是描绘用于指定界标顶点的示例过程的流程图，从该界标顶点可以计算三角测量所需的所有距离；

图8是描绘示例查询处理的流程图；

图9是描绘通过加速的K-A星搜索的示例处理的流程图；

图10是图示可以在其上实现本发明的实施例的计算机系统的框图；

图11是图示可以用于控制计算系统的操作的基本软件系统的框图。

具体实施方式

在下面的描述中，出于解释的目的，阐述了许多具体细节以便提供对本发明的透彻理解。但是，将显而易见的是，可以在没有这些具体细节的情况下实践本发明。在其它情况下，以框图形式示出了众所周知的结构和设备，以避免不必要地使本发明晦涩难懂。

总体概述

本文的技术选择图的顶点的小子集作为界标顶点。对于图中的每个顶点，发现并记录到(和从，如果图是有向的)每个界标顶点的最短路径的长度。然后可以在多个并发查询之间共享往返界标的距离。在运行时，当为顶点的给定源/目的地对生成前k条最便宜路径时，一些预先计算的距离被用于估计给定顶点到查询的目标顶点的距离。基于估计的距离，优先探索中间路径以减少探索搜索空间，从而加速前k条路径查找查询。没有已知的使用界标来加速的前k条最便宜路径算法。

与其它现有的回答前k条最便宜路径查询的解决方案相比，这些解决方案为顶点的每个源/目的地对构建最短路径树(SPT)，本文的技术构建界标并在图加载时计算界标距离，然后在同一图的不同查询中共享界标距离。界标距离被用于估计其它顶点之间的距离，这可以驱动图探索并修剪无用的路径。

本文的技术的优点包括：

·更快：在运行时，SPT的计算成本比本文的距离估计高；

·更小：存储器占用不会随着查询的运行量而增长。如果只有十个界标顶点，那么无论运行多少查询，每个顶点都只存储十个特性。基于SPT的解决方案必须为每个查询存储SPT；以及

·可控的存储器占用：如果查询仅探索图的一个区域，那么本文的技术可以将界标限制到那个区域。基于SPT的解决方案必须处理整个图。

上述优点对于多用户图处理系统是重要的，因为小且可控的存储器占用以及速度对于维持高系统吞吐量至关重要。

在实施例中，对于包含包括界标顶点的顶点的图，计算机计算每个顶点和每个界标顶点之间的距离。基于每个顶点到每个界标顶点的距离，计算从源顶点到目标顶点的前几条最短路径。

在实施例中，三角测量建立从当前顶点的邻居顶点到查询的目标顶点的距离的下限。在一个实施例中，使用基于距离下限的距离预测来加速对前几条最短路径的K-A星搜索。

1.0示例计算机

图1是描绘实施例中的示例计算机100的框图。计算机100基于图的界标顶点进行三角测量以加速搜索源顶点和目标顶点之间的一些最短路径。计算机100可以是诸如刀片之类的机架式服务器、个人计算机、大型机、虚拟计算机或其它计算设备。

在易失性存储器和/或持久存储装置中，计算机100可以存储和/或加载可能包含许多顶点(诸如A-J)的逻辑图110。图1-5涉及相同的计算机100和相同的图110。图110的内容如下。

顶点A-J可以通过边互连。边可以是有向的。例如，有向边从顶点A开始，如箭头所示，在顶点H处终止。有向边只应当沿着该边指示的方向被遍历。例如，顶点H可从顶点A到达，但顶点A不能从顶点H到达。

在实施例中，相同的两个顶点可以通过具有相同方向和相同或不同长度的多条冗余边连接，如下面所解释的。在实施例中，冗余边被考虑并且可以贡献单独的解路径，如下面所解释的。在未示出的实施例中并且因为计算机100寻找最优(即，最短)图遍历路径，在相同方向的相同的两个顶点之间的冗余边被忽略。对于这样的冗余边，只考虑最短边。

边可以是无向的，诸如连接顶点A和I的边，如图所示，没有箭头。在实施例中，无向边可以被实现为在相同两个顶点之间的相反方向的两条有向边。

顶点，诸如A，可以有多条起始边、终止边和/或无向边。因此，顶点可以直接连接到无、一个或多个直接邻居顶点，但是根据边的方向，一些邻居顶点可能无法到达或只能间接到达(即，通过遍历附加的顶点和边)。例如，由于边方向，顶点A连接到顶点H，但顶点A不能从顶点H到达。同样，顶点G连接到顶点B，但是由于边方向，顶点B从顶点G只能通过中间顶点A到达。

图110不需要被连接。例如，顶点D被断开。直接或间接连接的顶点可以通过多条遍历路径连接。例如，顶点C可通过路径F→C和路径F→G→C从顶点F到达。

在本文中，距离和长度是同义词，并且每条边都有长度。每条包含多条边的遍历路径的长度是这些边的长度之和。当边度量不是长度时，本文的技术直接适用。例如，边可以代替地有：

·权重，

·持续时间；例如，由于交通拥堵或红绿灯引起的倒车会使得更长距离的路线比直达路线更快，

·财务成本；例如，由于道路收费引起的倒车会使得更长距离的路线比直达路线更便宜，或者

·物流成本；例如，由于燃料消耗引起的倒车会使得更长距离的平坦路线比丘陵直达路线更便宜。

如图所示，边可以具有不同的长度(即，距离)。例如，边C-G在两个方向上的长度都是0.4，如图所示。边可以有默认长度，诸如零或一。在这个示例中，默认边长为一。因此，边F→G的长度为一。

因为边可以是有向的，所以相同的两个顶点可以由两条边(即，每个方向上的边)连接，而这两条边可以有不同的长度。例如，边H→J比边J→H长。

在未示出的实施例中，所有边都具有相同的长度。在这种情况下，路径F→C将比路径F→G→C更短(即，更少的边)，尽管两条路径都起源于顶点F并终止于顶点C。

在所示实施例中，路径的长度是路径中边的长度之和。如图所示并且虽然有更多边，但路径F→G→C的长度为1+0.4＝1.4，它小于如图所示长度为2的路径F→C的长度。因此，与直觉相反，具有更多边的路径可以比具有较少边的路径短，或者可以不短。

在操作中，计算机100探索图110以找到从源顶点(诸如如图所示的I)到目标顶点(诸如如图所示的C)的几条最短路径。在实施例中，只考虑没有循环的路径，这有两个后果：a)排除自指向(未示出)边，这是在同一顶点处起始和终止的边，以及b)遍历路径不能包括同一个顶点多于一次。例如，路径F→A→B→G→A→H被排除在外，因为它两次访问顶点A。在实施例中：包括循环，可以在相同的遍历路径中重新访问顶点，并且解路径可以包含循环。

计算机100在两个阶段中找到最短路径。在第一阶段，选择顶点的子集作为界标，诸如F-G和J。界标距离120通过发现每个顶点A-J之间以及与每个界标F-G和J的最短路径来导出。在这个示例中，界标距离120最多具有：10个顶点x3个界标x2个方向＝六十个距离。在这个示例中，界标距离120具有少于六十个距离，因为在特定顶点和特定界标之间没有路径。例如，从界标J无法到达顶点A，其在界标距离120中被示为空白(即，无值)。根据实施例，不可达性可以被表示为具有诸如负数之类的无效值的距离。

如果界标距离120中的行仅包含空白，那么该行的顶点与所有界标断开连接，诸如顶点D。在界标距离120中，作为界标的顶点F-G和J的行包含一些零，因为界标与自身之间的距离始终为零。

在第一阶段期间，计算机100用最短距离填充界标距离120。可以使用各种最短路径算法来填充界标距离120。在实施例中，最短路径算法接受单个源顶点和单个目标顶点。如上面所解释的，界标距离120记录多达六十个距离，在这种情况下，最短路径算法可以被调用多达六十次。例如，最短路径算法可以是Bellman-Ford、Dijkstra、Gabow或Thorup。

在实施例中，用于界标距离查找的最短路径算法接受多个源顶点和/或多个目标顶点。无论是接受多个源还是只接受一个源，最短路径算法都可以充分利用可从不同源顶点和/或不同中间顶点到达和/或可以到达不同目标顶点和/或不同中间顶点的共同(即，共享)子路径。在实施例中，最短路径算法维护一个或多个最短路径树(SPT)。在实施例中，最短路径算法基于多源广度优先搜索(MS-BFS)。

所有对最短路径算法都被排除在外，因为它们需要太多时间和/或空间。基于图110有多少顶点，所有对最短路径需要四次方时间。本文的技术比四次方要快。

到第一阶段结束时，界标距离120就可以使用了。第一阶段仅需要图110。但是，第二阶段还需要可以由查询识别或以其它方式选择的(一个或多个)源顶点和(一个或多个)目标顶点。在第二阶段中，计算机100可以接收查询(未示出)以找到从特定源顶点到特定目标顶点的几条最短路径。例如，查询可以请求从源顶点I到目标顶点C的前两条最短路径，如图所示。

在这个示例中，从源顶点I到目标顶点C有七条解路径，示为解距离130。虽然解路径I→A→C包含最少的边，但这不是从源顶点I到目标顶点C的前两条最短路径之一。代替地，解距离130示出解路径I→A→B→G→C和解路径I→A→G→C是两条最短路径。因此，查询应当只返回这两条路径。

在其它示例中，查询可以请求从源顶点I到目标顶点C的前七条最短路径或前八条最短路径。在这两种情况下，查询都应当准确返回解决方案的所有七条解路径距离130。

大多数图路径搜索算法，诸如广度优先搜索(BFS)或深度优先搜索(DFS)，都是基于迭代探索。每次迭代都有当前顶点，诸如对于DFS，或当前顶点子集，例如对于BFS的地平线或边界。从(一个或多个)当前顶点扇出的边在该迭代中被遍历。

基于(一条或多条)当前路径的(一条或多条)新路径通过将(一条或多条)当前边遍历到相邻顶点而进一步扩展。因此，路径搜索增量(即，迭代地)使路径增长更长，并且由于边的扇出，路径数量翻倍。如本文稍后解释的，本文通过路径查找技术保证收敛，使得对于任何图，只有有限的中间路径和解路径的集合需要处理。

为了演示，对解距离130进行排序以示出解路径将通过总是遍历最短可用边的常规贪婪深度优先搜索(DFS)来发现。例如，当DFS的当前顶点是如图所示的顶点A时，边A→H将是要遍历的顶点A的边中的第一条，因为边A→H是顶点A的最短起始边，这是不好的选择，因为这是个死胡同(即，目标顶点C不能从顶点H到达)。同样，边A→B几乎是顶点A基于边长要遍历的最后一条边，这是不幸的，因为边A→B是最短解路径的一部分。

实际上，解距离130示出最短的两条解路径是贪婪DFS要发现的最后两条解路径，这可以是违反直觉的，因为贪婪通常旨在加速最优性的发现。例如，贪婪DFS通常优于BFS。如下面所解释的并且尤其是关于图5所解释的，本文的技术由于各种原因优于贪婪DFS，包括：a)比贪婪DFS更好的边优先化，以便更快地发现最短路径，b)预测性修剪(即，避免)死胡同(即，无用)路径，和c)如本文稍后解释的，更好的停止准则，其预测未探索的解路径不可能比已经找到的解路径更短。

2.0修剪示例

图2是描绘实施例中的示例修剪200的框图。修剪200应用修剪规则1-2，其使用界标距离120来修剪死胡同顶点。

如上面所讨论的，一些顶点可能无法从其它一些顶点到达。例如，一些顶点可能无法从一些界标顶点到达，并且一些界标顶点可能无法从一些顶点到达，如图1的界标距离120中的空白所示。修剪规则1-2检测不可到达性并可以使一些顶点被排除在外。

当当前顶点的邻居顶点可从界标顶点到达，而目标顶点不能从该界标顶点到达时，修剪规则1检测到邻居顶点和目标顶点之间没有路径。根据修剪规则1，可以修剪掉该邻居顶点(即，从所有迭代和所有解路径中排除)。

当界标顶点可从目标顶点到达但不能从邻居顶点到达时，修剪规则2检测到邻居顶点和目标顶点之间没有路径。根据修剪规则2，可以修剪掉该邻居顶点。

在每次迭代开始时，可以应用修剪规则1-2来检测应当修剪当前顶点的哪些邻居顶点。被修剪的顶点被排除在外，即使可从另一个还不是当前顶点的顶点到达。因此，一次修剪可以具有重复的性能益处。同样，修剪的益处进一步与修剪后的子图的尺寸成正比，该修剪后的子图只能通过修剪后的顶点到达。例如，本文的修剪技术可以避免修剪后的子图可以包含数千个顶点和数百万条边，但贪婪DFS无法避免。

基于当前迭代的当前顶点A，修剪发生如下。修剪200是演示表，它实际上并没有被存储，它有识别当前顶点A的每个邻居顶点B-C、E和G-H的邻居列。邻居顶点I被排除在外(即，未示出)，因为它在以前的迭代中被访问过(并且不应当被重新访问)。

对于界标列中示出的三个界标顶点F-G和J中的每一个，每个邻居顶点在邻居列中重复。修剪规则1-2中的每一个都有两个相应的条件要由每对邻居顶点和界标顶点满足或不满足。仅当对于给定顶点对，第一个条件成功且第二个条件失败时，才会修剪该邻居顶点。

修剪规则1-2中的每一个对于两个条件都有两个相应的列，其包含指示是(即，条件成功)或否(即，条件失败)的布尔值。对于或者修剪规则1或者2的修剪200中的行，如果规则的第一列指示是，并且规则的第二列指示否，那么修剪该邻居顶点。

修剪规则1的第一列有一个条件，即，邻居顶点可从界标顶点到达。该列对一些顶点示出否，使得修剪规则1不会基于那些顶点对修剪那些邻居顶点。

修剪规则1的第二列有一个条件，即，目标顶点C可从界标顶点到达。该列对许多顶点示出是，使得修剪规则1不会基于那些顶点对修剪那些邻居顶点。

如果在修剪规则的一列中示出空白，那么修剪规则的另一个列已经指示不按该修剪规则进行修剪。

只有表示具有邻居顶点H和界标顶点J的一对的修剪200的底行才在修剪规则1的第一列中为“是”并在修剪规则1的第二列中为“否”。因此，当当前顶点为A时，修剪规则1仅修剪邻居顶点H。如图所示，邻居顶点H也是被修剪规则2修剪的唯一邻居顶点(即，当界标顶点为F且当前顶点为A时)。因此，修剪规则1-2中的任何一个都足以修剪邻居顶点H。

3.0示例三角测量

图3是描绘实施例中的示例三角测量300的框图。三角测量300中的任一个或没有一个可以计算从当前顶点A(未示出)的邻居顶点B到目标顶点C的最短部分路径的长度(示为问号？)的最佳下限。

三角测量包含三个顶点，它们始终是当前迭代的当前顶点的邻居顶点、界标顶点和当前查询的目标顶点C。三角测量计算从邻居顶点到目标顶点的最短路径的可能下限，但不一定是最准确的下限。大多数三角测量计算不是最佳的可能下限。

三角测量中一个、几个或没有一个三角测量计算最佳下限。最佳下限是最高的。因此，在选择最佳下限之前，应当计算多个三角测量。虽然图3中仅示了两个三角测量(F、B、C和B、C、G)，但应当计算更详尽的三角测量集，如图4中所示。

下限是保证小于或等于从邻居顶点到目标顶点的最短路径的实际长度的估计。如本文稍后解释的，可以使用下限来估计目标顶点与邻居顶点的距离。贪婪DFS会浪费时间遍历作为长解路径的一部分的短边，本文的技术避免了这种情况，因为下限促进估计包含短边的解路径有多长。例如，代替地，较长的边可以是解路径的一部分，其基于具有较小下限的较长边而被估计为更短，如本文稍后所演示的。负的下限可以用零代替作为下限。

界标距离120i-ii包含图1的界标距离120的小部分。界标距离120i-ii中的每一个都演示了两个所示的三角测量之一，两个所示的三角测量不同在于界标顶点是三角测量的源还是目标，但是不一定是路径查询的源或目标。

当诸如F之类的界标顶点是三角测量的源顶点时，三角测量的下限是距离(L,T)–距离(L,V)，如界标距离120i的左下方的公式所示，其中：L是界标顶点；T是查询的目标顶点；并且V是邻居顶点。通过该公式计算的三角测量的下限在界标距离120i的右下方示出。

V可以是(一个或多个)不同迭代的不同当前顶点的相同邻居顶点。因为三角测量不要求当前顶点，所以在迭代之前或在将顶点V用作邻居顶点之前，可以可选地急切地计算具有一些或所有界标顶点的一些或所有顶点的三角测量。同样，可以根据需要延迟计算与邻居顶点V的三角测量。

在接收查询之前通常不会计算三角测量，因为三角测量需要查询的目标顶点。在任何情况下，由三角测量计算的下限都可以被高速缓存以供重用。在实施例中，并行和/或串行的多个查询可以共享三角化下限的高速缓存。

每个三角测量在源顶点和目标顶点之间都有中间顶点，其不是查询的目标顶点。在一些情况下，中间顶点是界标顶点。三角测量的或者源顶点或者目标顶点(但不是两者)是界标顶点。当诸如G之类的界标顶点是三角测量的目标顶点时，三角测量的下限是距离(V,L)-距离(T,L)，如界标距离120ii的左下方的公式所示。

4.0距离预测

图4是描绘实施例中的示例三角测量400的框图。如上面所解释的，准确的下限可以需要对给定邻居顶点的所有界标顶点进行三角测量。三角测量400的每一行示出基于给定邻居顶点和给定界标顶点的一对三角测量。每行有两个三角测量，因为一个三角测量可以使用界标顶点作为源顶点，而另一个三角测量可以使用相同的界标顶点作为目标顶点。

具有两个三角测量的每一行也意味着两个下限，示为X和Y列。这两个下限中的较高者是更准确的估计，示为最大下限列。每个邻居顶点对于每个界标顶点都有单独的三角测量行。

例如，三角测量400的前三行包含针对所有三个界标顶点F-G和J的三角测量。虽然给定的邻居顶点具有许多行，但只有一行具有最佳估计的下限，即，那些行中具有最大下限列中的最大值的行。例如，最大下限列对于邻居顶点E示出0.8和1.2，在这种情况下，最佳下限估计是1.2。

三角测量400的顶行如下。列T-W具有来自作为图1的界标距离120的一部分的界标距离120iii的值。列T和U具有一个三角测量所需的距离，而列V和W具有另一个三角测量所需的距离。两个三角测量计算在相应的列X和Y中示出的下限，它们基于算术减法，使得X＝T–U和Y＝V–W。

三角测量400并未示出所有行和所有值。空白值指示不相关或不感兴趣的值，这并不意味着未计算那些值。一些不相关或不感兴趣的行未示出。例如，界标顶点J缺少感兴趣的行，因为界标顶点J具有非常有限的双向可达性，使得界标顶点J不会为最大下限列贡献感兴趣的值。未示出用于邻居顶点H的行，因为顶点H已如本文前面解释的那样被修剪。

三角测量400是演示性的，而不是被存储。高速缓存下限需要高速缓存来自最大下限列的最佳值，这些值可以被高速缓存为邻居顶点的特性，或者高速缓存在由邻居顶点键入的高速缓存中。

5.0加速的K-A星搜索

各种图搜索算法具有各个方面，诸如半径、回溯、递归、并发和/或偏差，当图巨大时，它们会对性能产生重大影响。例如，穿过曼哈顿式城市街道网格的汽车必须在每个红绿灯交叉路口的三条出发边之间做出选择。一条只有20个交叉口的看似适中的路线将涉及3^20≈35亿条不同路线之间的总体选择。照此，通过智能启发式加速图搜索对于非平凡图可以是重要的。

图5是描绘实施例中的示例加速的K-A星搜索500的框图。K-A星搜索(又名K-A*搜索)500是一种图搜索算法，它使用优先级队列510来发现图1的前几(即，K)条最短路径。图1的图110的一部分在图5中示出以用于演示性参考。

K-A星搜索500通过将先前的中间路径逐渐增长稍长来迭代地生成中间路径。每条中间路径具有长度和路径的最后一个顶点与查询的目标顶点之间的剩余距离的估计下限。例如，优先级队列510的路径列具有路径I→A，其预测距离列示出中间路径长度为1并且估计的剩余距离的下限为0.9。

因此，预测路径I→A的迭代增长以包括附加的顶点通过增长到至少1+0.9＝1.9的长度来到达目标顶点C，如预测的距离列所示。0.9的估计下限取自图4的具有当前顶点I、邻居顶点A和界标顶点F的三角测量400的右下方。

K-A星搜索500有利于预测到达目标顶点C的中间路径，总长度较短，总长度是当前长度加上估计的剩余距离的下限，如上面所解释的。这种对预测的距离的偏差是K-A星搜索500具有在预测的距离列上按升序排序的优先级队列510的原因。

优先级队列510在创建时为空。然后源顶点I最初存储在优先级队列510中，它在优先级队列510中示为顶行。

K-A星搜索500是迭代的。因为路径I在迭代开始之前被添加到优先级队列510，所以路径I在优先级队列510中被示为在在迭代开始之前的迭代零中添加，如添加的列中所示。第一次迭代是迭代一。

实际上仅存储优先级队列510的路径和预测的距离列。三个迭代列是演示性的并且不存储。迭代列示出了关于优先级队列510在每次迭代中包含哪些路径的变化，如下面所解释的。

在每次迭代中，当前顶行中的路径在从优先级队列510中移除之后被扩展。例如，路径I被移除以在迭代一中进行扩展，如已移除列中所示。

优先级队列510示出了针对所有迭代1-7的队列内容随时间的演变，这不是针对个体迭代的队列内容的快照。例如，基于添加和移除的列，优先级队列510在迭代一中仅包含路径I→A，因为路径I和I→A是在迭代一期间或之前添加的，但路径I在迭代一期间被移除以用于扩展。因此，虽然未如此示出，但路径I→A在迭代1-2之间位于优先级队列510的顶部，并在迭代2中被移除以进行扩展。

扩展需要：a)移除优先级队列510的顶行的路径，并且该路径以当前顶点结束，b)对于当前顶点的每条可用边，创建新路径并插入优先级队列510，该新路径基于被移除的路径，如由当前边进一步扩展到邻居顶点。因此，K-A星搜索500增量/迭代地使路径增长更长，并且由于边的扇出，路径数量翻倍。

将新的中间路径插入优先级队列510需要：计算新路径的长度，调用从新路径中的最后一个顶点到目标顶点C的剩余距离的下限估计，并将那两个量相加以计算预测的距离作为用于优先级队列510的排序键。例如，在迭代2中，路径I→A出队并扩展以从当前顶点A到达邻居顶点B-C和E-G，其估计的下限在迭代2表中右侧示出，该表具有图4的三角测量400的最大下限列的一部分。因此，三角测量影响优先级队列510的排序，这是K-A星搜索500的新颖方面。因此，K-A星搜索500的偏差不是贪婪的，而是预测的，这也是新颖的。

收敛(即，最终耗尽优先级队列510)得到保证，因为K-A星搜索500总是或者：检测到已经发现前K条解路径，或者优先级队列变得被耗尽(即，变为空)，如本文稍后解释的。即使包括循环，这种有保证的收敛也会发生。

优先级队列510的预测的距离列中的值单调增加，因为K-A星搜索500有偏差。排队的路径中的边的计数不是单调的，因为较少的边并不意味着到目前为止更短的长度、更短的剩余长度、更短的组合长度，如本文前面所解释的。例如，路径I→A→B→G出现在路径I→A→F上方的优先级队列510中，即使路径I→A→F具有较少的边并且更早地入队。

诸如I→A→B→G→C和I→A→C之类的路径被示为粗体，因为它们是到达目标顶点C的解路径。添加的解路径列是空白的，因为解路径不应当添加到优先级队列510。示出优先级队列中的解路径510是演示性的。针对一些图的一些查询不会返回所有的解路径，诸如查询前几条最短路径，诸如当有超过k个解路径时前/最佳k条路径。

因为针对当前查询的每条解路径都以目标顶点C结束，所以一旦生成路径，该路径就被识别为解路径。优先级队列510的找到的列示出在哪次迭代中生成了每条解路径。

在这个示例中，查询查找从源顶点I到目标顶点C的前两条路径。找到的列指示要到达的前两条解路径是在相应的迭代2和4期间找到的。这包括解路径I→A→B→G→C，这保证是前两条解路径之一，因为在迭代4结束时，优先级队列510仅包含三条中间路径，其预测的距离为2.1、2.3和2.4，它们比1.9长，这是解路径I→A→B→G→C的长度。

换句话说，K-A星搜索500一生成解路径I→A→B→G→C就知道它总是最短的解路径，即使优先级队列510还不是空的。而且在迭代4处，仍然未知先前找到的解路径I→A→C是否是前两条解路径，因为优先级队列510包含预测距离小于解路径I→A→C长度的中间路径。因此，优先级队列510应当在迭代4之后继续迭代以确定已经发现或未发现的哪条解路径将是第二最短的解路径。

迭代7是K-A星搜索500的最后一次迭代，即使优先级队列510仍然包含两条未探索的中间路径I→A→F→G和I→A→E→F，并且未找到解路径I→A→F→G→C。在迭代7中，生成解路径I→A→G→C，并将其检测为前两个查询的第二最短解路径，在这种情况下，搜索/迭代停止。仍然排队的两条中间路径的预测的距离都比解路径I→A→G→C的长度长。

因为预测的距离是下限，所以剩余排队的中间路径的扩展不能达到比已找到的前两条路径中的任一条更短的解路径。因此，K-A星搜索500在优先级队列510没有下溢的情况下完成。而BFS或DFS，无论是否贪婪，都不会做出预测并且不会停止，直到优先级队列510最终为空。

6.0示例路径查找过程

图6是描绘在实施例中通过基于界标顶点进行三角测量来加速搜索源顶点和目标顶点之间的最短路径的示例过程的流程图。参考图1和5讨论图6。

步骤602是准备性的，可以在接收路径查找查询之前发生，并且每个图只需要发生一次，诸如110。例如，步骤602可以在急切或延迟加载图110时发生。步骤602计算每个图顶点和每个界标顶点之间的距离。

在实施例中，界标顶点的计数基于图110的顶点和/或边的计数。在实施例中，界标顶点的计数与顶点的计数成对数。例如，步骤602可以选择logN个界标顶点，其中N对图110中的所有顶点进行计数。在实施例中，界标顶点的计数是诸如10、100或1000之类的小常数。

步骤602计算两个方向上的单独距离，即，到每个界标顶点的距离和从每个界标顶点的距离。步骤602可以使用矩阵算术，诸如使用距离矩阵，诸如热带矩阵乘法和/或最小加矩阵代数。步骤602可以代替地使用蛮力探索(诸如图形路径查找搜索)以发现距离。

步骤602不需要识别或记录往返界标顶点的实际最短路径，因为记录最短路径长度就足够了。步骤602计算可以存储为与每个界标顶点相关联的两列或存储为与每个顶点A-J相关联的两行的界标距离120。界标距离120可以高速缓存在存储器中或盘上，以供对相同图110的后续查询。

基于界标距离120，步骤604计算从源顶点到目标顶点的前K条最短路径。例如，计算机100可以接收针对图110的路径查找查询，该查询指定源顶点I和目标顶点C并将结果限制为前三条解路径，这会导致步骤604。步骤604可以包括以下活动中的一些或全部。

在急切的实施例中，步骤604基于目标顶点C在接收到查询后并且在K-A星搜索500开始迭代之前计算所有三角测量和/或修剪。例如，步骤604可以针对多个查询中的每一个进行。但是，如果那些查询共享相同的图110，那么步骤602只需要发生一次。在懒惰的实施例中，步骤604立即开始K-A星搜索500，并且仅在特定顶点是迭代K-A星搜索500的当前顶点时发生三角测量和修剪。例如，当顶点A是当前顶点时，其它顶点是A的邻居，并且那些邻居可以被修剪或三角测量以估计从邻居顶点到目标顶点C的距离的下限。

一旦被修剪，对于K-A星搜索500的剩余部分，顶点就仍然被修剪。在实施例中，懒惰三角测量被高速缓存以在以后的迭代中和/或由共享相同目标顶点C的并发或以后的查询重用。例如，可以基于最近最少使用(LRU)高速缓存策略从高速缓存中逐出三角测量。例如，具有不同目标顶点的查询不共享三角测量，并且可以竞争高速缓存存在。

在实施例中，界标距离120被高速缓存。例如，相同的图110的所有查询，无论源顶点和目标顶点如何，都可以共享相同的界标距离120。在实施例中，只要图110保持被加载，界标距离120就保留在存储器中。

当找到前k条最短路径时，K-A星搜索500和步骤604结束，即使优先级队列510仍然包含未探索的中间路径和/或一些解路径未被发现。如果优先级队列510被耗尽/为空，那么K-A星搜索500和步骤604结束。前k条最短路径(如果优先级队列510下溢则更少)可以作为对客户端查询的回答返回给客户端。

7.0示例界标过程

图7-8示出了在实施例中操作的计算机100。图7的过程是准备性的，并且可以在加载图110之后立即急切地操作，而无需等待查询。图8的过程是完全可操作的，并且可以在查询执行期间发生。

图7是描绘在实施例中用于指定界标顶点的示例过程的流程图，可以从该界标顶点计算三角测量所需的所有距离。参考图1和5讨论图7。

图7的过程有四个阶段，顺序如下：1)限制多少个界标顶点，2)识别界标顶点，3)计算三角测量所需的界标距离，以及4)将界标距离存储在存储器中和/或盘上。

虽然没有示出，但第一阶段计算需要多少界标顶点。例如，界标顶点的计数可以基于图110的固定数量的顶点和/或顶点的(一个或多个)部分，诸如：百分比、对数、顶点与边的比率和/或，以边的计数测得的图110的直径、直径与顶点的比率。不管界标顶点的限制公式是什么，界标顶点都应当是图110中的顶点的少数。

更多界标顶点可以产生更准确和更高估计的三角测量下限。但是，更好的三角测量并不意味着更好的解路径。太少的界标顶点会造成产生完全相同查询结果的不准确的三角测量，但需要更多时间和空间，因为优先级队列510将包含不太准确和低估的预测的距离510，这使得K-A星搜索500退化为贪婪DFS，但是仍然可能比四次方复杂度更好。但是，太多的界标顶点会增加三角测量延迟，而准确性几乎没有增加。

如本文后面所讨论的，并且因为可能难以计算最优数量的界标，K-A星搜索500可以以太少的界标顶点开始，并且当平均查询延迟超过阈值时，可以指定附加的界标顶点，这可以反复发生，直到时延可接受或停止改善。每当添加界标顶点时，可以容易地增量地执行准备或执行三角测量的数值处理。界标顶点的单调增长是容易适应的。添加界标顶点或者提高估计的(一个或多个)上限的值和准确性，或者那些估计保持不变。

第二阶段需要识别界标顶点。所示实施例具有不同的顶点选择方式。如图所示，箭头连接选择顶点的多步骤方式。箭头的缺失示出了单独的选择方式，在一些实施例中可以组合或不组合。

步骤701随机地选择界标顶点。例如，每十分之一、百分之一或千分之一顶点可以是界标顶点。

步骤702将界标顶点的选择限制到图110的(一个或多个)地形或拓扑区域，诸如当图110被分层布置时，诸如平面或径向。例如，界标选择可以在某种程度上或完全偏向图110的外围/周界。如果查询的(一个或多个)目标顶点是已知的，那么步骤702可以将界标选择限制到图110的包含大部分或所有目标顶点的区域来提高三角测量准确性，以至于可以需要更少的界标顶点来实现相同的准确性。

基于边长，用于选择的一般偏差可以最大化界标顶点和/或均匀空间界标顶点之间的距离。步骤703A-B协作以最大化界标顶点之间的地形距离。步骤703A用单个种子顶点(诸如随机选择的顶点)初始化顶点的增长子集。种子顶点不会变成界标顶点。步骤703B基于距离的总和迭代地选择距生长子集中的所有顶点最远的顶点。所选择的顶点变成界标顶点并被添加到增长的子集中。

步骤704A-B协作以最大化界标顶点之间的拓扑距离。步骤704A选择：不会变成界标顶点的种子顶点、距种子顶点最远的第一界标顶点，以及距第一界标顶点和种子顶点最远的第二界标顶点。

步骤704B不使用种子顶点。步骤704B迭代地选择最大化以下各项之间的算术差的顶点：a)沿着包括所选择的顶点的最短路径的所有界标顶点对之间的距离之和，以及b)到目前为止选择的不包括所选择的顶点的所有界标顶点对之间的距离之和。

虽然未示出，但第三阶段计算界标距离120。第四阶段需要将界标距离120的部分存储为顶点的特性的步骤705，诸如存储在存储器和/或盘上的(一个或多个)列式向量中。在步骤705之后，计算机100准备进行三角测量。

8.0示例查询处理

图8是描绘实施例中的示例查询处理的流程图。参考图1、4-5和9讨论图8。

步骤801接收查询，该查询指定源顶点、目标顶点和对查找多少最短路径的限制。

在实施例中，可选步骤802基于界标距离120对一些或所有顶点A-J进行急切的三角测量。例如，步骤802可以计算三角测量400。

步骤802可以慢，并且三角测量400可以具有巨大的存储占用，这可以是仅对一些顶点执行步骤802或完全跳过步骤802的原因。同样，针对一些或所有顶点的三角测量可以已经由具有相同的图110的相同目标顶点C的先前查询高速缓存。如本文稍后解释的，三角测量可以懒惰地单独或批量执行。三角测量是幂等的。例如，可以按需重新生成从高速缓存中驱逐的三角测量。

步骤803执行加速的K-A星搜索，诸如500或900。K-A星搜索找到前几条最短路径作为对步骤801的查询的回答。该回答可以被发送回客户端。

在实施例中，步骤804基于回答查询的前几条最短路径来检测金融欺诈。欺诈检测的计算成本是昂贵的。例如，发现非法金融可以基于参与者(诸如汇款者)之间的关系和事件。最短路径可以通过实现搜索半径来增加图分析的相关性。最短路径可以识别活动或参与者的可疑关联。作为示例，一些财务合规应用依赖于逻辑图来调查电汇风险，这可以会揭示特定财务账户如何与其它已知欺诈账户相关联。

基于界标距离120的共享/重用/高速缓存，步骤805顺序地和/或并发地地执行同一个图110的多个查询。

步骤806基于(一个或多个)查询的时延来指定附加的界标顶点。如本文前面所解释的：a)本文的K-A星搜索通过增加距离下限的准确性来加速，b)更多的三角测量提高距离下限的准确性，c)更多的界标距离120提供更多的三角测量，以及d)更多的界标顶点提供更多界标距离120。而且如本文前面所解释的，加载图110和执行第一查询的总时延在以下两者之间具有张力：a)通过提高准确性来加速，和b)通过避免提高准确性所需的预备计算来加速。

如本文前面所讨论的，总体效率可以通过以下方式提高：a)乐观地从太少的界标开始，b)检测个体或多个查询的过度时延，诸如使用阈值，c)重复指定一个或一些附加顶点成为界标顶点，直到时延变得可接受或停止改善，以及d)计算附加的三角测量并在步骤806处添加更多界标顶点时替换上限。

9.0搜索的提前终止

图9是描绘在实施例中由加速的K-A星搜索900进行的示例处理的流程图。参考图1和5讨论图9。K-A星搜索900可以是K-A星搜索500的实施方式。

步骤901操作包含中间路径的优先级队列，这些中间路径通过中间路径长度和到目标顶点C的剩余估计距离之和来排序/排序(ordered/sorted)。例如，优先级队列可以由树状堆结构实现，诸如用二叉堆的堆排序。二项堆比二叉堆具有更快的插入，并且插入是本文加速的K-A星搜索的主要队列操作，诸如当K-A星搜索在优先级队列为空之前停止时。

步骤902移除优先级队列的头部，其是被预测为最短路径的一部分的中间路径。步骤902识别当前顶点的每个邻居顶点，当前顶点是中间路径中的最后一个顶点。步骤902在前K条最短路径搜索期间检测到邻居顶点已经被扩展了K次。即，对于当前查询，在先前迭代期间，终止于邻居顶点的K条中间路径已经到达优先级队列的头部并从优先级队列中被移除。后续步骤903-906仅针对尚未扩展K次的邻居顶点发生。

在步骤903中扩展中间路径以生成包含中间路径和终止于邻居顶点的边的新路径。

如果邻居顶点是目标顶点C，那么新路径是解路径，尽管不一定是前几条解路径。步骤904计算新路径的长度并检测邻居顶点是否是目标顶点C。如果新路径是解路径，那么步骤904还检测是否保证前K条最短路径包括新路径，如果新路径的长度小于优先级队列的新头部的成本，就是这种情况，其中成本是指包含优先级队列的新头部的最短解路径的预测长度。在K-A星搜索的早期迭代中，当优先级队列的新头部插入优先级队列的某个位置时，该成本先前已计算并存储。因为优先级队列的新头部会影响步骤904，所以即使优先级队列不为空，步骤904也可以检测到前k条最短路径。

在排除循环的实施例中，步骤905-906仅对步骤903中生成的不终止于目标顶点C的新路径发生。换句话说，步骤905-906对作为中间路径的新路径发生，但是不适用于作为解路径的新路径。包括包含目标顶点C的循环的实施例可以执行步骤905-906，其中识别出的解路径被进一步处理为中间路径。

步骤905基于界标顶点、目标顶点C和步骤902的邻居顶点进行懒惰三角测量。如果对邻居顶点的三角测量被急切地计算和/高速或缓存，那么针对邻居顶点跳过步骤905。但是，步骤902的当前顶点可以具有需要三角测量的其它邻居顶点。

步骤906基于从中间顶点到目标顶点的估计距离计算在步骤902中生成的新路径的成本。成本是包含新路径的最短解路径的预测长度，这需要将新路径的长度添加到从步骤902的邻居顶点到目标顶点C的距离下限。

在K-A星搜索900的每次迭代中执行一次步骤902，其使中间路径出队，并且在该迭代中，对出队的中间路径的最后一个顶点的每个邻居顶点执行步骤903-906。在任何情况下，K-A星搜索900一直迭代到指定K条最短路径，如步骤907所示，或者直到优先级队列下溢。例如，K-A星搜索900可以识别至少K条解路径，而不知道这是否包括前k条最短路径。例如，K-A星搜索900可以：a)甚至在生成前k条最短路径之后进行迭代，以及b)仅在附加迭代之后(诸如在优先级队列下溢之前或之后)明确指定已经生成的前k条最短路径，这可以在估计的上限明显不准确时会发生。

硬件概述

根据一个实施例，本文描述的技术由一个或多个专用计算设备实现。专用计算设备可以是硬连线的以执行这些技术，或者可以包括数字电子设备(诸如被持久地编程为执行这些技术的一个或多个专用集成电路(ASIC)或现场可编程门阵列(FPGA))，或者可以包括被编程为根据固件、存储器、其它存储装置或组合中的程序指令执行这些技术的一个或多个通用硬件处理器。这种专用计算设备还可以将定制的硬连线逻辑、ASIC或FPGA与定制编程相结合，以实现这些技术。专用计算设备可以是台式计算机系统、便携式计算机系统、手持设备、联网设备或者结合硬连线和/或程序逻辑以实现这些技术的任何其它设备。

例如，图10是图示可以在其上实现本发明实施例的计算机系统1000的框图。计算机系统1000包括总线1002或用于传送信息的其它通信机制，以及与总线1002耦合以处理信息的硬件处理器1004。硬件处理器1004可以是例如通用微处理器。

计算机系统1000还包括耦合到总线1002的主存储器1006，诸如随机存取存储器(RAM)或其它动态存储设备，用于存储将由处理器1004执行的信息和指令。主存储器1006还可以用于存储在执行由处理器1004执行的指令期间的临时变量或其它中间信息。当存储在处理器1004可访问的非瞬态存储介质中时，这些指令使计算机系统1000成为被定制以执行指令中指定的操作的专用机器。

计算机系统1000还包括耦合到总线1002的只读存储器(ROM)1008或其它静态存储设备，用于存储用于处理器1004的静态信息和指令。存储设备1010(诸如磁盘、光盘或固态驱动器)被提供并耦合到总线1002，用于存储信息和指令。

计算机系统1000可以经由总线1002耦合到显示器1012(诸如阴极射线管(CRT))，用于向计算机用户显示信息。包括字母数字键和其它键的输入设备1014耦合到总线1002，用于将信息和命令选择传送到处理器1004。另一种类型的用户输入设备是光标控件1016(诸如鼠标、轨迹球或光标方向键)，用于将方向信息和命令选择传送到处理器1004并用于控制显示器1012上的光标移动。这种输入设备通常在两个轴上具有两个自由度，第一轴(例如，x)和第二轴(例如，y)，这允许设备指定平面中的位置。

计算机系统1000可以使用定制的硬连线逻辑、一个或多个ASIC或FPGA、固件和/或程序逻辑(它们与计算机系统相结合，使计算机系统1000成为或将计算机系统1000编程为专用机器)来实现本文所述的技术。根据一个实施例，响应于处理器1004执行包含在主存储器1006中的一个或多个指令的一个或多个序列，计算机系统1000执行所述的技术。这些指令可以从另一个存储介质(诸如存储设备1010)读入到主存储器1006中。包含在主存储器1006中的指令序列的执行使得处理器1004执行本文所述的处理步骤。在替代实施例中，可以使用硬连线的电路系统代替软件指令或与软件指令组合使用。

如本文使用的术语“存储介质”是指存储使机器以特定方式操作的数据和/或指令的任何非瞬态介质。这种存储介质可以包括非易失性介质和/或易失性介质。非易失性介质包括例如光盘、磁盘或固态驱动器，诸如存储设备1010。易失性介质包括动态存储器，诸如主存储器1006。存储介质的常见形式包括例如软盘、柔性盘、硬盘、固态驱动器、磁带或任何其它磁数据存储介质、CD-ROM、任何其它光学数据存储介质、任何具有孔图案的物理介质、RAM、PROM和EPROM、FLASH-EPROM、NVRAM、任何其它存储器芯片或盒式磁带。

存储介质不同于传输介质但可以与传输介质结合使用。传输介质参与在存储介质之间传送信息。例如，传输介质包括同轴电缆、铜线和光纤，包括包含总线1002的导线。传输介质也可以采用声波或光波的形式，诸如在无线电波和红外数据通信期间生成的那些。

各种形式的介质可以参与将一个或多个指令的一个或多个序列传送到处理器1004以供执行。例如，指令最初可以在远程计算机的磁盘或固态驱动器上携带。远程计算机可以将指令加载到其动态存储器中，并使用调制解调器通过电话线发送指令。计算机系统1000本地的调制解调器可以在电话线上接收数据并使用红外发送器将数据转换成红外信号。红外检测器可以接收红外信号中携带的数据，并且适当的电路系统可以将数据放在总线1002上。总线1002将数据传送到主存储器1006，处理器1004从主存储器1006检索并执行指令。由主存储器1006接收的指令可以可选地在由处理器1004执行之前或之后存储在存储设备1010上。

计算机系统1000还包括耦合到总线1002的通信接口1018。通信接口1018提供耦合到网络链路1020的双向数据通信，其中网络链路1020连接到本地网络1022。例如，通信接口1018可以是集成服务数字网(ISDN)卡、电缆调制解调器、卫星调制解调器或者提供与对应类型的电话线的数据通信连接的调制解调器。作为另一个示例，通信接口1018可以是局域网(LAN)卡，以提供与兼容LAN的数据通信连接。还可以实现无线链路。在任何此类实现中，通信接口1018都发送和接收携带表示各种类型信息的数字数据流的电信号、电磁信号或光信号。

网络链路1020通常通过一个或多个网络向其它数据设备提供数据通信。例如，网络链路1020可以提供通过本地网络1022到主计算机1024或到由互联网服务提供商(ISP)1026操作的数据设备的连接。ISP 1026进而通过全球分组数据通信网络(现在通常称为“互联网”1028)提供数据通信服务。本地网络1022和互联网1028都使用携带数字数据流的电信号、电磁信号或光信号。通过各种网络的信号以及网络链路1020上并通过通信接口1018的信号(其将数字数据携带到计算机系统1000和从计算机系统1000携带数字数据)是传输介质的示例形式。

计算机系统1000可以通过(一个或多个)网络、网络链路1020和通信接口1018发送消息和接收数据，包括程序代码。在互联网示例中，服务器1030可以通过互联网1028、ISP1026、本地网络1022和通信接口1018发送对应用程序的所请求代码。

接收到的代码可以在被接收到时由处理器1004执行，和/或存储在存储设备1010或其它非易失性存储器中以供稍后执行。

软件概述

图11是可以用于控制计算系统1000的操作的基本软件系统1100的框图。软件系统1100及其组件，包括它们的连接、关系和功能，仅仅是示例性的，并且不意味着限制(一个或多个)示例实施例的实现。适于实现(一个或多个)示例实施例的其它软件系统可以具有不同的组件，包括具有不同的连接、关系和功能的组件。

软件系统1100用于指导计算系统1000的操作。可以存储在系统存储器(RAM)1006和固定存储装置(例如，硬盘或闪存)1010上的软件系统1100包括内核或操作系统(OS)1110。

OS 1110管理计算机操作的低级方面，包括管理进程的执行、存储器分配、文件输入和输出(I/O)以及设备I/O。表示为1102A、1102B、1102C...1102N的一个或多个应用可以被“加载”(例如，从固定存储装置1010传送到存储器1006中)以供系统1100执行。意图在计算机系统1000上使用的应用或其它软件也可以被存储为可下载的计算机可执行指令集，例如，用于从互联网位置(例如，Web服务器、app商店或其它在线服务)下载和安装。

软件系统1100包括图形用户界面(GUI)1115，用于以图形(例如，“点击”或“触摸手势”)方式接收用户命令和数据。进而，这些输入可以由系统1100根据来自操作系统1110和/或(一个或多个)应用1102的指令来操作。GUI 1115还用于显示来自OS 1110和(一个或多个)应用1102的操作结果，用户可以提供附加的输入或终止会话(例如，注销)。

OS 1110可以直接在计算机系统1000的裸硬件1120(例如，(一个或多个)处理器1004)上执行。可替代地，管理程序或虚拟机监视器(VMM)1130可以插入在裸硬件1120和OS1110之间。在这个配置中，VMM 1130充当OS 1110与计算机系统1000的裸硬件1120之间的软件“缓冲”或虚拟化层。

VMM 1130实例化并运行一个或多个虚拟机实例(“客人机”)。每个客人机包括“客人”操作系统(诸如OS 1110)，以及被设计为在客户操作系统上执行的一个或多个应用(诸如(一个或多个)应用1102)。VMM 1130向客人操作系统呈现虚拟操作平台并管理客人操作系统的执行。

在一些情况下，VMM 1130可以允许客人操作系统如同其直接在计算机系统1100的裸硬件1120上运行一样运行。在这些实例中，被配置为直接在裸硬件1120上执行的客人操作系统的相同版本也可以在VMM 1130上执行而无需修改或重新配置。换句话说，VMM 1130可以在一些情况下向客人操作系统提供完全硬件和CPU虚拟化。

在其它情况下，客人操作系统可以被专门设计或配置为在VMM 1130上执行以提高效率。在这些实例中，客人操作系统“意识到”它在虚拟机监视器上执行。换句话说，VMM1130可以在某些情况下向客户操作系统提供半虚拟化。

计算机系统进程包括硬件处理器时间的分配，以及存储器的分配(物理和/或虚拟)、用于存储由硬件处理器执行的指令的存储器的分配，用于存储由硬件处理器执行指令所生成的数据，和/或用于当计算机系统进程未运行时在硬件处理器时间的分配之间存储硬件处理器状态(例如，寄存器的内容)。计算机系统进程在操作系统的控制下运行，并且可以在计算机系统上执行的其它程序的控制下运行。

云计算

本文一般地使用术语“云计算”来描述计算模型，该计算模型使得能够按需访问计算资源的共享池，诸如计算机网络、服务器、软件应用和服务，并且允许以最少的管理工作或服务提供商交互来快速提供和释放资源。

云计算环境(有时称为云环境或云)可以以各种不同方式实现，以最好地适应不同要求。例如，在公共云环境中，底层计算基础设施由组织拥有，该组织使其云服务可供其它组织或公众使用。相反，私有云环境一般仅供单个组织使用或在单个组织内使用。社区云旨在由社区内的若干组织共享；而混合云包括通过数据和应用可移植性绑定在一起的两种或更多种类型的云(例如，私有、社区或公共)。

一般而言，云计算模型使得先前可能由组织自己的信息技术部门提供的那些职责中的一些代替地作为云环境内的服务层来输送，以供消费者使用(根据云的公共/私人性质，在组织内部或外部)。取决于特定实现，由每个云服务层提供或在每个云服务层内提供的组件或特征的精确定义可以有所不同，但常见示例包括：软件即服务(SaaS)，其中消费者使用在云基础设施上运行的软件应用，同时SaaS提供者管理或控制底层云基础设施和应用。平台即服务(PaaS)，其中消费者可以使用由PaaS的供应者支持的软件编程语言和开发工具，以开发、部署和以其它方式控制它们自己的应用，同时PaaS提供者管理或控制云环境的其它方面(即，运行时执行环境下的一切)。基础设施即服务(IaaS)，其中消费者可以部署和运行任意软件应用，和/或提供进程、存储装置、网络和其它基础计算资源，同时IaaS提供者管理或控制底层物理云基础设施(即，操作系统层下面的一切)。数据库即服务(DBaaS)，其中消费者使用在云基础设施上运行的数据库服务器或数据库管理系统，同时DbaaS提供者管理或控制底层云基础设施和应用。

为了说明可以用于实现(一个或多个)示例实施例的基本底层计算机组件而呈现的上述基本计算机硬件和软件以及云计算环境。但是，(一个或多个)示例实施例不必限于任何特定的计算环境或计算设备配置。代替地，根据本公开，(一个或多个)示例实施例可以在本领域技术人员将理解为能够支持本文呈现的(一个或多个)示例实施例的特征和功能的任何类型的系统体系架构或处理环境中实现。

在前面的说明书中，已经参考众多具体细节描述了本发明的实施例，这些细节可以从实现到实现有所变化。因而，说明书和附图应被视为说明性而非限制性的。本发明范围的唯一和排他性指示，以及申请人意图作为本发明范围的内容，是以发布这种权利要求书的具体形式从本申请发布的权利要求书集合的字面和等同范围，包括任何后续更正。