Efficient processing of location-cloaked queries

When requesting location-based services, users can associate their queries with a purposely blurred location such as a circular or rectangular geographic region instead of their exact position. This strategy makes it possible for privacy protection, but presents problems in query processing. Since the server does not know a user's exact position, it has to retrieve query results for each position inside the user's cloaking region. While the server workload dramatically increases, a client downloading all query results will waste its battery power, because most of the data may be irrelevant to its query interest. This paper considers the problems of efficient processing of location-cloaked queries (LCQs). Our key observation is that queries may overlap in their cloaking regions and thus share some query results. In light of this, we propose to process queries as a batch instead of one by one independently. The technical contributions of this paper are threefold. 1) We propose to decompose queries into subqueries based on their interested region. Since the subqueries with a common region need to be processed only once, the server workload is minimized. 2) We propose a novel scheduling technique that addresses the dilemma between minimizing server latency and ensuring good fairness in query processing. 3) We present a personalized air indexing technique by which a client can filter out and download only the needed query results, thus avoiding the waste of energy in downloading irrelevant data.