Create unique buckets for stream of entities based on constraints on the entity attributes

Question

I have stream (magnitude 10s of millions) of entities, say Item which is modeled as below:

class Item {
 String id;
 Double price;
 Double profitPercentage;
 Country originCountry;
 Country destinationCountry;
 ...
}

All the attributes of this entity are well defined, and are restricted to Price related information + metadata.

I'd like to give a user the ability to create Buckets, which are nothing but a set of constraints on the attribute (e.g. price > 1000, originCountry == Country.USA, profitPercentage between 5 and 20), but with the condition that an Entity cannot fall into two buckets (The same should detected when an attempt is made to create such a conflicting Bucket).

The operations on each type of Entity are also well defined e.g. Double can only be used in comparisons (>,<,=,range),Country (which logically represents a member of a well-defined set of values) in some set etc)

This is mainly because each bucket is associated with an automated action, such as payment,rejection or refund, and resolution of overlapping actions is non-trivial.

The obvious solution to this problem is to allow the user to define priorities on the Buckets created (implies that multiple Buckets can match a given Entity), but this is something I would like to avoid, since it requires that there can never be two buckets having same priority, and such an occurrence would fail at runtime.

I am looking for solutions which could be used to detect the conflicts during creation time, but I have no clue where to begin. Others have suggested some sort of SMT Solver (Z3 was recommended), but I am not aware if this is at all feasible.

Answer 1

If you are lucky enough to have to deal with conjunctions only (logical and's) and no disjunctions (or's), checking whether a newly introduced bucket conflicts/formally intersects with those already defined, may not be as hard as it seems.

For instance, you could always normalize the definitions of their list of constraints after, say, the lexicographic order of the corresp. attribute names, and then it should not be too difficult to figure out why, e.g.,

(originCountry == Country.USA, price > 1000, profitPercentage between 5 and 20, ...)

indeed conflicts with

((unconstrained originCountry), price > 1500, profitPercentage between 0 and 10, ...)

but not with

((unconstrained originCountry), price > 1000, profitPercentage > 20, ...)

Basically, for any two of such tuples, a vs b:

given,

(constraint-a-1, ... , constraint-a-N)

and

(constraint-b-1, ... , constraint-b-N)

(where N is the number of attributes, price, profitPercentage, etc)

the intersection will be empty if there is any i in 1..N, where constraint-a-i does not intersect with constraint-b-i.

Presumably, some (unconstrained attribute) always intersects with itself or with any (constraint on same attribute).

But, likely, I missed something.

'Hope this helps.

Answer 2

I think there're a couple of options to consider:

1. create disjunct buckets, as you suggest. This creates the problem of checking, if the buckets really are disjunct.
2. run with buckets, as you suggest, but run all tests on all items and mark those for special handling, for which multiple rules fire (e.g. use manual inspection).
3. The Linux packet filter has a prioritised table of conditions which are executed one after the other. Some actions might terminate processing, after some other actions processing continues (think logging). There's the ability to call-out to other tables. See man iptables
4. Use a decision tree to create one single deterministic set of rules.

If you'd chose (1), you'd probably want to do (2) anyway, to check your checking algorithm.

From the user's point of view (1) and (2) might be perceived as complex after some time, because why (the heck) do I get a checking error, if I am certain two buckets are not the same? (you'll want to avoid cryptic error messages, and probably give some examples).

(3) is reasonable but I can tell you it will take some time to get used to it. Debugging that might not be so nice, unless you make sure your implementation supports it. I'd think this one allows managing the largest set of rules. This is definitely the most practical solution which has stood the test of time and has gone through multiple iterations, before arriving at what it is now.

(4) forces a certain logic into the decision and will probably need 2-3 attempts to get it right (like starting from scratch with a different condition at the root of the tree). Reasoning about it from the users point of view might be easiest. Might not be the best solution, if the rules are very fine grained and the tree gets large.

Depending on the size of the rule set, I would either choose (3) or (4).

All of these options might need careful thinking and a good strategy how to deploy, if you're using multiple parallel instances on your input stream.