Multiple event matching algorithm
I have a task to compare several events (facts) with each other with some of their properties. As a result, events corresponding to some action should be generated. An action can be created by matching events of all existing types.
Is there any algorithm that could be used for such a task? Or in any direction?
thank
Example: We have several events with different types and properties. The SEEN type is a cumulative event (multiple events can be combined to match), but the FOUND type is not.
Event 1 (SEEN):
DATE="2009-09-30"
EYES_COLOR="BLUE"
LEFT_SOCK_COLOR="RED"
Event 2 (SEEN):
DATE="2009-09-30"
EYES_COLOR="BLUE"
RIGHT_SOCK_COLOR="GREEN"
Event 3 (FOUND):
DATE="2009-09-30"
EYES_COLOR="BLUE"
LEFT_SOCK_COLOR="BLUE"
RIGHT_SOCK_COLOR="GREEN"
PLACE="MARKET"
Event 4 (FOUND):
DATE="2009-09-30"
EYES_COLOR="BLUE"
LEFT_SOCK_COLOR="GREEN"
PLACE="SHOP"
Event 5 (FOUND):
DATE="2009-09-30"
EYES_COLOR="BLUE"
PLACE="AIRPORT"
For the above events, such actions should be generated (by composing consistent events):
Action 1_2_3:
DATE="2009-09-30"
EYES_COLOR="BLUE"
LEFT_SOCK_COLOR="RED"
RIGHT_SOCK_COLOR="GREEN"
PLACE="MARKET"
Action 2_4:
DATE="2009-09-30"
EYES_COLOR="BLUE"
LEFT_SOCK_COLOR="GREEN"
PLACE="SHOP"
Facilities:
Event 1 + Event 2 + Event 3 => Action 1_2_3
Event 2 + Event 4 => Action 2_4
Event 5 does not match with anything.
source to share
in your case, every two events are either compatible or not; we can denote this by C (e, e '), which means that event e is compatible with event e'. You can build the maximum set of compatible events, of course, iteratively; when you have a set of {e1, e2, ..., en} compatible events, you can add e 'to the set if and only if e' is compatible with every e1, ..., en, i.e. C (ei, e ') is true for all 1 <= i <= n.
Unfortunately, in your case, the number of maximum sets of compatible events can be exponential in relation to the number of events, because you can have, for example, events e1, e2, e3 and e4 so that they are all mask compatible, but none of them not compatible with two other events; for this set, you already get 6 different "actions" and they overlap.
A simple algorithm is to have a recursive search in which you add events one by one to the prospective "action", and when you cannot add any events, you log the action; then you come back. It was called "search backward". You can improve your running time and then use the correct data structures to "quickly" find the relevant events.
As in the comment, the SEEN / FOUND question is open; I am assuming the fields are being merged "as is".
source to share
This pseudocode might help: (C # syntax)
foreach (var found in events.Where(x => x.EventType == "Found"))
{
var matches = events.Where(x => x.EventType == "Seen"
&& x.Whatever == found.Whatever);
if (matches.Count() > 0)
{
// Create an action based on the single "Found" event
// and the multiple matching "Seen" events.
}
}
source to share
I'm not sure I understood the question correctly. It seems that for each FOUND event, you want to define all the corresponding SEEN events and combine them? Python code:
# assume events are dictionaries, and you have 2 lists of them by type:
# (omitting DATE because it always "2009-09-03" in your example)
seen_events = [
{
"EYES_COLOR": "BLUE",
"LEFT_SOCK_COLOR": "RED",
},
{
"EYES_COLOR": "BLUE",
"RIGHT_SOCK_COLOR": "GREEN",
},
]
found_events = [
{
"EYES_COLOR": "BLUE",
"LEFT_SOCK_COLOR": "BLUE",
"RIGHT_SOCK_COLOR": "GREEN",
"PLACE": "MARKET",
},
{
"EYES_COLOR": "BLUE",
"LEFT_SOCK_COLOR": "GREEN",
"PLACE": "SHOP",
},
{
"EYES_COLOR": "BLUE",
"PLACE": "AIRPORT",
},
]
def do_action(seen_events, found):
"""DUMMY"""
for seen in seen_events:
print seen
print found
print
# brute force
for found in found_events:
matching = []
for seen in seen_events:
for k in found:
if k in seen and seen[k] != found[k]:
break
else: # for ended without break (Python syntax)
matching.append(seen)
if matching:
do_action(matching, found)
which prints:
{'EYES_COLOR': 'BLUE', 'RIGHT_SOCK_COLOR': 'GREEN'}
{'EYES_COLOR': 'BLUE', 'PLACE': 'MARKET', 'LEFT_SOCK_COLOR': 'BLUE', 'RIGHT_SOCK_COLOR': 'GREEN'}
{'EYES_COLOR': 'BLUE', 'RIGHT_SOCK_COLOR': 'GREEN'}
{'EYES_COLOR': 'BLUE', 'PLACE': 'SHOP', 'LEFT_SOCK_COLOR': 'GREEN'}
{'EYES_COLOR': 'BLUE', 'LEFT_SOCK_COLOR': 'RED'}
{'EYES_COLOR': 'BLUE', 'RIGHT_SOCK_COLOR': 'GREEN'}
{'EYES_COLOR': 'BLUE', 'PLACE': 'AIRPORT'}
Right, this is not efficient - O (n * m) - but does that even describe the problem correctly?
source to share