Tracking large numbers of moving objects in an event processing system

• US 9,189,280 B2
• Filed: 05/13/2011
• Issued: 11/17/2015
• Est. Priority Date: 11/18/2010
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Park, Hoyong, Hsiao, Eric, Piper, Andrew
• Primary Examiner(s): Sough, H S
• Assistant Examiner(s): Onat, Umut
• Application Number:
  US13/107,742
• Publication Number:
  US 20120291049A1
• Time in Patent Office: 1,649 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications

Abstract

Techniques for tracking large numbers of moving objects in an event processing system are provided. An input event stream can be received, where the events in the input event stream represent the movement of a plurality of geometries or objects. The input event stream can then be partitioned among a number of processing nodes of the event processing system, thereby enabling parallel processing of one or more continuous queries for tracking the objects. The partitioning can be performed such that each processing node is configured to track objects in a predefined spatial region, and the spatial regions for at least two nodes overlap. This overlapping window enables a single node to find, e.g., all of the objects within a particular distance of a target object, even if the target object is in the process of moving from the region of that node to the overlapping region of another node.

Claims

1. A method comprising:

receiving, by a computer system, an input event stream comprising a sequence of events, the sequence of events representing movement of a plurality of objects, wherein the input event stream includes a first event of the sequence of events, the first event being associated with a first object of the plurality of objects; and

partitioning, by the computer system, the input event stream among a plurality of processing nodes to facilitate parallel tracking of the plurality of objects using a plurality of bit vectors that correspond to the plurality of processing nodes, wherein each of the plurality of bit vectors comprises a plurality of bit values corresponding to the plurality of objects, wherein each processing node of the plurality of processing nodes is configured to track those of the plurality of objects having spatial positions in a predefined spatial region, and wherein the predefined spatial regions for at least two processing nodes in the plurality of processing nodes overlap, wherein the partitioning for the first event includes;

determining, by the computer system, a spatial position of the first object based upon the first event;

determining, by the computer system, that the spatial position of the first object is in the predefined spatial region tracked by a first processing node of the plurality of processing nodes;

determining, by the computer system using a first bit value of a first bit vector of the plurality of bit vectors that is associated with the first processing node, that the first processing node is not currently tracking the first object, wherein the first bit value is associated with the first object;

changing, by the computer system, the first bit value from a first value to a second value that is different than the first value; and

transmitting, by the computer system, a command to the first processing node for inserting the first event into a first spatial-region-representing relation that is operated upon by the first processing node.

2. The method of claim 1 wherein:

the plurality of processing nodes operate upon a plurality of spatial-region-representing relations, the plurality of spatial-region-representing relations including the first spatial-region-representing relation;

each event of the sequence of events includes an identifier of the associated object and a current spatial position of the object; and

the partitioning the input event stream comprises, for each received event;

determining a subset of processing nodes in the plurality of processing nodes configured to track objects in the predefined spatial region that encompasses the current position of the object; and

for each processing node in the plurality of processing nodes;

determining whether the processing node is in the subset;

when the processing node is in the subset, determining whether to cause the event to be inserted or updated in the spatial-region-representing relation operated on by the processing node; and

when the processing node is not in the subset, determining whether to cause the event to be deleted from the spatial-region-representing relation operated on by the processing node.

3. The method of claim 2 wherein determining whether to insert or update the event in the relation operated on by the processing node comprises:

retrieving, from the bit vector associated with the processing node, the bit value associated with the object;

when the bit value is the first value;

transmitting to the processing node a command for inserting the event into the spatial-region-representing relation; and

setting the bit value to the second value; and

when the bit value is the second value, transmitting a command to the processing node for updating the event in the spatial-region-representing relation.

4. The method of claim 2 wherein determining whether to delete the event from the relation operated on by the processing node comprises:

retrieving, from the bit vector stored for the processing node, the bit value associated with the object; and

when the bit value is the second value;

transmitting to the processing node a command for deleting the event from the relation; and

setting the bit value to the first value.

5. The method of claim 2 wherein:

the predefined spatial regions for the plurality of processing nodes are indexed using an R-tree index; and

the determining the subset of processing nodes comprises performing, based on the current position of the object, a search into the R-tree index.

