Selective processing of location-sensitive data streams

Abstract

A method for processing a first data stream specifying locations of a user at different times and a second data stream specifying values of a monitored attribute at a location of interest at different times includes: receiving a location-centric trigger specifying at least one spatial predicate condition relative to the location of interest and at least one non-spatial predicate condition relevant to the location of interest, calculating a safe region that includes locations whose probability of satisfying the spatial predicate condition falls below a first threshold, calculating a safe value container that includes values whose probability of satisfying the non-spatial predicate condition falls below a second threshold, and processing the first data stream and the second data stream against the location-centric trigger, by considering only those locations that are not contained within the safe region and only those values that are not contained within the safe value container.

1 . A method for processing updates in the form of a plurality of incoming data streams, the plurality of incoming data streams comprising a first data stream that specifies one or more locations of a mobile user at one or more times and a second data stream that specifies one or more values of a monitored attribute at a location of interest at one or more times, the method comprising:
 receiving a location-centric trigger, the location-centric trigger specifying at least one spatial predicate condition relevant to the location of interest and at least one non-spatial predicate condition relevant to the location of interest;   calculating a safe region for the first data stream, the safe region comprising at least one of the one or more locations whose probability of satisfying the spatial predicate condition falls below a first predefined threshold;   calculating a safe value container for the second data stream, the safe value container comprising at least one of the one or more values whose probability of satisfying the non-spatial predicate condition falls below a second predefined threshold; and   processing the first data stream and the second data stream against the location-centric trigger, wherein the processing considers only those of the updates identifying those of the one or more locations that are not contained within the safe region and only monitored data values identifying those of the one or more values that are not contained within the safe value container,   wherein at least one of: the receiving, the calculating a safe region, the calculating a safe value container, or the processing is performed using a processor.   
     
     
         2 . The method of  claim 1 , further comprising:
 activating the location-centric trigger when the processing identifies at least one of the one or more locations that satisfies the spatial predicate condition and at least one of the one or more values that satisfies the non-spatial predicate condition.   
     
     
         3 . The method of  claim 1 , further comprising:
 delivering the safe region to the mobile user.   
     
     
         4 . The method of  claim 1 , wherein the safe region comprises a rectangle having a maximum weighted perimeter. 
     
     
         5 . The method of  claim 4 , wherein calculating the safe region comprises:
 determining a current location of the mobile user;   determining a cell of a grid within which the current location lies; and   constructing the safe region within the cell.   
     
     
         6 . The method of  claim 5 , wherein constructing the rectangle comprises:
 partitioning the cell into a plurality of partitions, where an origin of the plurality of partitions is the current location of the mobile user;   defining a plurality of candidate points within each of the plurality of partitions;   obtaining a plurality of tension points within each of the plurality of partitions from the plurality of candidate points;   defining a plurality of component rectangles, where each component rectangle in the plurality of component rectangles has as a first corner one of the plurality of tension points, the first corner being opposite in the component rectangle from the origin; and   forming the safe region from an intersection of one or more of the plurality of component rectangles.   
     
     
         7 . The method of  claim 6 , wherein the plurality of candidate points comprises a spatial region corner corresponding to the spatial predicate condition. 
     
     
         8 . The method of  claim 6 , wherein the plurality of candidate points comprises one or more intersection points of a boundary of the cell with a spatial region associated with the spatial predicate condition. 
     
     
         9 . The method of  claim 6 , wherein the plurality of candidate points comprises one or more intersection points of the spatial predicate condition with axes of a coordinate system based at the origin. 
     
     
         10 . The method of  claim 6 , wherein the plurality of candidate points comprises one or more intersection points of the cell with axes of a coordinate system based at the origin. 
     
     
         11 . The method of  claim 6 , further comprising:
 trimming the plurality of candidate points prior to obtaining the plurality of tension points.   
     
     
         12 . The method of  claim 11 , wherein the trimming comprises:
 identifying two or more of the plurality of candidate points that intersect an axis of a coordinate system based at the origin; and   removing all but one of the two or more of the plurality of candidate points, where the one is that of the two or more of the plurality of candidate points that is closest to the origin.   
     
     
         13 . The method of  claim 11 , wherein the trimming comprises:
 removing those of the plurality of candidate points that dominate others of the plurality of candidate points.   
     
     
         14 . The method of  claim 6 , wherein the plurality of tension points comprises those of the plurality of candidate points that form a largest possible rectangular region that does not overlap with a spatial region associated with the spatial predicate condition. 
     
     
         15 . The method of  claim 6 , wherein forming the safe region comprises:
 selecting each of the plurality of partitions in decreasing order according to a probability density function of expected future movement of the mobile user; and   identifying, from within each of the plurality of partitions as it is selected, one of the plurality of component rectangles that has a largest weighted perimeter; and   calculating the intersection in accordance with the one of the plurality of component rectangles identified in each of the plurality of partitions.   
     
     
         16 . An apparatus comprising computer readable storage medium containing an executable program for processing updates in the form of a plurality of incoming data streams, the plurality of incoming data streams comprising a first data stream that specifies one or more locations of a mobile user at one or more times and a second data stream that specifies one or more values of a monitored attribute at a location of interest at one or more times, where the program performs steps comprising:
 receiving a location-centric trigger, the location-centric trigger specifying at least one spatial predicate condition relevant to the location of interest and at least one non-spatial predicate condition relevant to the location of interest;   calculating a safe region for the first data stream, the safe region comprising at least one of the one or more locations whose probability of satisfying the spatial predicate condition falls below a first predefined threshold;   calculating a safe value container for the second data stream, the safe value container comprising at least one of the one or more values whose probability of satisfying the non-spatial predicate condition falls below a second predefined threshold; and   processing the first data stream and the second data stream against the location-centric trigger, wherein the processing considers only those of the updates identifying those of the one or more locations that are not contained within the safe region and only monitored data values identifying those of the one or more values that are not contained within the safe value container.   
     
     
         17 . The apparatus of  claim 16 , wherein the steps further comprise:
 activating the location-centric trigger when the processing identifies at least one of the one or more locations that satisfies the spatial predicate condition and at least one of the one or more values that satisfies the non-spatial predicate condition.   
     
     
         18 . A method for assisting in processing a plurality of incoming data streams, the plurality of incoming data streams comprising a first data stream that specifies one or more locations of a mobile user at one or more times and a second data stream that specifies one or more values of a monitored attribute at a location of interest at one or more times, the method comprising:
 delivering a location-centric trigger to a location-based information monitoring system, the location-centric trigger specifying at least one spatial predicate condition relative to the location of interest and at least one non-spatial predicate condition relevant to the location of interest;   receiving a safe region from the location-based information monitoring system, the safe region comprising at least one of the one or more locations whose probability of satisfying the spatial predicate condition falls below a first predefined threshold;   processing a current location of the mobile user against the safe region; and   delivering the current location to the location-based information monitoring system only if the current location lies outside of the safe region,   wherein at least one of: the delivering the location-centric trigger, the receiving, the processing, or the delivering the current location is performed using a processor.   
     
     
         19 . The method of  claim 18 , wherein the safe region comprises a rectangle having a maximum weighted perimeter. 
     
     
         20 . An apparatus comprising computer readable storage medium containing an executable program for assisting in processing a plurality of incoming data streams, the plurality of incoming data streams comprising a first data stream that specifies one or more locations of a mobile user at one or more times and a second data stream that specifies one or more values of a monitored attribute at a location of interest at one or more times, where the program performs steps comprising:
 delivering a location-centric trigger to a location-based information monitoring system, the location-centric trigger specifying at least one spatial predicate condition relative to the location of interest and at least one non-spatial predicate condition relevant to the location of interest;   receiving a safe region from the location-based information monitoring system, the safe region comprising at least one of the one or more locations whose probability of satisfying the spatial predicate condition falls below a first predefined threshold;   processing a current location of the mobile user against the safe region; and   delivering the current location to the location-based information monitoring system only if the current location lies outside of the safe region.