动态规划的二分图分布式处理 <?>

Question

我正在尝试找出在分布式（更准确地说是 FaaS）环境中处理文档的有效算法。

暴力破解方法为 O(D * F * R)，其中：

D 是要处理的文档数量
F 是过滤器的数量
R 是单个过滤器中规则的最高数量

我可以假设：

单个过滤器不超过10条规则
一些过滤器可能共享规则（所以它是 N 对 N 的关系）
规则是布尔函数（谓词）所以我可以尝试利用早期切割，这意味着如果我有 f() && g() && h() 和 f() 评估为false 那么我根本不需要处理 g() 和 h() 并且可以 return false 立即。
在单个文档中，字段数量始终相同（大约 5-10 个）
过滤器、规则和文档已经在数据库中
每个过滤器至少有一个规则

使用共享（第二个假设）我有一个想法，首先针对每个规则处理文档，然后（完成后）使用已计算的规则计算结果对每个过滤器进行处理。这样，如果 Rule 被共享，那么我只计算一次。但是，它没有利用早期切割（第三个假设）。

第二个想法是使用早期切割作为稍微优化的暴力破解，但它不会使用规则共享。

规则共享看起来像子问题共享，因此记忆和动态规划可能会有所帮助。

我注意到，Filter-Rule 关系是二分图。不太确定它是否可以帮助我。我还注意到，我可以使用反向集并在每个规则存储中使用相应的集。然而，这会产生循环依赖，并可能导致数据库中的不同步问题。

默认的想法是文档是流式的，每个文档都是事件，将创建 FaaS 实例来处理它。但是，这可能会强制每个 FaaS 实例查询所有过滤器，由于 Shared-Nothing 架构，这使我的查询时间为 O(F * D)。

示例过滤器：

{
    'normalForm': 'CONJUNCTIVE',
    'rules':
    [
        {
            'isNegated': true,
            'field': 'X',
            'relation': 'STARTS_WITH',
            'value': 'G',
        },
        {
            'isNegated': false,
            'field': 'Y',
            'relation': 'CONTAINS',
            'value': 'KEY',
        },
}

或更简洁的形式：

document -> !document.x.startsWith("G") && document.y.contains("KEY")

文档：

{
    'x': 'CAR',
    'y': 'KEYBOARD',
    'z': 'PAPER',
}

计算结果为真。

我可以稍微更改数据模型，流式传输其他内容而不是文档（例如过滤器），并使用任何 nosql 数据库和工具来帮助它。 Apache Flink（事件处理）和 MongoDB（使用其规则检索过滤器的单个查询）或者 Neo4j（模型看起来像二分图）看起来可以帮助我，但不确定。

是否可以有效地处理它（关于 - 可能 - 数据库查询）？什么工具合适？

我也一直在想，我是否正在尝试解决一些可能具有有用的定理和算法的更一般（数学）问题的特例。

编辑：我的最新想法：像 Redis 一样在缓存中收集所有文档。然后单个事件启动并发布 N 个函数（如函数即服务），每个函数选择 F/N（过滤器的数量除以实例数 - 所以只需在实例之间均匀分布过滤器）这样每个过滤器都是仅从数据库中获取一次。

现在，每个实例都从缓存中流式传输所有文档（一个文档应该小于 1MB，同时我应该有 1-10k，所以应该适合缓存）。这样每个文档只从数据库中选择一次（缓存）。

我已经减少了数据库读取操作（仍然有一些规则被多次选择），但我仍然没有利用过滤器之间的规则共享。我可以使用文档数据库故意忽略它。这样通过选择过滤器我也将得到它的规则。仍然 - 我必须重新计算它的价值。

我想这就是我使用 Shared Nothing 可扩展架构的结果？

Answer 1

我意识到虽然我的图确实（理论上）是二分图，但（在实践中）它将是一组不相交的二分图（因为并非所有规则都将被共享）。这意味着，我可以在不同的 FaaS 实例上独立处理那些不相交的部分，而无需重新计算相同的规则。

这将我的问题简化为处理单个二分连通图。现在，我可以利用动态规划的好处，并且只有在我共享内存的情况下才能共享规则计算的结果，所以我不能在不牺牲这个好处的情况下进一步划分（和分配）这个问题。所以我这样想：如果我已经决定，我将不得不重新计算一些规则，然后让它比我将得到的不相交的部分低。

这实际上是最小割问题，具有（幸运的）多项式复杂度已知算法。

但是，这对我来说可能并不理想，因为我不想切割图的任何部分 - 我想理想地把图切成两半（分而治之策略，可以递归地重新应用直到图将非常小，可以在具有时间限制的 FaaS 实例中在几秒钟内处理。

这意味着，我正在寻找切割，这将创建两个不相交的二分图，每个图可能具有相同数量的顶点（或至少相似）。

这是最稀疏的切割问题，即 NP-hard，但具有 O(sqrt(logN)) 近似算法，也有利于减少切割边缘。

目前，这看起来确实是我问题的解决方案，但我很乐意听到任何建议、改进和其他答案。

也许用其他数据模型或算法可以做得更好？也许我可以用一些定理进一步减少它？也许我可以将它转换为其他（更简单的）问题，或者至少更容易跨节点划分和分布？

这个想法和分析强烈建议使用图数据库。

动态规划的二分图分布式处理 <?>

Bipartite graph distributed processing with dynamic programming <?>

distributed-computing

dynamic-programming

event-handling

graph-algorithm

apache-flink