图形数据库更适合最短路径算法吗？
我的目标是为道路网络编写最短路径算法。
目前我的架构是这样的：我将所有数据存储在启用PostGIS的PostgreSQL数据库中。 我做了一个SELECT * FROM ways ，这个SELECT * FROM ways在具有100,000条边的表上（方式）占用不到3秒，之后我将（Java，Ruby或基于任何东西的）最短路径算法应用到已驻留在内存中的图。 在具有100,000条边的图表上，第二个操作可能需要约1.5秒。
所以，它需要：
这与pgRouting非常类似（据我所知，它使用C Boost将图存储在内存中），除了pgRouting总共花费大约2秒来计算同一数据集上的最短路径（是的，它是快速的，但是这对我来说是一个黑匣子，所以我需要我自己的）。
但最近我发现了Graph数据库和Neo4j。 在他们的网站上，他们声称“仍然能够以亚秒级的速度在数百万道路和航点的图表上进行这些计算，这使得在许多情况下可以放弃使用K / V商店的预计算索引的正常方法，并且能够将路由放到关键路径上，以适应现场条件并构建高度个性化和动态的空间服务。“
所以问题是：在我的特定问题下图形数据库会更快吗？
该问题具有以下属性：
如果您使用任何图形数据库（如Neo4j），您肯定不必重新发明轮子。 许多最短路径算法都是内置于此的，它旨在处理复杂性，以防在任何特定道路，单向道路，道路得分等情况下考虑速度限制。如何在数据增长时跟上性能10次，或者100次。 考虑到你的总计算时间为3秒，对于100,000种方式，它可以在1M分钟内进行，而在Neo4j中，响应将以毫秒为单位。
我没有使用“图表”数据库的经验，但是根据你的问题来判断，我有一些想法。
首先，直截了当的答案将是“创建这样一个图形数据库，并与您的解决方案进行性能比较”。 您可以测量内存使用情况，执行时间（速度），CPU利用率和/或其他度量标准。 这将为您提供足够的数据来做出决定。
我的其他建议是修改你的方法。 您所描述的三个问题属性（一个表，加载所有路径并且不需要可伸缩性）适用于您当前的域，但不适用于图数据库的一个。 这是一个完全不同的编程范例，您可能需要调整和调整您的方法以适应这些特殊类型数据库的领域。 如果您在非标准环境中应用标准方法（如图形数据库），那么执行性能或任何其他类型的比较是不合理的。
回顾：将问题转换为图形数据库的条款并相应地进行建模。 做完这些之后，对两种解决方案进行性能比较。
我敢打赌，假设您已经为图形数据库适当地转换并建模了问题，它会为您提供更好的性能。 “存储读取排序”的经典方法很简单，但除非积极优化才有效。
图形数据库的突破不仅仅是性能，它更多的是关于概念：你的路由算法处理单个关系图 （即图是链接都是相同类型的），而图形数据库则是多关系图 。
这使您可以计算仅采用特定类型边缘或避免其他类型的节点之间的最短路径。
有关更多信息，您应该阅读关于图db中的代数和管道概念。
我强烈建议thinkerpop项目从图形数据库开始。
链接地址: http://www.djcxy.com/p/54137.html上一篇: Is a graph database better for shortest paths algorithms?