GIT-CERCS-10-06
Myungcheol Doo, Ling Liu, Nitya Narasimhan, Venu Vasudevan,
Mondrian Tree: Efficient Indexing Structure for Scalable Spatial Triggers Processing over Mobile Environment
Spatial Alarms are reminders for mobile users upon their arrival of certain spatial location of interest. 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. Existing techniques for processing spatial alarms cannot solve these two problems at the same time. In this paper we present the design and implementation of a new indexing technique, Mondrian tree. The Mondrian tree indexing method partitions the entire universe of discourse into spatial alarm monitoring regions and alarm-free regions. This enables us to reduce the number of on-demand alarm-free region computations, significant saving of both server load and client to server communication cost. We evaluate the efficiency of the Mondrian tree indexing approach using a road network simulator and show that the Mondrian tree offers significant performance
enhancements on spatial alarm processing at both the server side and the client side.