Author
S Prabhakar, Y Xia, D Kalashnikov, WG Aref, S Hambrusch
Abstract
Moving object environments are characterized by large numbers of moving objects and numerous concurrent continuous
queries over these objects. Efficient evaluation of these queries in response to the movement of the objects is critical for
supporting acceptable response times. In such environments the traditional approach of building an index on the objects
(data) suffers from the need for frequent updates and thereby results in poor performance. In fact, a brute force, no-index
strategy yields better performance in many cases. Neither the traditional approach, nor the brute force strategy achieve
reasonable query processing times. This paper develops novel techniques for the efficient and scalable evaluation of multiple
continuous queries on moving objects. Our solution leverages two complimentary techniques: Query Indexing and Velocity
Constrained Indexing (VCI). Query Indexing relies on i) incremental evaluation; ii) reversing the role of queries and data;
and iii) exploiting the relative locations of objects and queries. VCI takes advantage of the maximum possible speed of
objects in order to delay the expensive operation of updating an index to reflect the movement of objects. In contrast to
an earlier technique [29] that requires exact knowledge about the movement of the objects, VCI does not rely on such
information. While Query Indexing outperforms VCI, it does not efficiently handle the arrival of new queries. Velocity
constrained indexing, on the other hand, is unaffected by changes in queries. We demonstrate that a combination of Query
Indexing and Velocity Constrained Indexing enables the scalable execution of insertion and deletion of queries in addition
to processing ongoing queries. We also develop several optimizations and present a detailed experimental evaluation of our
techniques. The experimental results show that the proposed schemes outperform the traditional approaches by almost two
orders of magnitude.
