假设我有一个非常大的无向、无权图(从数亿个顶点开始,每个顶点约有10条边),非分布式且仅由单个线程处理,并且我想在它上面进行广度优先搜索。我预计它们会受到I/O限制,因此我需要一个适用于BFS的磁盘页面布局,磁盘空间不是问题。搜索可以从每个顶点以相等的概率开始。直观地说,这意味着最小化不同磁盘页面上顶点之间的边数,这是一个图分区问题。
图本身看起来像一条意大利面条,想象一组随机连接的点,其中一些倾向于更短的边。
问题是,如何对这么大的图进行分区?我找到的可用图分区器只能处理适合内存的图。我找不到任何流图分区算法的描述或实现。
或者,也许有一种替代方法可以获得适用于BFS的磁盘布局?
现在作为近似值,我使用顶点附加的空间坐标,并按照希尔伯特排序顺序将顶点放在磁盘上。这样,空间接近的顶点会落在同一页上,但它们之间的边的存在或不存在完全被忽略了。我能做得更好吗?
另一种选择是,我可以使用希尔伯特排序顺序将图分成几个部分,对子图进行分区,然后将它们拼接在一起,并接受接缝处的较差分区。
我已经研究过一些东西:
图本身看起来像一条意大利面条,想象一组随机连接的点,其中一些倾向于更短的边。
问题是,如何对这么大的图进行分区?我找到的可用图分区器只能处理适合内存的图。我找不到任何流图分区算法的描述或实现。
或者,也许有一种替代方法可以获得适用于BFS的磁盘布局?
现在作为近似值,我使用顶点附加的空间坐标,并按照希尔伯特排序顺序将顶点放在磁盘上。这样,空间接近的顶点会落在同一页上,但它们之间的边的存在或不存在完全被忽略了。我能做得更好吗?
另一种选择是,我可以使用希尔伯特排序顺序将图分成几个部分,对子图进行分区,然后将它们拼接在一起,并接受接缝处的较差分区。
我已经研究过一些东西:
- 如何存储数十亿个节点和顶点的大型有向无权图
- http://neo4j.org/ - 我没有找到它如何在磁盘上进行图形布局的任何信息
分区实现(除非我弄错了,否则所有实现都需要将图形适合内存):
- http://glaros.dtc.umn.edu/gkhome/views/metis
- http://www.sandia.gov/~bahendr/chaco.html
- http://staffweb.cms.gre.ac.uk/~c.walshaw/jostle/
- http://www.cerfacs.fr/algor/Softs/MESHPART/
编辑:关于图形外观和 BFS 能够从任何位置开始的信息。 编辑:有关对子图进行分区的想法。