TRACKING LARGE NUMBERS OF MOVING OBJECTS IN AN EVENT PROCESSING SYSTEM
First Claim
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;
partitioning, by the computer system, the input event stream among a plurality of processing nodes to facilitate parallel tracking of the plurality of objects, wherein each processing node of the plurality of processing nodes is configured to track an object in the plurality of objects in a predefined spatial region, and wherein the predefined spatial region for at least two processing nodes in the plurality of processing nodes overlap; and
for a processing node in the plurality of processing nodes, determining whether to insert or update an event in a relation operated on by the processing node, wherein determining whether to insert or update the event in the relation operated on by the processing node comprises;
retrieving, from a bit vector associated with the processing node, a bit value associated with the object;
when the bit value is a first value;
transmitting to the processing node a command for inserting the event into the relation; and
setting the bit value to a second value; and
when the bit value is the second value, transmitting a command to the processing node for updating the event in the relation.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
20 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; partitioning, by the computer system, the input event stream among a plurality of processing nodes to facilitate parallel tracking of the plurality of objects, wherein each processing node of the plurality of processing nodes is configured to track an object in the plurality of objects in a predefined spatial region, and wherein the predefined spatial region for at least two processing nodes in the plurality of processing nodes overlap; and for a processing node in the plurality of processing nodes, determining whether to insert or update an event in a relation operated on by the processing node, wherein determining whether to insert or update the event in the relation operated on by the processing node comprises; retrieving, from a bit vector associated with the processing node, a bit value associated with the object; when the bit value is a first value; transmitting to the processing node a command for inserting the event into the relation; and setting the bit value to a second value; and when the bit value is the second value, transmitting a command to the processing node for updating the event in the relation. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. 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; 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, wherein each processing node of the plurality of processing nodes is configured to track an object in the plurality of objects in a predefined spatial region, and wherein the predefined spatial region for at least two processing nodes in the plurality of processing nodes overlap; and for a processing node in the plurality of processing nodes, code that causes the processor to determine whether to insert or update an event in a relation operated on by the processing node, wherein the code that causes the processor to determine whether to insert or update the event in the relation operated on by the processing node comprises; code that causes the processor to retrieve, from a bit vector associated with the processing node, a bit value associated with the object; when the bit value is a first value; code that causes the processor to transmit to the processing node, a command for inserting the event into the relation; and code that causes the processor to set the bit value to a second value; and when the bit value is the second value, code that causes the processor to transmit a command to the processing node for updating the event in the relation. - View Dependent Claims (13, 14)
-
-
15. 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; partition the input event stream among the plurality of processing nodes to facilitate parallel tracking of the plurality of objects, wherein each processing node of the plurality of processing nodes is configured to track an object in the plurality of objects in a predefined spatial region, and wherein the predefined spatial region for at least two processing nodes in the plurality of processing nodes overlap; and for a processing node in the plurality of processing nodes, determine whether to delete an event from a relation operated on by the processing node, wherein determining whether to delete the event from the relation operated on by the processing node comprises; retrieving, from a bit vector associated with the processing node, a bit value associated with the object; when the bit value is a first value; transmitting to the processing node a command for deleting the event from the relation; and clearing the bit value to a second value different from the first value. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification