Using semantic caching to manage location dependent data in mobile computing

ABSTRACT

Location-dependent applications are becoming very popular in mobile environments. To improve system performance and facilitate disconnection, caching is crucial to such applications. In this paper, a semantic caching scheme is used to access location dependent data in mobile computing. We first develop a mobility model to represent the moving behaviors of mobile users and formally define location dependent queries. We then investigate query processing and cache management strategies. The performance of the semantic caching scheme and its replacement strategy FAR is evaluated through a simulation study. Our results show that semantic caching is more flexible and effective for use in LDD applications than page caching, whose performance is quite sensitive to the database physical organization. We also notice that the semantic cache replacement strategy FAR, which utilizes the semantic locality in terms of locations, performs robustly under different kinds of workloads.

REFERENCES

• 1: CSIM18 Simulation Engine (C++ Version): User's Guide. Mesquite Software Inc., Austin, TX, 1998.
• 2: A. Acharya, B. R. Badrinath, T. Imielinski, and J. C. Navas. A www-based location-dependent information service for mobile clients. Technical report, Rutgers University, July 1995.
• 3: Boris Y. L. Chan , Antonio Si , Hong Va Leong, Cache Management for Mobile Databases: Design and Evaluation, Proceedings of the Fourteenth International Conference on Data Engineering, p.54-63, February 23-27, 1998
• 4: Chungmin Melvin Chen , Nicholas Roussopoulos, The implementation and performance evaluation of the ADMS query optimizer: integrating query result caching and matching, Proceedings of the 4th international conference on extending database technology on Advances in database technology, p.323-336, May 1994, Cambridge, United Kingdom
• 5: Shaul Dar , Michael J. Franklin , Björn Þór Jónsson , Divesh Srivastava , Michael Tan, Semantic Data Caching and Replacement, Proceedings of the 22th International Conference on Very Large Data Bases, p.330-341, September 03-06, 1996
• 6: Prasad M. Deshpande , Karthikeyan Ramasamy , Amit Shukla , Jeffrey F. Naughton, Caching multidimensional queries using chunks, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.259-270, June 01-04, 1998, Seattle, Washington, United States
• 7: Margaret H. Dunham , Abdelsalam Helal, Mobile computing and databases: anything new?, ACM SIGMOD Record, v.24 n.4, p.5-9, Dec. 1995 [doi>10.1145/219713.219727]
• 8: 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
• 9: P. Godfrey and J. Gryz. Semantic query caching in heterogeneous databases. In Proceedings of KRDB at VLDB, pages 6.1-6.6, Athens, Greece, August 1997.
• 10: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 11: H. V. Jagadish, Linear clustering of objects with multiple attributes, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.332-342, May 23-26, 1990, Atlantic City, New Jersey, United States
• 12: B. T. Jonsson. Siumei: Design overview and class interfaces. Technical report, University of Maryland, 1996. Available from http://www.cs.umd.edu/projects/dimsum/.
• 13: Arthur M. Keller , Julie Basu, A predicate-based caching scheme for client-server database architectures, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.1, p.035-047, January 1996 [doi>10.1007/s007780050014]
• 14: George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, On indexing mobile objects, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.261-272, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304002]
• 15: Ken. C. K. Lee , H. V. Leong , Antonio Si, Semantic query caching in a mobile environment, ACM SIGMOBILE Mobile Computing and Communications Review, v.3 n.2, p.28-36, April 1999 [doi>10.1145/584027.584029]
• 16: Q. Ren and M. Dunham. Semantic caching and query processing. Technical Report 98-CSE-4, Southern Methodist University, May 1998.
• 17: Qun Ren , Margaret H. Dunham, Using clustering for effective management of a semantic cache in mobile computing, Proceedings of the 1st ACM international workshop on Data engineering for wireless and mobile access, p.94-101, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313300.313418]
• 18: Nicholas Roussopoulos, An incremental access method for ViewCache: concept, algorithms, and cost analysis, ACM Transactions on Database Systems (TODS), v.16 n.3, p.535-563, Sept. 1991 [doi>10.1145/111197.111215]
• 19: Peter Scheuermann , Junho Shim , Radek Vingralek, WATCHMAN: A Data Warehouse Intelligent Cache Manager, Proceedings of the 22th International Conference on Very Large Data Bases, p.51-62, September 03-06, 1996
• 20: A. Prasad Sistla , Ouri Wolfson , Sam Chamberlain , Son Dao, Modeling and Querying Moving Objects, Proceedings of the Thirteenth International Conference on Data Engineering, p.422-432, April 07-11, 1997

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

  C. Computer Systems Organization

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Languages, Measurement, Performance, Theory