用于存储稀疏矩阵的数据库

Question

我有一个非常大且非常稀疏的矩阵，仅由0和1组成。然后，我基本上处理（行列）对。每行/列最多有10k对。

我需要有以下几种：

• 的（行 - 列）对并行插入

• 整行或整列的快速检索

• 快速查询的存在（行 - 列）对

• 如果可能，Ruby客户端

---

是否存在适用于这些约束的现有数据库？

如果没有，你会得到我最好的表现：

• SQL数据库，像这样的表：

row(indexed) | column(indexed)（但指标就必须不断刷新）

• 甲NoSQL的键值存储，具有两个表所示：

row => columns ordered list

column => rows ordered list

（但元素平行插入到列表）

• 别的东西

感谢您的帮助！

Answer 1

一个稀疏的0/1矩阵听起来像adjacency matrix，这是用来表示图形。基于此，您可能正在尝试解决某些图形问题，并且图形数据库可以满足您的需求。

图形数据库，如Neo4J，对于图的快速遍历非常有用，因为检索顶点的邻居需要O（给定顶点的邻居数），所以它与顶点数无关整个图。 Neo4J也是事务性的，所以并行插入不是问题。您可以在MRI Ruby中使用​​，或使用JRuby library进行更加无缝的集成。另一方面，如果您试图分析图中的连接，并且足够在一段时间内完成该分析并且只是提供可用的结果，那么您可以尝试使用框架的运气。基于Google Pregel的图表处理。它有点像Map-Reduce，但是针对图形处理。已经有several open source implementations of that paper。但是，如果图形数据库或图形处理框架不适合您的需要，我建议看看HBase，它是一个基于Google BigTable的开源，面向列的数据存储。它的数据模型实际上与您所描述的非常相似（稀疏矩阵），它具有行级别的事务，并且不需要您检索整行，只是为了检查某个特定的对是否存在。有一些Ruby libraries for that database，但我想像使用JRuby而不是MRI与它进行交互会更安全。

Answer 2

如果您的矩阵真的很稀疏（即节点只有少量互连），那么您将从RDBMS（如Oracle，PostgreSQL或SQL Server）获得相当高效的存储。基本上你会有一个包含两个字段（行，列）和一个索引或键的表。

单向设置主键（取决于您是否主要按行或列进行查询），并且相反地在字段上创建另一个索引。这将只存储连接存在的数据，并且它将与图中的边数成正比。

索引将允许您高效地检索行或列，并始终保持同步。

如果每个节点有10,000个节点和10个连接，则数据库将只有100,000个条目。每节点100个ednges将有1,000,000个条目等等。对于稀疏连接，这应该相当有效。

背的-FAG分组估计

该表将基本上具有行和列的字段。如果聚集索引变为（行，列，值），则另一个覆盖索引将变为（列，行，值）。如果增加和删除是随机的（即，不按行或列进行分批），I/O将近似于表格的两倍。

如果按行或列对插入进行批处理，那么您将在其中一个索引上获得更少的I/O，因为记录物理上位于其中一个索引中。如果矩阵实际上是稀疏的，那么这个邻接列表表示是迄今为止最紧凑的存储方式，这比将其存储为二维数组要快得多。

具有64位值的10,000 x 10,000矩阵需要800MB加上行索引。更新一个值需要写入每个写入至少80k（写出整行）。如果数据可以按插入行分组，则可以按行优化写入。如果插入是实时和随机的，那么您将为每个插入写出80k行。

实际上，这些写操作会有一定的效率，因为这些写操作都将被写入大部分连续的区域，具体取决于您的NoSQL平台如何物理存储其数据。

我不知道如何稀疏连接，但如果每个节点平均有100个连接，那么您将拥有1,000,000条记录。这将大约每行16字节（Int4行，Int4列，Double值）加上聚集表和覆盖索引的几个字节开销。这种结构大约需要32MB +的存储空间。

假设插入不是行或列排序，更新行或列上的单个记录将导致两个单个磁盘块写入（8k，实际上是一个段）用于随机访问。

将100万个随机排序的条目添加到数组表示会导致大约80GB的写入量+少量开销。向邻接列表表示中添加1m条目会导致大约32MB的写入（实践中为16GB，因为整个数据块将写入每个索引叶节点），再加上一点开销。

对于该级别的连接（每个节点有10,000个节点，100个边），邻接列表 在存储空间中可能更高效，也可能在I/O中更高效。您将从该平台获得一些优化，因此某种基准可能适用于查看哪些在实践中更快。