An adaptive peer-to-peer network for distributed caching of OLAP results

ABSTRACT

Peer-to-Peer (P2P) systems are becoming increasingly popular as they enable users to exchange digital information by participating in complex networks. Such systems are inexpensive, easy to use, highly scalable and do not require central administration. Despite their advantages, however, limited work has been done on employing database systems on top of P2P networks.Here we propose the PeerOLAP architecture for supporting On-Line Analytical Processing queries. A large number low-end clients, each containing a cache with the most useful results, are connected through an arbitrary P2P network. If a query cannot be answered locally (i.e. by using the cache contents of the computer where it is issued), it is propagated through the network until a peer that has cached the answer is found. An answer may also be constructed by partial results from many peers. Thus PeerOLAP acts as a large distributed cache, which amplifies the benefits of traditional client-side caching. The system is fully distributed and can reconfigure itself on-the-fly in order to decrease the query cost for the observed workload. This paper describes the core components of PeerOLAP and presents our results both from simulation and a prototype installation running on geographically remote peers.

REFERENCES

• 1: J. Albrecht , W. Lehner, On-Line Analytical Processing in Distributed Data Warehouses, Proceedings of the 1998 International Symposium on Database Engineering & Applications, p.78, July 08-10, 1998
• 2: P. Cao, J. Zhang, and P. B. Beach. Active cache: Caching dynamic contents on the web. In Middleware Conference, 1998.
• 3: 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
• 4: Prasad Deshpande , Jeffrey F. Naughton, Aggregate Aware Caching for Multi-Dimensional Queries, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.167-182, March 27-31, 2000
• 5: 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
• 6: Hector Garcia-Molina , Wilburt J. Labio , Janet L. Wiener , Yue Zhuge, Distributed and parallel computing issues in data warehousing (abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.7, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277701]
• 7: Gnutella. http://gnutella.wego.com.
• 8: S. Gribble, A. Halevy, Z. Ives, M. Rodrig, and D. Suciu. What can databases do for peer-to-peer? In WebDB Workshop, 2001.
• 9: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada
• 10: Richard Hull , Gang Zhou, A framework for supporting data integration using the materialized and virtual approaches, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.481-492, June 04-06, 1996, Montreal, Quebec, Canada
• 11: Icq. http://www.icq.com.
• 12: Panos Kalnis , Dimitris Papadias, Proxy-server architectures for OLAP, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.367-378, May 21-24, 2001, Santa Barbara, California, United States
• 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: Donald Kossmann, The state of the art in distributed query processing, ACM Computing Surveys (CSUR), v.32 n.4, p.422-469, Dec. 2000 [doi>10.1145/371578.371598]
• 15: Yannis Kotidis , Nick Roussopoulos, DynaMat: a dynamic view management system for data warehouses, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.371-382, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 16: Thanasis Loukopoulos , Panos Kalnis , Ishfaq Ahmad , Dimitris Papadias, Active Caching of On-Line-Analytical-Processing Queries in WWW Proxies, Proceedings of the 2001 International Conference on Parallel Processing, p.419-426, September 03-07, 2001
• 17: Napster. http://www.napster.com.
• 18: W. S. Ng, B. C. Ooi, and K. L. Tan. Bestpeer: A self configurable peer-to-peer system (poster). In ICDE, 2002.
• 19: Olap council apb-1 olap benchmark r-ii. http://www.olapcouncil.org.
• 20: M. Tamer Özsu , Patrick Valduriez, Principles of distributed database systems (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 21: 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
• 22: Seti@home. http://setiathome.ssl.berkely.edu.
• 23: Amit Shukla , Prasad Deshpande , Jeffrey F. Naughton, Materialized View Selection for Multidimensional Datasets, Proceedings of the 24rd International Conference on Very Large Data Bases, p.488-499, August 24-27, 1998
• 24: Amit Shukla , Prasad Deshpande , Jeffrey F. Naughton, Materialized View Selection for Multi-Cube Data Models, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.269-284, March 27-31, 2000
• 25: Michael Stonebraker , Paul M. Aoki , Witold Litwin , Avi Pfeffer , Adam Sah , Jeff Sidell , Carl Staelin , Andrew Yu, Mariposa: a wide-area distributed database system, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.1, p.048-063, January 1996 [doi>10.1007/s007780050015]
• 26: Beverly Yang , Hector Garcia-Molina, Comparing Hybrid Peer-to-Peer Systems, Proceedings of the 27th International Conference on Very Large Data Bases, p.561-570, September 11-14, 2001
• 27: Neal Young, On-line caching as cache size varies, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.241-250, January 28-30, 1991, San Francisco, California, United States
• 28: Yihong Zhao , Prasad M. Deshpande , Jeffrey F. Naughton, An array-based algorithm for simultaneous multidimensional aggregates, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.159-170, May 11-15, 1997, Tucson, Arizona, United States

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Public networks
      C.2.4 Distributed Systems
          Subjects: Distributed databases

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases; Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Data sharing

General Terms:
Algorithms, Documentation, Theory