Distributed caching of multi-dimensional data in mobile environments

ABSTRACT

Caching has been an important technique for saving network traffic and reducing response time, especially in mobile environments where bandwidth is often a scarce resource. In this paper, we propose a novel approach for caching multidimensional data in a cluster of mobile devices. In particular, we focus on the most common types of multi-dimensional queries, namely range and k-nearest neighbor queries, by computing a cacheable region for every query, caching the result at the client, and indexing it in an R*-tree at the cluster gateway. Subsequent queries are first issued to the R*-tree and only remainder queries or queries that cannot be guaranteed exact answers are sent to the remote data server. To the best of our knowledge, our work is the first to study caching results from complex multi-dimensional queries (e.g., kNN query) and propose to build an R*-tree on previously fetched query results in a cluster of mobile devices. Rigorous experiments show that our approach significantly reduces network traffic and response time.

REFERENCES

• 1: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 2: 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
• 3: Averill M. Law , David M. Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1999
• 4: Liu, B., Lee, W., Lee, D. Distributed Caching of Multi-dimensional Data in Mobile Environments. (available at http://ihome.ust.hk/~liubin).
• 5: 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]
• 6: Qun Ren , Margaret H. Dunham , Vijay Kumar, Semantic Caching and Query Processing, IEEE Transactions on Knowledge and Data Engineering, v.15 n.1, p.192-210, January 2003 [doi>10.1109/TKDE.2003.1161590]
• 7: http://www.census.gov/geo/www/tiger/
• 8: Baihua Zheng , Dik Lun Lee, Semantic Caching in Location-Dependent Query Processing, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.97-116, July 12-15, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Algorithms, Experimentation

Keywords:
caching, mobile data management, multi-dimensional database