In mobile environments, mobile clients can accessinformation with respect to their locations by submittingLocation-Dependent Spatial Queries (LDSQs) to Location-Based Service (LBS) servers. Owing to scarce wirelesschannel bandwidth and limited client battery life, frequentLDSQ submission from clients must be avoided. Observingthat LDSQs issued from a client located at nearby positionswould likely return the same query results, we explore theidea of valid scope, which represents a spatial area in whicha set of LDSQs will retrieve exactly the same set of queryresults. With a valid scope derived and an LDSQ resultcached, a client can assert whether the new LDSQs can beanswered with the maintained LDSQ result, thus eliminatingthe need of sending LDSQs to the server. Contention onthe wireless channel and client energy consumed for datatransmission can be considerably reduced. In this paper,we design efficient algorithms to compute the valid scopefor common types of LDSQs, including nearest neighborqueries, range queries and window queries. Through anextensive set of experiments, our proposed valid scopecomputation algorithms are shown to outperform existingapproaches.
展开▼