How would you find the most specific "filter" that matches a document? (determining which market segment a user fits in)

Question

Imagine you have actions setup for when a user is from a certain demographic/market segment. The filters work a bit like a graph, matching for country, region, platform, operating system, and browser.

By default, you will match any value (if you specify US, you match for all users from the US regardless of region, platform, OS, or browser)

If you specify multiple values for any property of the filter it works like an OR (can be any of the values you specified), for the filter to match all the properties must have at least one match or be empty (accept all), essentially an AND operation.

So we can have:

Segment #1:
Countries: United States, Canada

Segment #2:
Countries: United States
Regions: New York
Platform: Tablets

Segment #3
Countries: United States
Browser: Chrome

Segment #4
Countries: United States

Segment #5
  Match all (all filters left empty)

Scenario #1

User from Canada on his Tablet
Result: Segment #1

Scenario #2

User from New York, United States visits from Google Chrome on his Tablet.
Result: Segment #2, because the filter more specifically matches the user (matches country, region, and platform)

Scenario #3

User from Texas visits from his desktop
Result: Segment #4, tie with segment #1 is resolved because Segment #4 only matches United States and is therefore more specific

Work so far

I was thinking I could take each segment and load it up into a graph database that looks something like this

Country -> Region -> Platform --> OS -> Browser -> Segment

Each node either has a value (ex: United States, Chrome, Firefox, etc) and relationships that link it to any node below it in the tree (Country -> Browser is okay, Browser -> Country is not) or is null ("match all").

Each relationship (represented by ->) would also store a weight used to resolve ties. Relationships from a catch-all node get the max weight as they will always lose to a more specific filter.

Example database (numbers on the lines are the weight, lower weight becomes the prefered path)

Potential query

So now I need a query (maybe neo4j can do this?) that does the following:

• Find the top level country node with the same value as the user or null
• Go through each relationship (sorted by weight in ascending order)
• Find the longest path, ties go to the node connected by a relationship with the lowest weight (if the tie is between a relationship to a null/catch-all node, the null node loses)
• Continue this loop until we find a segment #

I'm sorry for the long post, it's hard to explain what I'm getting at via text.

What I'm looking for

• Am I on the right path to solving this problem?
• Are there better ways to go about this?
• What would be the best way to store these relationships (graph database?)
• How can I build a query that does what I want?

tl;dr: Need a way decent/performant way of finding the longest/most specific path in a graph like data structure. Comments requesting clarification or with any related information/documentation/projects/reading are very welcome

Answer 1

With Neo4j, you can store properties in a relationship, example:

(u1:User{name:"foo"})-[:FRIEND_WITH{since : "2015/01/01"}]->(u2:User{name:"bar"})

I think you should store country nodes this way:

(usa:Country{name: "USA", other attributes...})

So you can find every single country by matching with Country label, and then filter with the name property to get the one you're looking for.

Same for the cities, you can do a simple relationship to store every city :

(usa:Country{ name: "USA"})-[:CONTAINS_CITY]->(n:City{name: "New York", other attributes...})

and then you can add platform etc after the city.

To match a segment related to a certain country, you can do this way (example for Scenario #1) :

Match (c:Country{name : "Canada"})-[*1..2]->(p:Platform{name : "Tablet"})-[*1..]->(s:Segment) return s

Then you can create your segment by using nodes and create relations between them, the only problem may be on this case:

• User1 has a Tablet in Canada
• User2 has a Tablet in Canada using Chrome

In this case, because of the depth match on the relationship ([*1..]) the User1 can be on the same segment as User2. The solution is to create intermediate nodes with default values, in case you don't have browser informations for example.