Method for reverse real-time matching based on event-driven graph patterns

A method for reverse real-time matching based on event-driven graph patterns, wherein the method comprises the following steps:

• (1) definition of a graph pattern:
• the graph pattern is used to describe a spatial connection relationship among vertices and edges in a graph in a reverse order and attribute constraints thereof, and specifically, comprising a linked list of matching steps and matching contexts;
• the matching contexts is used for storing intermediate results of a matching process, and supporting matching conditions of non-adjacent vertices or edges;
• the linked list of matching steps comprises matching steps connected in series in a form of a linked list, and each matching step comprises the following content:
• a. Vertex Predicate (vp for short):
• according to various attributes of a vertex, combined with the matching contexts, determining whether the current vertex meets the matching conditions;
• b. Edge Predicate (ep for short):
• according to the various attributes of an edge, combined with the matching contexts, determining whether the current edge meets the matching conditions;
• (2) establishment of reverse matching architecture:
• the reverse matching architecture supports graph pattern matching and graph pattern management, comprising the following components:
• a. a session manager:
• responsible for creating and managing a matching session, restricting the behavior of the matching session according to session configuration information, and managing the life cycle of the matching session;
• the session manager is further responsible for adding and deleting all graph patterns, and limiting the number of concurrent matching sessions;
• b. a matching session:
• when receiving a matching request, the session manager creates a matching session to perform an actual graph matching operation;
• the matching session comprises a working graph loader, a working graph, a graph pattern matcher and a subgraph matching pool, and after the matching ends, the session manager returns to a result set and ends the life cycle of the matching session;
• the working graph loader:
• according to the matching requirements and progress, loading corresponding vertices and edges from an underlying graph data storage (Graph Storage) to form a working graph for reverse matching, the working graph loader also needs to abide by various conditional constraints issued by the session manager to the matching session, so as to prevent the matching process from occupying too many resources or time;
• the working graph:
• loading the related underlying graph data into the current matching session, so that the graph pattern matcher can quickly access and traverse the underlying graph data;
• the subgraph matching pool:
• used for storing subgraph instances generated according to different graph patterns and matching progresses;
• the subgraph instance comprises the following content:
• MatchingSteps:
• pointing to the linked list of steps of the graph pattern corresponding to the current subgraph instance;
• NextStep:
• pointing to the next matching step required for matching the current subgraph instance;
• NextVertex:
• pointing to the next vertex that needs to be loaded and matched, and the working graph loader loads into the working graph during the next matching step;
• MatchingContext:
• pointing to the matching context generated in a subgraph matching process, implemented in a data structure of a dictionary, and storing intermediate results of the matching process and information that needs to be temporarily stored in a form of key value pairs;
• MatchingResult:
• the matching result records the various vertices and edges that meet the matching step in a form of a list;
• the graph pattern matcher:
• controlling the complete process of reverse matching;
• c. session configuration:
• storing relevant configuration parameters of the matching session, comprising:
• the maximum number of vertices of the working graph, the maximum number of edges of the working graph, the maximum traversal depth and the maximum matching duration;
• d. registered graph patterns:
• containing all graph patterns that need to be matched in real time, as well as the mapping relationships between events and the graph patterns;
• (3) reverse matching method:
• (3.1) after receiving an event, the session manager initializes the entire matching process, comprising:
• (3.1.1) the session manager looks for a set of corresponding starting vertices from the received event according to requirements, and looks for a graph pattern corresponding to the current event from the registered graph patterns;
• if the corresponding starting vertices cannot be found, or if the corresponding graph pattern cannot be found, the session manager directly returns an empty result set;
• (3.1.2) the session manager creates a corresponding matching session according to the session configuration, initializes the graph pattern matcher, the subgraph matching pool and the working graph loader;
• at the same time, the session manager constructs a corresponding subgraph instance according to the starting vertices and the graph pattern, and places the subgraph instance in the subgraph matching pool;
• (3.2) the graph pattern matcher traverses the subgraph instances in the subgraph matching pool, and performs the following loop operations:
• (3.2.1) taking out the current subgraph instance and deleting it from the subgraph matching pool;
• (3.2.2) looking for the vertex corresponding to NextVertex of the current subgraph instance from the working graph, and verifying whether NextVertex meets the attribute constraints of the vertex predicate in NextStep;
• if the NextVertex does not meet the constraints, destroying the current subgraph instance and returning to step (3.2.1) to take the next subgraph instance;
• if the NextVertex meets the constraints, adding the vertex into a matching result list MatchingResult of the current subgraph instance and continuing the next operation;
• (3.3.3) if the edge predicate in NextStep is empty, ending the matching, adding the current matching subgraph instance into the result set, and returning to step (3.2.1);
• if the edge predicate in NextStep is not empty, continuing to load all edges pointing to NextVertex and determining whether the loaded edges meet the attribute constraints of the edge predicate one by one, if an edge e that meets the attribute constraints of the edge predicate is found, the graph pattern matcher will copy the current subgraph instance and perform the following operations:
• a. adding the edge e into the MatchingResult of the copied subgraph instance;
• b. setting NextVertex of the new instance as a starting vertex of the edge e;
• c. setting NextStep of the new instance as a subsequent matching step of the current matching step;
• d. finally, the graph pattern matcher adds the new subgraph instance into the subgraph matching pool;
• after traversing of all edges, the graph pattern matcher destroys the current subgraph instance;
• (3.3) repeating step (3.2), until one of the following conditions is met:
• a. the subgraph matching pool is empty, and there is no subgraph instance for matching;
• b. the scale of the working graph exceeds a limit in the session configuration, comprising:
• the number of vertices or edges in the working graph exceeds the limit, or the depth of the working graph exceeds the limit;
• c. the time of the entire reverse matching exceeds a pre-configured time limit;
• and
• (3.4) the graph pattern matcher returns to the result set, clears the subgraph matching pool and the working graph, and ends the current matching session.