小步最短路径算法的经济价值

路径值存储分析

社交网络Facebook拥有约28亿活跃用户(2022年)，是目前世界上最大的社交网络。对于Dijkstra最短路径算法，若是用8字节存储节点路径长度，需要20.88 GB；对于小步最短路径算法，用1比特标记节点是否获取最短路径，需要0.326 GB。

互联网是世界上最大的网络之一。根据2022年的数据,互联网上约有63亿个独立主机(即连接到互联网的设备)。对于Dijkstra最短路径算法，若是用8字节存储节点路径长度，需要46.9 GB；对于小步最短路径算法，用1比特标记节点是否获取最短路径，需要0.733 GB。

神经网络:人脑是一个巨大的神经网络,据估计有860-1000亿个神经元。对于Dijkstra最短路径算法，若是用8字节存储节点路径长度，需要640.37 GB - 744.83 GB；；对于小步最短路径算法，用1比特标记节点是否获取最短路径，需要10 GB – 11.6 GB。

索引网页数量:根据最新的数据,目前主要搜索引擎(如谷歌、必应等)索引的网页数量大约在 600 - 800 亿页之间。实际网页数量由于存在许多未被索引的网页,实际的全球网页数量要远高于索引数量。一般估计实际网页数量在 1 - 5 万亿页左右。需要注意的是,这只是一个粗略的估计,因为网页数量是一个不断变化的动态指标。随着互联网的快速发展,新的网页不断被创建和发布,网页总数也在持续增加。

1小型服务器和工作站:内存容量通常在 4GB 到 128GB 之间，适用于中小型企业和个人工作站。2中型服务器:内存容量通常在 128GB 到 512GB 之间，适用于中大型企业的关键应用服务。3大型服务器:内存容量通常在 512GB 到 6TB 之间，适用于大型企业的数据库、大数据和虚拟化应用。4高端服务器:内存容量可超过 6TB，主要用于超大规模的数据处理、人工智能训练等。

服务器代价

1TB内存的服务器一年消耗的电能在2000美元左右，通常需要非常高的投资成本，具体的价格会根据硬件供应商、配置规格等因素而有所不同。一般来说, 配置1TB内存容量的服务器的价格大致在几万美元。除了内存容量,服务器的其他配置如处理器、存储、网络接口等,也会对最终价格产生影响。通常情况下,配置越高端,价格也会相应更高。这只是一个粗略的价格范围估计，实际价格可能会根据不同供应商和采购时间而有所波动。

对于搜索引擎这样的大型系统来说,1TB内存的服务器通常使用年限在5 年左右，这样既可以保持技术领先,又可以控制好硬件投资和运营成本。当然,实际使用年限也会根据具体的硬件配置、业务负载、维护保养等情况而有所不同。总的来说,服务器需要持续投入大量资金来更新和升级硬件,确保整个系统的高性能和可靠性。

数据集

1. bio-CE-CX bio-CE-GN bio-DM-CX bio-HS-CX bio-SC-HT
2. bio-human-gene1 bio-human-gene2 bio-mouse-gene bio-WormNet-v3
3. datagen-7_5-fb datagen-7_6-fb datagen-7_7-zf datagen-7_8-zf datagen-7_9-fb datagen-8_0-fb datagen-8_1-fb

https://ldbcouncil.org/benchmarks/graphalytics/

Dijkstra最短路径算法因为需要通过更新路径值，而需要把值保留在内存中。对于每个节点，小步最短路径算法只需要一个标记为，来标记该节点是否确定最短路径，所有我们可以用一个相对很小的连续内存空间，来存储所有节点的标记。对于计算出的节点的最短路径的值，可以批量地写到外存。通过两次映射，即先把节点ID映射到等价类ID和其内部元素ID，在计算最短路径后再映射回节点ID，小步最短路径算法可节省计算机的大量内存，并且还显著提高了算法的性能。

因为硬件的问题，我们只使用了规模较小的图，无法对更大的图进行测试。上述图测试结果是Dijkstra最短路径算法需要的时间/小步最短路径算法需要时间在1.5-5左右，其中，第一类图的比值在1.5-2左右，第二类图的比值在3-5左右，第一类图的比值在2-3左右。

使用小步最短路径算法的代价

需要进行数据的预处理，把节点聚类到等价类中并编码，用得到的编码存储和访问节点是否确定最短路径。这种编码具有非常好的扩展性，即对于变化的节点，可以不用重新计算整个图节点编码。