mysql - 如何存储和查询大量的矩阵？

Question

问题:

给定 k N x M 维矩阵(例如 M1 .. M5)。值是零和一个。您将如何找到与查询矩阵冲突的所有矩阵，例如问？碰撞意味着如果查询矩阵在与数据库中的矩阵相同的位置有一个“1”。

示例:

对于这个简单的例子，算法应该为查询找到 M1、M2、M3、M4 而不是 M5，因为没有与查询矩阵匹配的矩阵。

M1:                        M3:
+-----------------+        +-----------------+
| 0 0 0 0 0 0 0 0 |        | 0 0 0 0 0 0 0 1 |
| 0 1 1 0 0 0 0 0 |        | 0 0 0 0 0 0 0 0 |
| 0 1 1 0 0 1 1 0 |        | 0 0 1 0 0 0 0 0 |
| 0 0 0 0 0 0 0 0 |        | 0 0 1 0 0 0 0 1 |
+-----------------+        +-----------------+

M2:                        M4:
+-----------------+        +-----------------+
| 0 0 0 0 0 1 1 0 |        | 0 0 0 0 0 0 0 0 |
| 0 0 1 1 0 0 0 0 |        | 1 1 1 0 0 0 0 0 |
| 0 0 0 0 0 0 0 0 |        | 0 0 0 0 0 0 0 0 |
| 0 0 0 0 0 0 0 0 |        | 0 0 0 0 0 0 0 0 |
+-----------------+        +-----------------+

M5:
+-----------------+
| 0 0 0 0 0 0 0 0 |
| 0 0 0 0 1 0 0 0 |
| 0 0 0 0 0 1 0 0 |
| 0 0 0 0 0 0 0 0 |
+-----------------+

Q:
+-----------------+
| 0 0 0 0 0 0 0 0 |
| 0 0 1 0 0 0 0 0 |
| 0 0 1 0 0 0 0 0 |
| 0 0 0 0 0 0 0 0 |
+-----------------+

简单的解决方案:

遍历所有矩阵并进行按位与:

匹配:

     M1: 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0
      Q: 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
--------------------------------------------------------------------------
M1 && Q: 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 
--------------------------------------------------------------------------

不匹配:

     M5: 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
      Q: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
--------------------------------------------------------------------------
M5 && Q: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
--------------------------------------------------------------------------

问题:

1. 这可以在亚线性时间内完成吗？
2. 是否有比给定的朴素方法更好的算法？
3. 在数据库中存储和查询矩阵数据的好方法是什么？

问题 3 的注释: 我考虑过将矩阵的整数值存储在 MySQL 表中，并使用 MySQL 按位查询来查找它们。如果矩阵变得更大，例如，这会起作用(缩放)吗？ 100x100？

Answer 1

1 & 2. 次线性 ( < O(n*m) ) 解决方案可以使用稀疏矩阵方法并在第一次碰撞时终止。基本上在每一行都有一个索引列表，其中有一个 1 并查看是否存在冲突。从技术上讲，这可以是 O(n*m)，如果 Q 除了最后一列 1 之外都是 0，而 M 只是它的倒数。

3.这部分的答案取决于你的系统的限制和矩阵的组成方式。如果矩阵不稀疏，并且您正在查看内存使用情况，则可以将行存储为分解为 1 和 0 的整数集合。如果矩阵稀疏，您可以简单地存储一组点。