Tracking large numbers of moving objects in an event processing system
First Claim
1. A method comprising:
- receiving, by a computer system, an event stream comprising a sequence of events representing movement of a plurality of objects, the event stream including a first event of the sequence of events, and the first event being associated with a first object of the plurality of objects; and
partitioning, by the computer system, the 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, each of the plurality of bit vectors comprising a plurality of bit values corresponding to the plurality of objects, and the partitioning of the event stream comprising, for each event in the sequence of events;
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 a first processing node of the plurality of processing nodes, that the first processing node is currently tracking the first object of the plurality of objects, the first bit value being associated with the first object;
changing, by the computer system, the first bit value from a second value to a first value that is different than the second value; and
transmitting, by the computer system, a command to the first processing node for deleting the first event from a first spatial-region-representing relation that is operated upon by the first processing node.
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 event stream comprising a sequence of events representing movement of a plurality of objects, the event stream including a first event of the sequence of events, and the first event being associated with a first object of the plurality of objects; and partitioning, by the computer system, the 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, each of the plurality of bit vectors comprising a plurality of bit values corresponding to the plurality of objects, and the partitioning of the event stream comprising, for each event in the sequence of events; 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 a first processing node of the plurality of processing nodes, that the first processing node is currently tracking the first object of the plurality of objects, the first bit value being associated with the first object; changing, by the computer system, the first bit value from a second value to a first value that is different than the second value; and transmitting, by the computer system, a command to the first processing node for deleting the first event from a first spatial-region-representing relation that is operated upon by the first processing node. - 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 event stream comprising a sequence of events, the sequence of events representing movement of a plurality of objects, the event stream including a first event of the sequence of events, and the first event being associated with a first object of the plurality of objects; and code that causes the processor to partition the 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, each of the plurality of bit vectors comprising a plurality of bit values corresponding to the plurality of objects, and the partitioning of the event stream comprising, for each event in the sequent of events; determining, using a first bit value of a first bit vector of the plurality of bit vectors that is associated with a first processing node of the plurality of processing nodes, that the first processing node is currently tracking the first object of the plurality of objects, the first bit value being associated with the first object; changing the first bit value from a second value to a first value that is different than the second value; and transmitting a command to the first processing node for deleting the first event from a first spatial-region-representing relation that is operated upon by the first processing node. - View Dependent Claims (13, 14, 15)
-
-
16. 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 event stream comprising a sequence of events, the sequence of events representing movement of a plurality of objects, the event stream including a first event of the sequence of events, and the first event being associated with a first object of the plurality of objects; partition the 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, each of the plurality of bit vectors comprising a plurality of bit values corresponding to the plurality of objects, and the partitioning of the event stream comprising, for each event in the sequence of events; determining, using a first bit value of a first bit vector of the plurality of bit vectors that is associated with a first processing node of the plurality of processing nodes, that the first processing node is currently tracking the first object of the plurality of objects, the first bit value being associated with the first object; changing the first bit value from a second value to a first value that is different than the second value; and transmitting a command to the first processing node for deleting the first event from a first spatial-region-representing relation that is operated upon by the first processing node. - View Dependent Claims (17, 18, 19, 20)
-
Specification