loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Scalable Cache Invalidation Algorithms for Mobile Data Access
November/December 2003 (vol. 15 no. 6)
pp. 1498-1511
ASCII Text
x 
 
Ahmed Elmagarmid, Jin Jing, Abdelsalam (Sumi) Helal, Choonhwa Lee, "Scalable Cache Invalidation Algorithms for Mobile Data Access," IEEE Transactions on Knowledge and Data Engineering, vol. 15, no. 6, pp. 1498-1511, November/December, 2003.
 
 
BibTex
x
 
@article{ 10.1109/TKDE.2003.1245288,
author = {Ahmed Elmagarmid and Jin Jing and Abdelsalam (Sumi) Helal and Choonhwa Lee},
title = {Scalable Cache Invalidation Algorithms for Mobile Data Access},
journal ={IEEE Transactions on Knowledge and Data Engineering},
volume = {15},
number = {6},
issn = {1041-4347},
year = {2003},
pages = {1498-1511},
doi = {http://doi.ieeecomputersociety.org/10.1109/TKDE.2003.1245288},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Knowledge and Data Engineering
TI - Scalable Cache Invalidation Algorithms for Mobile Data Access
IS - 6
SN - 1041-4347
SP1498
EP1511
EPD - 1498-1511
A1 - Ahmed Elmagarmid,
A1 - Jin Jing,
A1 - Abdelsalam (Sumi) Helal,
A1 - Choonhwa Lee,
PY - 2003
KW - Mobile data access
KW - cache invalidation
KW - disconnected operation
KW - data broadcast.
VL - 15
JA - IEEE Transactions on Knowledge and Data Engineering
ER -
 

Abstract—In this paper, we address the problem of cache invalidation in mobile and wireless client/server environments. We present cache invalidation techniques that can scale not only to a large number of mobile clients, but also to a large number of data items that can be cached in the mobile clients. We propose two scalable algorithms: the Multidimensional Bit-Sequence (MD-BS) algorithm and the Multilevel Bit-Sequence (ML-BS) algorithm. Both algorithms are based on our prior work on the Basic Bit-Sequences (BS) algorithm. Our study shows that the proposed algorithms are effective for a large number of cached data items with low update rates. The study also illustrates that the algorithms can be used with other complementary techniques to address the problem of cache invalidation for data items with varied update and access rates.

[1] S. Acharya, R. Alonso, M. Franklin, and S. Zdonik, “Broadcast Disks: Data Management for Asymmetric Communication Environments,” Proc. ACM SIGMOD, pp. 199-210, May 1995.
[2] D. Barbara and T. Imielinski, “Sleepers and Workaholics: Caching Strategies in Mobile Environments,” Proc. ACM SIGMOD, pp. 1-12, May 1994.
[3] M.J. Franklin, Caching and Memory Management in Client-Server Database Systems PhD thesis, Univ. of Wisconsin-Madison, 1993.
[4] Y. Huang, P. Sistla, and O. Wolfson, "Data Replication for Mobile Computers," Proc. ACM-SIGMOD Int'l Conf. Management of Data,Minneapolis, Minn., May 1994.
[5] T. Imielinski and B.R. Badrinath, “Wireless Computing: Challenges in Data Management,” Comm. ACM, vol. 37, no. 10, Oct. 1994.
[6] T. Imielinski, S. Viswanathan, and B.R. Badrinath, “Energy Efficient Indexing on Air,” Proc. ACM SIGMOD Conf., pp. 25-36, May 1994.
[7] J. Jing, A. Elmagarmid, A. Helal, and R. Alonso, “Bit-Sequences: An Adaptive Cache Invalidation Method in Mobile Client/Server Environments,” Mobile Networks and Applications, vol. 2, pp. 115-127, 1997.
[8] V. Liberatore, Multicast Scheduling for List Requests Proc. INFOCOM, pp. 1129-1137, 2002.
[9] L.B. Mummert and M. Satyanarayanan, “Variable Granularity Cache Coherence,” Operating Systems Rev., vol. 28, no. 1, pp. 55-60, Jan. 1994.
[10] K. Tan, J. Cai, and B. Ooi, “Evaluation of Cache Invalidation Strategies in Wireless Environments,” IEEE Trans. Parallel and Distributed Systems, vol. 12, no. 8, pp. 789-807, Aug. 2001.
[11] K.L. Wu, P.S. Yu, and M.S. Chen, “Energy-Efficient Caching for Wireless Mobile Computing, Proc. 20th Int'l Conf. Data Eng., pp. 336-345, Mar. 1996.

Index Terms:
Mobile data access, cache invalidation, disconnected operation, data broadcast.
Citation:
Ahmed Elmagarmid, Jin Jing, Abdelsalam (Sumi) Helal, Choonhwa Lee, "Scalable Cache Invalidation Algorithms for Mobile Data Access," IEEE Transactions on Knowledge and Data Engineering, vol. 15, no. 6, pp. 1498-1511, Nov./Dec. 2003, doi:10.1109/TKDE.2003.1245288
Usage of this product signifies your acceptance of the Terms of Use.