6. The method of claim 1 wherein the computer system is a load balancing node of an event processing system.

7. The method of claim 1 wherein the sequence of events represent the movement of more than one million distinct objects.

8. The method of claim 1 wherein the plurality of objects are motor vehicles.

9. The method of claim 1 wherein the predefined spatial regions for the plurality of processing nodes are one-dimensional, two-dimensional, or three-dimensional regions.

10. The method of claim 1, wherein the input event stream further includes a second event of the sequence of events that is associated with a second object of the plurality of objects, and wherein the partitioning for the second event includes:

determining, by the computer system, a second spatial position of the second object based upon the second event;

determining, by the computer system, that the second spatial position of the second object is in a second predefined spatial region tracked by a second processing node of the plurality of processing nodes and a third predefined spatial region tracked by a third processing node of the plurality of processing nodes;

determining, by the computer system using a second bit value of a second bit vector of the plurality of bit vectors that is associated with the second processing node, that the second processing node is currently tracking the second object, wherein the second bit value is associated with the second object;

transmitting, by the computer system, a second command to the second processing node for updating the second event in a second spatial-region-representing relation that is operated upon by the second processing node;

determining, by the computer system using a third bit value of a third bit vector of the plurality of bit vectors that is associated with the third processing node, that the third processing node is not currently tracking the second object, wherein the third bit value is associated with the second object;

changing, by the computer system, the third bit value from the first value to the second value; and

transmitting, by the computer system, a third command to the third processing node for inserting the second event into a third spatial-region-representing relation that is operated upon by the third processing node.

11. The method of claim 1, wherein the partitioning for the first event further includes:

prior to the changing the first bit value, identifying, by the computer system, from the first bit vector corresponding to the first processing node, the first bit value;

determining, by the computer system, a type of the command to be sent to the first processing node based on the first bit value.

12. The method of claim 1, wherein the input event stream further includes a second event of the sequence of events that is also associated with the first object, wherein the partitioning further includes:

determining, by the computer system, a second spatial position of the first object based upon the second event;

determining, by the computer system, that the second spatial position of the second object is not in the first predefined spatial region tracked by the first processing node;

determining, by the computer system using a second bit value of a first bit vector, that the first processing node is currently tracking the first object;

changing, by the computer system, the first bit value from the second value to the first value; and

transmitting, by the computer system, another command to the first processing node for deleting one or more events associated with the first object from the first spatial-region-representing relation operated upon by the first processing node.

13. A non-transitory computer readable medium having stored thereon program code executable by a processor, the program code comprising:

code that causes the processor to receive an input event stream comprising a sequence of events, the sequence of events representing movement of a plurality of objects, wherein the input event stream includes a first event of the sequence of events, the first event being associated with a first object of the plurality of objects; and

code that causes the processor to partition the input event stream among a plurality of processing nodes to facilitate parallel tracking of the plurality of objects using a plurality of bit vectors that correspond to the plurality of processing nodes, wherein each of the plurality of bit vectors comprises a plurality of bit values corresponding to the plurality of objects, wherein each processing node of the plurality of processing nodes is configured to track those of the plurality of objects having spatial positions in a predefined spatial region, and wherein the predefined spatial regions for at least two processing nodes in the plurality of processing nodes overlap, wherein the partitioning for the first event includes;

determining a spatial position of the first object based upon the first event;

determining that the spatial position of the first object is in the predefined spatial region tracked by a first processing node of the plurality of processing nodes;

determining, using a first bit value of a first bit vector of the plurality of bit vectors that is associated with the first processing node, that the first processing node is not currently tracking the first object, wherein the first bit value is associated with the first object;

changing the first bit value from a first value to a second value that is different than the first value; and

transmitting a command to the first processing node for inserting the first event into a first spatial-region-representing relation that is operated upon by the first processing node.

14. The non-transitory computer readable medium of claim 13, wherein:

the plurality of processing nodes operate upon a plurality of spatial-region-representing relations, the plurality of spatial-region-representing relations including the first spatial-region-representing relation;

each event of the sequence of events includes an identifier of the associated object and a current spatial position of the object; and

the partitioning the input event stream comprises, for each received event;

