GIT-CERCS-08-07
Bhuvan Bamba, Ling Liu, Philip S. Yu,
Scalable Processing of Spatial Alarms
Spatial alarms extend the idea of time-based alarms to the spatial
dimension. Just as time-based alarms are set to remind us of the arrival
of a future reference time point, spatial alarms are set on a spatial
location of interest which the subscribers of the alarm will travel to
sometime in the future. Spatial alarm processing requires meeting two
demanding objectives: high accuracy, which ensures zero or very low alarm
misses, and high scalability, which requires highly efficient and optimal
processing of spatial alarms. In
this paper we present a motion-aware framework, facilitated by two
systematic methods, for scalable processing of spatial alarms. First, we
introduce the concept of safe period to minimize the number of unnecessary
spatial alarm evaluations, increasing the throughput and scalability of
the system. We show that our safe period-based alarm evaluation techniques
can significantly reduce the server load for spatial alarm processing
compared to the periodic evaluation
approach, while preserving the accuracy and timeliness of spatial alarms.
Second, we develop a suite of spatial alarm grouping techniques based on
spatial locality of the alarms and motion behavior of the mobile users,
which reduces the safe period computation cost for spatial alarm
evaluation at the server side. We evaluate the scalability and accuracy of
our approach using a road network simulator and show that the proposed
motion-aware safe period-based approach to spatial alarm processing offers
significant performance enhancements for the alarm processing server while
maintaining high accuracy of spatial alarms, especially compared to the
conventional periodic alarm evaluation approach.