如何存储稀疏邻接矩阵

Question

我读了几个话题，但是我迷失了。我对这个非常新。我想存储巨大的稀疏矩阵，并有几个想法，但可以在它们之间进行选择。以下是我的需求：

1. 大约5000万个顶点的邻接矩阵。
2. 每个顶点的最大邻居数-大约10,000个。
3. 每个顶点的平均邻居数-大约200-300个。
4. 快速行查询-向量将与此矩阵相乘。
5. O(1)复杂度添加边缘。
6. 很可能不会删除边缘。
7. v相邻的顶点的枚举-尽可能快。
8. 可移植性-必须有一种方法将基础从一个计算机转移到另一个计算机。

所以，这是我的想法：

1. 巨大的表格，其中包含成对的（行，列）。非常简单，但是至少枚举顶点将是O(log N)，其中N是表的大小。我认为它相当慢。此外，必须对其进行索引。每个RDBMS都适用于此。
2. 大量列表：每个顶点一个列表。非常快的枚举，但是存储这些列表需要大量资源吗？此外，我不确定在这种情况下要使用哪个DBMS：可能是一些NoSql？
3. 巨大的表格（行|列集）。两者的组合。我不确定是否有任何RDBMS支持任意集合。你知道吗？也许NoSql在这里很有用？
4. 邻接列表的集合。任何RDBMS都适用于该集合，并且在复杂度方面的成本很好，但它们可以被针对一个顶点的多个请求杀死。
5. HDF5-我认为由于I/O而慢。
6. Neo4j-据我所知，它将数据存储在双向列表中，因此实际上与＃4相同，我对吗？

请帮我选择或提供更好的决策。

如果我在某些地方的估计错误，请纠正我。

- ov7a

Answer 1

一个混合使用neo4j / hbase的方法可能会很有效，其中neo4j优化图处理方面，而hbase则在可扩展性方面承担重任-例如存储大量额外属性。

neo4j包含节点和关系。从可扩展性方面来看，它可能足够好了。我在独立非neo4j网站上的调查声称，在单台机器上有数十亿个节点/关系，并且遍历性能比RDBMS高几个数量级。

但是......如果需要更多的可扩展性，您可以引入hbase大型设备来存储非关系/节点标识符的额外属性。然后，仅将hbase rowkey添加到neo4j节点信息中，以便在应用程序需要时进行查找。

- WestCoastProjects

Answer 2

最终，我实现了方案一。

我使用了两个表格的PostgreSQL：一个用于边缘，有两个列 - 起点/终点，另一个用于顶点，其中每个顶点编号是唯一的，并且还有一些用于描述顶点的列。

我基于pg_advisory_xact_lock实现了upsert。虽然速度有点慢，但对我来说足够了。

此外，从此配置中删除顶点很麻烦。

为了加快乘法运算的速度，我将边缘表格导出到文件中。它甚至可以放置在x64机器上的RAM中。

公平地说，数据量比我预期的少。总共只有7百万个顶点和1.6亿条边，而不是50百万个顶点和平均每个顶点的200-300条边。

- ov7a

---

是的，您更改了要求的基本前提 - 可扩展性方面。您的解决方案将无法满足原始要求。也许您至少可以点赞我的解决方案，因为它是唯一一个符合OP标准的“可行”解决方案。 - WestCoastProjects

可扩展性并不是问题。你为什么这么认为？因为数据量很大吗？最终，我的解决方案虽然运行速度比我想象的慢，但仍然让我满意。 你测试过你的解决方案吗？为什么你认为它是唯一可行的方案？ - ov7a

根据您的要求：大约有5000万个顶点的邻接矩阵，每个顶点有200-300个邻居。您自己承认，您在postrgres上的解决方案不支持这一点。 - WestCoastProjects

是的，你说得对，但是在OP中并没有水平扩展的要求。也许我误解了你的意思。你能具体说明一下吗？ - ov7a

我的评论是：对于更新后的160兆行需求，您的解决方案可能很好。但考虑到原始问题涉及100亿个边缘，水平可扩展性就变得非常重要，这时可能需要另一种解决方案。如果您将参数更改为原始问题（160兆与100亿兆），也许应该考虑给那些解决原始问题的答案以信任。 - WestCoastProjects

好的，现在我明白你的意思了。谢谢你澄清事情。 - ov7a