determining a subset of processing nodes in the plurality of processing nodes configured to track objects in the predefined spatial region that encompasses the current position of the object; and

for each processing node in the plurality of processing nodes;

determining whether the processing node is in the subset;

when the processing node is in the subset, determining whether to cause the event to be inserted or updated in the spatial-region-representing relation operated on by the processing node; and

when the processing node is not in the subset, determining whether to cause the event to be deleted from the spatial-region-representing relation operated on by the processing node.

15. The non-transitory computer readable medium of claim 13, wherein the partitioning for the first event further includes:

prior to the changing the first bit value, identifying, from the first bit vector corresponding to the first processing node, the first bit value;

determining a type of the command to be sent to the first processing node based on the first bit value.

16. The non-transitory computer readable medium of claim 13, wherein the input event stream further includes a second event of the sequence of events that is also associated with the first object, wherein the partitioning further includes:

determining a second spatial position of the first object based upon the second event;

determining that the second spatial position of the second object is not in the first predefined spatial region tracked by the first processing node;

determining, using a second bit value of a first bit vector, that the first processing node is currently tracking the first object;

changing the first bit value from the second value to the first value; and

transmitting another command to the first processing node for deleting one or more events associated with the first object from the first spatial-region-representing relation operated upon by the first processing node.

17. An event processing system, comprising:

a load balancer node; and

a plurality of processing nodes,

wherein the load balancer node is configured to;

receive an input event stream comprising a sequence of events, the sequence of events representing movement of a plurality of objects, wherein the input event stream includes a first event of the sequence of events, the first event being associated with a first object of the plurality of objects; and

partition the input event stream among the plurality of processing nodes to facilitate parallel tracking of the plurality of objects using a plurality of bit vectors that correspond to the plurality of processing nodes, wherein each of the plurality of bit vectors comprises a plurality of bit values corresponding to the plurality of objects, wherein each processing node of the plurality of processing nodes is configured to track those of the plurality of objects having spatial positions in a predefined spatial region, and wherein the predefined spatial regions for at least two processing nodes in the plurality of processing nodes overlap, wherein the partitioning for the first event includes;

determining a spatial position of the first object based upon the first event;

determining that the spatial position of the first object is in the predefined spatial region tracked by a first processing node of the plurality of processing nodes;

determining, using a first bit value of a first bit vector of the plurality of bit vectors that is associated with the first processing node, that the first processing node is not currently tracking the first object, wherein the first bit value is associated with the first object;

changing the first bit value from a first value to a second value that is different than the first value; and

transmitting a command to the first processing node for inserting the first event into a first spatial-region-representing relation that is operated upon by the first processing node.

18. The event processing system of claim 17, wherein:

the plurality of processing nodes operate upon a plurality of spatial-region-representing relations, the plurality of spatial-region-representing relations including the first spatial-region-representing relation;

each event of the sequence of events includes an identifier of the associated object and a current spatial position of the object; and

the partitioning the input event stream comprises, for each received event;

determining a subset of processing nodes in the plurality of processing nodes configured to track objects in the predefined spatial region that encompasses the current position of the object; and

for each processing node in the plurality of processing nodes;

determining whether the processing node is in the subset;

when the processing node is in the subset, determining whether to cause the event to be inserted or updated in the spatial-region-representing relation operated on by the processing node; and

when the processing node is not in the subset, determining whether to cause the event to be deleted from the spatial-region-representing relation operated on by the processing node.

19. The event processing system of claim 17, wherein the partitioning for the first event further includes:

prior to the changing the first bit value, identifying, from the first bit vector corresponding to the first processing node, the first bit value;

determining a type of the command to be sent to the first processing node based on the first bit value.

20. The event processing system of claim 17, wherein the input event stream further includes a second event of the sequence of events that is also associated with the first object, wherein the partitioning further includes:

determining a second spatial position of the first object based upon the second event;

determining that the second spatial position of the second object is not in the first predefined spatial region tracked by the first processing node;

determining, using a second bit value of a first bit vector, that the first processing node is currently tracking the first object;

changing the first bit value from the second value to the first value; and

transmitting another command to the first processing node for deleting one or more events associated with the first object from the first spatial-region-representing relation operated upon by the first processing node.