Determining an execution ordering

Abstract

There is provided a computer-implemented method of determining an execution ordering. An exemplary method comprises generating a directed graph based on a hierarchy. The hierarchy includes a plurality of pattern queries. The method also includes determining a minimum spanning tree of the directed graph. The method further includes determining an execution order of the pattern queries based on the minimum spanning tree.

What is claimed is: 
     
         1 . A computer-implemented method comprising:
 accessing a plurality of pattern queries directed to streaming data received from a tracking system;   generating a directed graph based on the plurality of pattern queries;   determining a minimum spanning tree of the directed graph;   determining, based on the minimum spanning tree, an edge directed to a first pattern query; and   determining, based on the edge, whether the first pattern query is to be executed independently or is to be computed conditionally from another pattern query.   
     
     
         2 . The computer-implemented method of  claim 1 , further comprising:
 when a source of the edge is a virtual ground, determining that the first pattern query is to be executed independently.   
     
     
         3 . The computer-implemented method of  claim 2 , further comprising:
 executing the first pattern query independently using a stack-based join.   
     
     
         4 . The computer-implemented method of  claim 1 , further comprising:
 when a source of the edge is a second pattern query, determining that the first pattern query is to be computed conditionally from the second pattern query.   
     
     
         5 . The computer-implemented method of  claim 4 , wherein the first pattern query is a child of the second pattern query, and the first pattern query is to be computed conditionally using a general to specific evaluation. 
     
     
         6 . The computer-implemented method of  claim 4 , wherein the first pattern query is a parent of the second pattern query, and the first pattern query is to be computed conditionally using a specific to general evaluation. 
     
     
         7 . The computer-implemented method of  claim 4 , further comprising:
 computing the first pattern query conditionally from the second pattern query.   
     
     
         8 . A computing device comprising:
 a hardware processor; and   a machine-readable storage medium storing instructions, the instructions executable by the hardware processor to:
 access a plurality of pattern queries directed to streaming data received from a tracking system; 
 generate a directed graph based on the plurality of pattern queries; 
 determine a minimum spanning tree of the directed graph; 
 determine, based on the minimum spanning tree, an edge directed to a first pattern query; and 
 determine, based on the edge, whether the first pattern query is to be executed independently or is to be computed conditionally from another pattern query. 
   
     
     
         9 . The computing device of  claim 8 , the instructions further executable to:
 responsive to a determination that a source of the edge is a virtual ground, determine that the first pattern query is to be executed independently.   
     
     
         10 . The computing device of  claim 9 , the instructions further executable to:
 execute the first pattern query independently using a stack-based join.   
     
     
         11 . The computing device of  claim 8 , the instructions further executable to:
 responsive to a determination that a source of the edge is a second pattern query, determine that the first pattern query is to be computed conditionally from the second pattern query.   
     
     
         12 . The computing device of  claim 11 , wherein the first pattern query is a child of the second pattern query, and the first pattern query is to be computed conditionally using a general to specific evaluation. 
     
     
         13 . The computing device of  claim 11 , wherein the first pattern query is a parent of the second pattern query, and the first pattern query is to be computed conditionally using a specific to general evaluation. 
     
     
         14 . The computing device of  claim 11 , the instructions further executable to:
 compute the first pattern query conditionally from the second pattern query.   
     
     
         15 . An article comprising a machine-readable storage medium storing instructions that upon execution cause a processor to:
 access a plurality of pattern queries directed to streaming data received from a tracking system;   generate a directed graph based on the plurality of pattern queries;   determine a minimum spanning tree of the directed graph;   determine, based on the minimum spanning tree, an edge directed to a first pattern query; and   determine, based on the edge, whether the first pattern query is to be executed independently or is to be computed conditionally from another pattern query.   
     
     
         16 . The article of  claim 15 , wherein the instructions further cause the processor to:
 in response to a determination that a source of the edge is a virtual ground, determine that the first pattern query is to be executed independently.   
     
     
         17 . The article of  claim 16 , wherein the instructions further cause the processor to:
 execute the first pattern query independently using a stack-based join.   
     
     
         18 . The article of  claim 15 , wherein the instructions further cause the processor to:
 in response to a determination that a source of the edge is a second pattern query, determine that the first pattern query is to be computed conditionally from the second pattern query.   
     
     
         19 . The article of  claim 18 , wherein the first pattern query is a child of the second pattern query, and the first pattern query is to be computed conditionally using a general to specific evaluation. 
     
     
         20 . The article of  claim 18 , wherein the first pattern query is a parent of the second pattern query, and the first pattern query is to be computed conditionally using a specific to general evaluation.