GIT-CERCS-06-07
Bugra Gedik, Ling Liu, Kun-Lung Wu, Philip S. Yu,
LIRA: Lightweight, Region-aware Load Shedding in Mobile CQ Systems
Position updates and query re-evaluations are two predominant, costly
components of processing location-based, continual queries (CQs) in mobile
systems. To obtain high-quality query results, the query processor usually
demands receiving frequent position updates from the mobile nodes. However,
processing frequent updates oftentimes causes the query processor to become
overloaded, under which updates must be dropped randomly, bringing down the
quality of query results, negating the benefits of frequent position updates.
In this paper, we develop LIRA − a lightweight, region-aware
load-shedding technique for preventively reducing the position-update load of a
query processor, while maintaining high-quality query results. Instead of
having to receive too many updates and then randomly drop some of them, LIRA
uses a region-aware partitioning mechanism to identify the most beneficial
shedding regions to cut down the position updates sent by the mobile nodes
within those regions. Based on the number of mobile nodes and queries in a region, LIRA
judiciously applies different amounts of update reduction for different
regions, maintaining better overall accuracy of query results. Experimental
results show that LIRA is vastly superior to random update dropping and clearly
outperforms other alternatives that do not possess full-scale, region-aware
load-shedding capabilities. Moreover, due to its lightweight nature, LIRA
introduces very little overhead.