Determining an execution ordering

Patent metadata

Field	Value
Publication number	US-2016203185-A1
Application number	US-201615074004-A
Country	US
Kind code	A1
Filing date	Mar 18, 2016
Priority date	Oct 31, 2011
Publication date	Jul 14, 2016
Grant date	—

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.

First claim

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.

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Gupta Chetan Kumar
• Wang Song
• Mehta Abhay
• Liu Mo
• Rundensteiner Elke A

Classifications

• G06F17/30498

  Physics · mapped topic

• G06F17/30516

  Physics · mapped topic

• G06F17/30463 Primary

  Physics · mapped topic

• G06F16/24542 Primary

  Plan optimisation · CPC title

• G06F16/2456

  Join operations · CPC title