Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Caching frequently accessed items on the mobile client is an important technique to enhance data availability and to improve data access time. Cache replacement policies are used to find a suitable subset of items for eviction from the cache due to limited cache size. The existing policies rely on Euclidean space and consider Euclidean distance as an important parameter for eviction. However, in practice the position and movement of objects are constrained to spatial networks where the important distance measure is the network distance. In this paper we propose a cache replacement policy, which considers the network density, network distance and probability of access as important factors for eviction. We make use of an already proven technique called Progressive incremental network expansion to compute the network distance more efficiently. A series of simulation experiments have been conducted to evaluate the performance of the policy. Results indicate that the proposed cache replacement scheme performs significantly better than the existing policies FAR and PAID and WPRRP.

REFERENCES

• 1: Swarup Acharya , Rafael Alonso , Michael Franklin , Stanley Zdonik, Broadcast disks: data management for asymmetric communication environments, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.199-210, May 22-25, 1995, San Jose, California, United States
• 2: A. Balamash and M. Krunz, "An Overview of Web Caching Replacement Algorithms", IEEE Communications Surveys & Tutorials, 6(2), 2004.
• 3: Daniel Barbará, Mobile Computing and Databases-A Survey, IEEE Transactions on Knowledge and Data Engineering, v.11 n.1, p.108-117, January 1999 [doi>10.1109/69.755619]
• 4: Daniel Barbará , Tomasz Imieliński, Sleepers and workaholics: caching strategies in mobile environments, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.1-12, May 24-27, 1994, Minneapolis, Minnesota, United States
• 5: Keith Cheverst , Nigel Davies , Keith Mitchell , Adrian Friday, Experiences of developing and deploying a context-aware tourist guide: the GUIDE project, Proceedings of the 6th annual international conference on Mobile computing and networking, p.20-31, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345916]
• 6: Margaret H. Dunham , Vijay Kumar, Location Dependent Data and its Management in Mobile Databases, Proceedings of the 9th International Workshop on Database and Expert Systems Applications, p.414, August 26-28, 1998
• 7: Mohammad Kolahdouzan , Cyrus Shahabi, Voronoi-based K nearest neighbor search for spatial network databases, Proceedings of the Thirtieth international conference on Very large data bases, p.840-851, August 31-September 03, 2004, Toronto, Canada
• 8: Mohammad R. Kolahdouzan , Cyrus Shahabi, Alternative Solutions for Continuous K Nearest Neighbor Queries in Spatial Network Databases, Geoinformatica, v.9 n.4, p.321-341, December 2005 [doi>10.1007/s10707-005-4575-8]
• 9: Ajey Kumar , Manoj Misra , A. K. Sarje, A weighted cache replacement policy for location dependent data in mobile environments, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea [doi>10.1145/1244002.1244204]
• 10: Dik Lun Lee , Jianliang Xu , Baihua Zheng , Wang-Chien Lee, Data Management in Location-Dependent Information Services, IEEE Pervasive Computing, v.1 n.3, p.65-72, July 2002 [doi>10.1109/MPRV.2002.1037724]
• 11: Atsuyuki Okabe , Barry Boots , Kokichi Sugihara, Spatial tessellations: concepts and applications of Voronoi diagrams, John Wiley & Sons, Inc., New York, NY, 1992
• 12: Elizabeth J. O'Neil , Patrick E. O'Neil , Gerhard Weikum, The LRU-K page replacement algorithm for database disk buffering, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.297-306, May 25-28, 1993, Washington, D.C., United States
• 13: Qun Ren , Margaret H. Dunham, Using semantic caching to manage location dependent data in mobile computing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.210-221, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345948]
• 14: Maytham Safar, K nearest neighbor search in navigation systems, Mobile Information Systems, v.1 n.3, p.207-224, August 2005
• 15: Liangzhong Yin , Guohong Cao , Ying Cai, A Generalized Target-Driven Cache Replacement Policy for Mobile Environments, Proceedings of the 2003 Symposium on Applications and the Internet, p.14, January 27-31, 2003
• 16: Baihua Zheng , Jianliang Xu , Dik L. Lee, Cache Invalidation and Replacement Strategies for Location-Dependent Data in Mobile Environments, IEEE Transactions on Computers, v.51 n.10, p.1141-1153, October 2002 [doi>10.1109/TC.2002.1039841]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Selection process

General Terms:
Experimentation, Management, Performance

Keywords:
cache replacement, location dependent information services, mobile computing