Bipartite graph distributed processing with dynamic programming <?>

Question

I am trying to figure out efficient algorithm for processing Documents in distributed (FaaS to be more precise) environment.

Bruteforce approach would be O(D * F * R) where:

• D is amount of Documents to process

• F is amount of filters

• R is highest amount of Rules in single Filter

I can assume, that:

• single Filter has no more than 10 Rules

• some Filters may share Rules (so it's N-to-N relation)

• Rules are boolean functions (predicates) so I can try to take advantage of early cutting, meaning that if I have f() && g() && h() with f() evaluating to false then I do not have to process g() and h() at all and can return false immediately.

• in single Document amount of Fields is always same (and about 5-10)

• Filters, Rules and Documents are already in database

• every Filter has at least one Rule

Using sharing (second assumption) I had an idea to first process Document against every Rule and then (after finishing) for every Filter using already computed Rules compute result. This way if Rule is shared then I am computing it only once. However, it doesn't take advantage of early cutting (third assumption).

Second idea is to use early cutting as slightly optimized bruteforce, but it won't use Rules sharing then.

Rules sharing looks like subproblem sharing, so probably memoization and dynamic programming will be helpful.

I have noticed, that Filter-Rule relation is bipartite graph. Not quite sure if it can help me though. I also have noticed, that I could use reverse sets and in every Rule store corresponding Set. This would however create circular dependency and may cause desynchronization problems in database.

Default idea is that Documents are streamed, and every single of them is event that will create FaaS instance to process it. However, this would probably force every FaaS instance to query for all Filters, which leaves me at O(F * D) queries because of Shared-Nothing architecture.

Sample Filter:

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

or in more condense form:

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

for Document:

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

evaluates to true.

I can slightly change data model, stream something else instead of Document (ex. Filters) and use any nosql database and tools to help it. Apache Flink (event processing) and MongoDB (single query to retrieve Filter with it's Rules) or maybe Neo4j (as model looks like bipartite graph) looks like could help me, but not sure about it.

Can it be processed efficiently (with regard to - probably - database queries)? What tools would be appropriate?

I have been also wondering, if maybe I am trying to solve special case of some more general (math) problem that may have useful theorems and algorithms.

EDIT: My newest idea: Gather all Documents in cache like Redis. Then single event starts up and publishes N functions (as in Function as a Service), and every function selects F/N (amount of Filters divided by number of instances - so just evenly distributing Filters across instances) this way every Filter is fetched from database only once.

Now, every instance streams all Documents from cache (one document should be less than 1MB and at the same time I should have 1-10k of them so should fit in cache). This way every Document is selected from database only once (to cache).

I have reduced database read operations (still some Rules are selected multiple times), but still I am not taking advantage of Rule sharing across Filters. I could intentionally ignore it by using document database. This way by selecting Filter I will also get it's Rules. Still - I have to recalculate it's value.

I guess that's what I get for using Shared Nothing scalable architecture?

Answer 1

I realized that although my graph is indeed (in theory) bipartite but (in practice) it's going to be set of disjoint bipartite graphs (as not all Rules are going to be shared). This means, that I can process those disjoint parts independently on different FaaS instances without recalculating same Rules.

This reduces my problem to processing single bipartite connected graph. Now, I can use benefits of dynamic programming and share result of Rule computation only if memory i shared, so I cannot divide (and distribute) this problem further without sacrificing this benefit. So I thought this way: if I have already decided, that I will have to recompute some Rules, then let it be low compared to disjoint parts that I will get.

This is actually minimum cut problem, that has (fortunately) polynomial complexity known algorithm.

However, this may be not ideal in my case, because I don't want to cut any part of graph - I would like to cut graph ideally in half (divide and conquer strategy, that could be reapplied recursively till graph would be so small that could be processed in seconds in FaaS instance, that has time bound).

This means, that I am looking for cut, that would create two disjoint bipartite graphs, with possibly same amount of vertexes each (or at least similar).

This is sparsest cut problem, that is NP-hard, but has O(sqrt(logN)) approximated algorithm, that also favors less cut edges.

Currently, this does look like solution for my problem, however I would love to hear any suggestions, improvements and other answers.

Maybe it can be done better with other data model or algorithm? Maybe I can reduce it further with some theorem? Maybe I could transform it to other (simpler) problem, or at least that is easier to divide and distribute across nodes?

This idea and analysis strongly suggests using graph database.