假设我有一个非常大的无向,未加权的图形(从数亿个顶点开始,每个顶点约10个边缘),非分布式和仅由单线程处理,并且我想对它进行广度优先搜索.我希望它们是I/O绑定的,因此我需要一个良好的BFS磁盘页面布局,磁盘空间不是问题.搜索可以以相同的概率在每个顶点上开始.直观地说,这意味着最小化不同磁盘页面上的顶点之间的边缘数量,这是图形分区问题.
图表本身看起来像一个意大利面,想到随机互连的随机点集,一些偏向于较短的边缘.
问题是,一个分区图如何大？我发现可用的图形分区器可以处理仅适合内存的图形.我找不到任何流图分区算法的描述和实现.
或者,也许有一种替代分区图,以获得适合BFS的磁盘布局？
现在作为近似,我使用这样的事实:顶点具有附加到它们的空间坐标,并以Hilbert排序顺序将顶点放在磁盘上.这种方式在空间上靠近顶点落在同一页面上,但它们之间的边缘的存在与否完全被忽略.我可以做得更好吗？
作为替代方案,我可以使用顶点的希尔伯特排序顺序将图形拆分为多个,将子图划分,将它们缝合并接受接缝处的不良分区.
我已经研究过的一些事情:
分区实现(除非我弄错了,所有这些都需要将图形放入内存中):
编辑:关于图表的样子以及BFS可以在任何地方开始的信息.编辑:分区子图的想法
我有大约3500个防洪设施,我想将其表示为确定流路径的网络(基本上是有向图).我目前正在使用SqlServer和CTE递归检查所有节点及其上游组件,只要上游路径不分叉,这就可以工作.然而,由于增加了上游复杂性,一些查询比其他查询指数长得多,即使它们在物理上不太远(即两个或三个"下游"段).在某些情况下,我会在杀死查询之前让它超过十分钟.我正在使用一个简单的双列表,一列是设施本身,另一列是第一列中列出的设施的上游设施.
我尝试使用当前工具添加索引以帮助加快速度,但这没有任何区别.并且,对于图中可能的连接,任何节点可以具有多个上游连接,并且可以从多个"下游"节点连接.
当然有可能在数据中有循环,但我还没有找到一种好的方法来验证这一点(除了CTE查询报告最大递归计数命中时;这些很容易修复).
所以,我的问题是,我存储这些信息是错误的吗？有没有比CTE更好的方法来查询上游点？