An efficient location update mechanism for continuous queries over moving objects

Abstract

In a moving-object database system that supports continuous queries (CQ), an important problem is to keep the location data consistent with the actual locations of the entities being monitored, in order to produce correct query results. This goal is often difficult to achieve due to limited network resources. However, if an object is not required by any query, its value need not be refreshed. Based on this observation, we redefine the notion of temporal consistency of data items with respect to the query result, where only data items that are relevant to the CQs need to be fresh. To exploit this correctness definition, we develop an adaptive time-based update technique called query-result update (QRU). The advantage of this technique is that it identifies objects with different levels of significance to the correctness of query results. Locations of objects that have more impact to the query result are acquired more frequently than the ones that do not. To achieve this objective, queries are classified into rank-based (i.e., ranks of objects are critical to query results) and non-rank-based. For each query class, QRU decides the time instant that an object should send a location update based on the predicted impact of the object to the query result. Moreover, the location update frequency of each object is continuously adjusted in order to adapt to the accuracy of the prediction model used. We evaluate the effectiveness of QRU by simulating execution of CQs over synthetic and real data sets. We also compare QRU experimentally with existing location update policies, namely the distance-based method, the time-based method, the speed dead-reckoning method, as well as the safe region strategy. © 2006 Elsevier B.V. All rights reserved.