图表数据库更适合最短路径算法吗？

Question

我的目标是为道路网络编写最短路径算法.

目前我的架构是这样的:我将所有数据存储在启用PostGIS的PostgreSQL数据库中.我做了一个SELECT * FROM ways,在一个有100,000个边缘(方式)的表上花了不到3秒钟,然后我将(Java,Ruby或任何基于任何东西的)最短路径算法应用于已经驻留在内存中的图形.在具有100,000个边缘的图形上,第二个操作可能需要大约1.5秒.

所以,它需要:

• 2-3秒将数据库中的所有路径加载到内存中并创建图形(节点以方式(边缘)存储在一个表中);
• 1-1.5秒计算已经在内存中的图形上的最短路径.

这与pgRouting非常相似(根据我的知识,它使用C Boost将图形存储在内存中),除了pgRouting总计大约需要2秒来计算同一数据集上的最短路径(是的,它很快,但是对我来说这是一个黑盒子,所以我需要自己的).

但最近我发现了Graph数据库和Neo4j.在他们的网站上,他们声称"仍然能够在数百万道路和航路点的图表上以亚秒速度进行这些计算,这使得在许多情况下放弃使用K/V存储预先计算索引的正常方法并且能够将路由放入关键路径,可以适应现场条件,建立高度个性化和动态的空间服务."

所以问题是:对于我的特定问题,图表数据库会更快吗？

该问题具有以下属性:

• 数据库由一个表(方式)组成;
• 对数据库的唯一查询是获取进入内存的所有方法(构建图形);
• 我不需要可伸缩性,即图形可能不会增长.

Answer 1

我没有“图形”数据库的经验，但从你的问题来看，我有一些想法。

首先，简单的答案是“创建这样一个图形数据库并与您的解决方案进行性能比较”。您可以测量内存使用情况、执行时间（速度）、CPU 利用率和/或可能的其他指标。这将为您提供足够的数据来做出决定。

我的另一个建议是修改你的方法。您描述的三个问题属性（一张表，加载所有路径且不需要可扩展性）适用于您当前的域，但不适用于图形数据库的域。这是一种完全不同的编程范例，您可能必须调整和调整您的方法以适应这些特殊类型数据库的领域。如果您在非标准环境（例如图形数据库）中应用标准方法，则进行性能或任何其他类型的比较是不合理的。

回顾：将您的问题转换为图形数据库的术语并相应地对其进行建模。完成此操作后，对两种解决方案进行性能比较。

我敢打赌，假设您针对图形数据库适当地翻译和建模了您的问题，它将为您带来更好的性能。“存储-读取-排序”的经典方法很简单，但除非积极优化，否则不会那么有效。