Moving from Batch to Streaming architecture using a Graph datastructure

Question

The use case I am trying to solve is, assigning millions of users to their groups/segments. I have thousands of different criteria from which buckets of users are created. E.g. bucket criteria:

All married males in NY or LA assign to Bucket/Segment 1;

Currently at the end of day, I query users from a TB scale table in cloud, one bucket criteria at a time, based on thousands of different bucket criterias. Then generate a daily feed for each of these segments.

I use to query the database every night but the number of segments/buckets have become so huge that its no longer is feasible to batch query each bucket criteria every night and populate buckets.

Instead I am thinking of moving to streaming architecture where a user is assigned to the segment as they come in. For that I am looking to load segment definitions into a directional (multi edge) graph data structure and determine which user qualifies for which segment as the user come in. Sample Graph below:

In case you are wondering why do I need multiple edges between two vertices, it is to represent and condition per bucket criteria. For e.g. if Segment 1 is

All married males in NY or LA assign to Bucket/Segment 1;

And Segment 2 is:

All married males assign to Bucket/Segment 2;

if Segment 1 and 2 share the same edge then that will be a problem because Segment 1 results are just a subset of Segment 2 results. Segment 2 has no city filter.

This graph theoretically represents all the relations for my use perfectly, but the problem is after implementing this graph the performance of graph creation algorithm has been disappointing. Most the time is spent creating edges for vertices in a bucket criteria for all possible paths to that edge.

Some filter values like Zip Codes can have tens of thousands of values which results in a proliferation of edges between nodes. I am looking for a way to optimize this graph creation.

Edit: Providing more details as per answer below;

1. Technology I am using: Google Cloud Dataflow (Managed Apache Beam). More details on how I am implementing this are in the comment here
2. Clean rules set to use sets instead of actual values: I am using sets for alot of rules like zipcodes and have it implemented already as zip in { "98500","98800",.... }. But for some rules for e.g. user email you can't really have a set and to represent each user email in the graph as a vertex.
3. Implement truth propagation graph: Will look more into this currently, I am using HashMap for my vertex and edges. My vertex is v={vertex_id, HashMap} and my edge = {edge_id,edge_to_vertex}. And my graph is implemented as HashMap

Answer 1

The problem in short:

• you have millions of Users and thousands of Rules to determine the Segments to which they belong (can be several);
• each Rule is a combination of conditions on User properties;
• you'd like to streamline the Segment identification in order to avoid applying each rule on every user.
• you experience performance problems

Potential causes

Unfortunately, we are somehow in the dark bout the technologies, and hence about what may cause the performance issue that your describe.

One of the performance issues is certainly related to the long lists of hundreds of zip codes, which will look as a long inefficient unsorted linked-list in any graph. So start cleaning your rule set by rewriting them using a set logic (e.g. if zip in { "98500","98800",.... } instead of if zip=="98500" or zip=="98800" or ... ). A similar issue is to make ranges more easily identifiable in the rules (e.g. if age in [21;49] instead of if age>=21 and age<=49)

Way forward

After this rule optimization, you can process your rules and build a truth propagation graph:

• the properties of a user are starting nodes (e.g. city, married, gender, ...)
• browse through all your rules. Create an edge to an intermediary node for each single condition, that is value (==), range, and set
• for each values that have to be combined with and create again an edge to another intermediary node, and same for the or relations, the last edge then goes to the segment.

With your example, this would result in a graph:

city   ----> { NYC, LA }  -----+
                               &------> segment1
married ---> Y   --------------+
        ---> N   ...           |
                               &------> segment2
                               |
gender  ---> M   --------------+
        ---> F   ...

When running this segment tagger, the expensive operations are at the start nodes. Using set operations (which in Java or C++ are implemented with hash-tables or b-trees) will make a significant difference compared to the sequential or-chains. You'll then have to propagate the truth through the graph, until it's no longer possible to activate a new node.

Future improvements

You could consider making graph optimizations. This is what the compiler do to identify common part in several expressions to compute them only once. However, this is really a hard topic.