A Practical Approach of Composing Near-Optimal Invalidation Reports for Mobile Databases

Caching can reduce expensive data transfers and improve the performance of mobile computing. To reuse caches after short disconnections, invalidation reports are broadcast to clients to identify outdated items. Detailed reports may not be desirable because they can consume too much bandwidth. On the other hand, false invalidations set in if accurate timing of updates is not provided. We observe that false invalidation rates are closely related to clients’ reconnection patterns and show that in theory, for any given reconnection pattern, a report with a minimal false invalidation rate can be derived. For practical uses, we capture the reconnection pattern by sampling and use the pattern to compose a near-optimal invalidation reports. This method is simple and fast. Experimental results have confirmed that our method is indeed close to optimal and more effective in reducing the false invalidation rate than others