8

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

目前我的架构是这样的：我将所有数据存储在启用 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 存储预计算索引的正常方法，并能够将路由置于关键路径，以适应生活条件，构建高度个性化和动态的空间服务。”

所以问题是：对于我的特定问题，图形数据库会更快吗？

该问题具有以下性质：

  • 数据库由一张表（方式）组成；
  • 对数据库的唯一查询是将所有方式都放入内存（以构建图形）；
  • 我不需要可扩展性，即图形很可能不会增长。
4

4 回答 4

3

图数据库的突破不仅在于性能，更在于概念：您的路由算法处理单个关系图（即图是链接都是相同类型的），而使用图数据库，您有一个多关系图。

这使您能够计算仅采用特定类型边缘或避免其他类型的节点之间的最短路径。

有关更多信息，您应该阅读有关图形数据库背后的代数和管道概念的信息。

我强烈推荐thinkerpop项目从图形数据库开始。

于 2013-04-11T12:21:00.343 回答
3

如果您使用任何图形数据库，例如 Neo4j，您当然不必重新发明轮子。许多最短路径算法内置于其中，旨在处理复杂性，以防您必须考虑任何特定道路、单向道路、道路得分等的速度限制。当数据增长时，您如何跟上性能 10次，或者，100次。考虑到 100,000 种方式的总计算时间为 3 秒，对于 1M 种方式，它可能以分钟为单位，而在 Neo4j 中，响应将以毫秒为单位。

于 2013-01-23T03:19:43.307 回答
1

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

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

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

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

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

于 2011-08-01T11:19:14.627 回答
0

图形数据库最初可能不会将所有数据加载到内存中，但随着时间的推移，好的数据库旨在处理超大型数据集。但是，一旦数据存在，图形数据库在遍历链接时所要做的工作就比关系数据库要少。这是因为它可以使用它们的身份直接访问相关对象，而不必使用 B-tree 索引和（可能）连接表，因此一旦节点和边被缓存，它应该会更快。

于 2011-08-05T22:12:31.027 回答