我目前有一个图,它有大约、1000万个节点、和--3500万个边缘。现在,完整的图表在程序开始时被加载到内存中。这需要几分钟(毕竟是Java ),并且需要大约半is的RAM。目前,它运行在一台带有双核处理器和4G内存的机器上。
当使用宽度优先搜索图时,内存使用量上升到1G的峰值,平均需要10秒。
我想把这个程序部署在几台电脑上。除了图搜索之外,这个功能所需的资源非常少。我的目标系统非常小,只有512兆内存。
对于如何在不消耗太多内存的情况下实现一个方法(可能使用数据库)来搜索该图,有什么建议吗?该程序大部分时间是空闲的,因为它正在访问一个硬件设备,所以路径查找可能需要大约5分钟对上述图形.
谢谢你对我提出的任何想法。
更新:
刚找到neo4j。有人知道它是否适合这种巨大的图形吗?
发布于 2010-02-13 18:26:39
你的问题有点模糊,但总的来说,一个好的策略主要是遵循广度优先语义,同时使用与深度优先搜索相同的内存量的策略是迭代深化。这样做的想法是,首先进行深度优先搜索,限制在1层;如果没有找到解决方案,从零开始,将其限制在2层;如果失败,则尝试3层,等等。
这在一开始看起来有点多余,但是由于您正在进行深度优先搜索,所以内存中的节点要少得多,并且总是比直接的广度优先搜索少搜索一个级别。由于一个级别中节点的数量呈指数增长,在较大的图上,很可能节省最后一个额外的级别,因为冗余地尝试前面的所有层是有回报的。
发布于 2010-02-13 21:32:31
我想说的是,当您有这样一个像样的大小图时,Neo4j绝对是一个很好的选择。它不仅有内置的BFS算法,还可以将数据持久化到磁盘上,从而缩短启动时间。
在highscalability.com:NEO4J -一个启动臀部的图形数据库上查看这个
我使用过Neo4j,它们的文档非常好,它们提供了一些很好的入门示例,确实只需要几分钟就能完成。
看看他们的- 10分钟开始指南
发布于 2014-04-17 15:56:41
Neo4j将数据作为图存储在数据库中,它将成为持久化的,您可以使用图遍历Api (BFS、DBS、A* Dijkstra . )或使用Cypher查询语言进行访问。
https://stackoverflow.com/questions/2258509
复制相似问题