SELECTIVE PROCESSING OF LOCATION-SENSITIVE DATA STREAMS

• US 20120276930A1
• Filed: 05/11/2012
• Published: 11/01/2012
• Est. Priority Date: 10/07/2009
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: GEDIK, Bugra, WU, Kun-Lung, BAMBA, Bhuvan
• Application Number:
  US13/469,350
• Publication Number:
  US 20120276930A1
• Time in Patent Office: Days
• US Class Current: 455/456.3
• CPC Class Codes: H04W 24/08 Testing, supervising or monitoring using real traffic
• CPC Class Codes: H04W 4/025 using location based information parameters

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.

Claims

1. A method for processing updates contained in at least 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 trigger, the 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;

discarding a first plurality of the updates whose probability of satisfying the spatial predicate condition falls below a first threshold;

discarding a second plurality of the updates whose probability of satisfying the non-spatial predicate condition falls below a second threshold; and

processing only those of the updates that are not discarded against the location-centric trigger,

wherein at least one of;

the receiving, the discarding a first plurality of the updates, the discarding a second plurality of the updates, or the processing is performed using a processor.

2. The method of claim 1, wherein the discarding the first plurality of the updates comprises:

calculating a safe region for the first data stream, where the safe region comprises at least one of the one or more locations whose probability of satisfying the spatial predicate condition falls below the first threshold; and

discarding those of the updates that specify locations contained within the safe region.

3. The method of claim 2, further comprising:

delivering the safe region to the mobile user.

4. The method of claim 2, 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. The method of claim 1, wherein the discarding the second plurality of the updates comprises:

calculating a safe value container for the second data stream, where the safe value container comprises at least one of the one or more values whose probability of satisfying the non-spatial predicate condition falls below the second threshold; and

discarding those of the updates that specify values contained within the safe region.

17. The method of claim 1, further comprising:

activating the 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. An apparatus comprising computer readable storage medium containing an executable program for processing updates contained in 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 trigger, the 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;

discarding a first plurality of the updates whose probability of satisfying the spatial predicate condition falls below a first threshold;

discarding a second plurality of the updates whose probability of satisfying the non-spatial predicate condition falls below a second threshold; and

processing only those of the updates that are not discarded against the location-centric trigger,

wherein at least one of;

the receiving, the discarding a first plurality of the updates, the discarding a second plurality of the updates, or the processing is performed using a processor.

19. The apparatus of claim 18, wherein the discarding the first plurality of the updates comprises:

calculating a safe region for the first data stream, where the safe region comprises at least one of the one or more locations whose probability of satisfying the spatial predicate condition falls below the first threshold; and

discarding those of the updates that specify locations contained within the safe region.

20. The apparatus of claim 18, wherein the discarding the second plurality of the updates comprises:

calculating a safe value container for the second data stream, where the safe value container comprises at least one of the one or more values whose probability of satisfying the non-spatial predicate condition falls below the second threshold; and

discarding those of the updates that specify values contained within the safe region.