存储稀疏矩阵的数据库

Question

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

我的需求如下：

• 并行插入（行-列）对

• 快速检索整行或整列

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

• 如果可能的话，一个 Ruby 客户端

---

是否有适用于此类约束的现有数据库？

如果没有，什么能让我获得最佳性能：

• 一个 SQL 数据库，有一个这样的表：

row(indexed) | column(indexed) （但索引必须不断刷新）

• 一个 NoSQL 键值存储，有两个这样的表：

row => columns ordered list

column => rows ordered list

（但将元素并行插入到列表中）

• 别的东西

谢谢你的帮助！

Answer 1

一个稀疏的 0/1 矩阵对我来说就像一个邻接矩阵，用于表示一个图形。基于此，您可能正在尝试解决一些图形问题，而图形数据库将满足您的需求。

图数据库，如Neo4J，非常适合图的快速遍历，因为检索一个顶点的邻居需要 O（给定顶点的邻居数），所以它与整个图中的顶点数无关。Neo4J 也是事务性的，所以并行插入不是问题。您可以使用MRI Ruby 中的REST API 包装器，或使用JRuby 库进行更无缝的集成。

另一方面，如果您正在尝试分析图中的连接，并且偶尔进行一次分析并提供结果就足够了，您可以尝试使用基于谷歌预凝胶。它有点像 Map-Reduce，但针对的是图形处理。该论文已经有几个开源实现。

但是，如果图形数据库或图形处理框架不适合您的需求，我建议您查看HBase，它是一种基于Google BigTable的开源、面向列的数据存储。它的数据模型实际上与您描述的非常相似（稀疏矩阵），它具有行级事务，并且不需要您检索整行，只需检查是否存在某个对。该数据库有一些Ruby 库，但我认为使用 JRuby 而不是 MRI 与其交互会更安全。