Optimized query planning of continuous aggregation queries in dynamic data dissemination networks

ABSTRACT

Continuous queries are used to monitor changes to time varying data and to provide results useful for online decision making. Typically a user desires to obtain the value of some aggregation function over distributed data items, for example, to know (a) the average of temperatures sensed by a set of sensors (b) the value of index of mid-cap stocks. In these queries a client specifies a coherency requirement as part of the query. In this paper we present a low-cost, scalable technique to answer continuous aggregation queries using a content distribution network of dynamic data items. In such a network of data aggregators, each data aggregator serves a set of data items at specific coherencies. Just as various fragments of a dynamic web-page are served by one or more nodes of a content distribution network, our technique involves decomposing a client query into sub-queries and executing sub-queries on judiciously chosen data aggregators with their individual sub-query incoherency bounds. We provide a technique of getting the optimal query plan (i.e., set of sub-queries and their chosen data aggregators) which satisfies client query.s coherency requirement with least cost, measured in terms of the number of refresh messages sent from aggregators to the client. For estimating query execution cost, we build a continuous query cost model which can be used to estimate the number of messages required to satisfy the client specified incoherency bound. Performance results using real-world traces show that our cost based query planning leads to queries being executed using less than one third the number of messages required by existing schemes.

REFERENCES

• 1: A. Davis , J. Parikh , W. E. Weihl, Edgecomputing: extending enterprise applications to the edge of the internet, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013397]
• 2: Anindya Datta , Kaushik Dutta , Helen Thomas , Debra Vandermeer , Krithi Ramamritham, Proxy-based acceleration of dynamically generated content on the world wide web: An approach and implementation, ACM Transactions on Database Systems (TODS), v.29 n.2, p.403-443, June 2004 [doi>10.1145/1005566.1005571]
• 3: John Dilley , Bruce Maggs , Jay Parikh , Harald Prokop , Ramesh Sitaraman , Bill Weihl, Globally Distributed Content Delivery, IEEE Internet Computing, v.6 n.5, p.50-58, September 2002 [doi>10.1109/MIC.2002.1036038]
• 4: S. Rangarajan, S. Mukerjee and P. Rodriguez. User Specific Request Redirection in a Content Delivery Network, 8th Intl. Workshop on Web Content Caching and Distribution (IWCW), 2003.
• 5: S. Shah, K. Ramamritham, and P. Shenoy. Maintaining Coherency of Dynamic Data in Cooperating Repositories. VLDB 2002.
• 6: Dynamai: Caching Technology for Dynmaic Content Revealed. www.infoworld.com/articles.
• 7: D. S. Hochbaum. Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing, vol. 11 (3), 1982.
• 8: Zongming Fei. A Novel Approach to Managing Consistency in Content Distribution. WCW 2001.
• 9: Rajeev Gupta , Ashish Puri , Krithi Ramamritham, Executing incoherency bounded continuous queries at web data aggregators, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060758]
• 10: Optimized Execution of Continuous Queries, APS 2006, www.cse.iitb.ac.in/~grajeev/APS06.PDF
• 11: Chris Olston , Jing Jiang , Jennifer Widom, Adaptive filters for continuous queries over distributed data streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872825]
• 12: Shetal Shah , Krithi Ramamritham , Chinya Ravishankar, Client assignment in content dissemination networks for dynamic data, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 13: NEFSC Scientific Computer System http://sole.wh.whoi.edu/~jmanning//cruise/serve1.cgi
• 14: Query cost model validation for sensor data. www.cse.iitb.ac.in/~ravivj/BTP06.pdf.
• 15: D. S. Hochbaum. Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing, vol. 11 (3), 1982.
• 16: S. Zhu and C. Ravishankar. Stochastic Consistency and Scalable Pull-Based Caching for Erratic Data Sources. VLDB 2004.
• 17: David Chu , Amol Deshpande , Joseph M. Hellerstein , Wei Hong, Approximate Data Collection in Sensor Networks using Probabilistic Models, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.48, April 03-07, 2006 [doi>10.1109/ICDE.2006.21]
• 18: A. Deshpande, C. Guestrin, S. R. Madden, J. M. Hellerstein, and W. Hong. Model-Driven Data Acquisition in Sensor Networks. VLDB, 2004.
• 19: Pearson Product moment correlation coefficient. http://www.nyx.net/~tmacfarl/STAT_TUT/correlat.ssi
• 20: Wai Lam , Chao Yang Ho, Using a generalized instance set for automatic text categorization, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.81-89, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290961]
• 21: Graham Cormode , Minos Garofalakis, Sketching streams through the net: distributed approximate query tracking, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 22: Shweta Agrawal , Krithi Ramamritham , Shetal Shah, Construction of a Coherency Preserving Dynamic Data Dissemination Network, Proceedings of the 25th IEEE International Real-Time Systems Symposium (RTSS'04), p.286-295, December 05-08, 2004 [doi>10.1109/REAL.2004.16]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Algorithms, Design, Management, Measurement, Performance

Keywords:
content distribution networks, continuous aggregation queries, data coherency, dynamic data, query dissemination cost