Adaptive filters for continuous queries over distributed data streams

ABSTRACT

We consider an environment where distributed data sources continuously stream updates to a centralized processor that monitors continuous queries over the distributed data. Significant communication overhead is incurred in the presence of rapid update streams, and we propose a new technique for reducing the overhead. Users register continuous queries with precision requirements at the central stream processor, which installs filters at remote data sources. The filters adapt to changing conditions to minimize stream rates while guaranteeing that all continuous queries still receive the updates necessary to provide answers of adequate precision at all times. Our approach enables applications to trade precision for communication overhead at a fine granularity by individually adjusting the precision constraints of continuous queries over streams in a multi-query workload. Through experiments performed on synthetic data simulations and a real network monitoring implementation, we demonstrate the effectiveness of our approach in achieving low communication overhead compared with alternate approaches.

REFERENCES

• 1: Rafael Alonso , Daniel Barbará , Hector Garcia-Molina , Soraya Abad, Quasi-Copies: Efficient Data Sharing for Information Retrieval Systems, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.443-468, March 14-18, 1988
• 2: Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603884]
• 3: Daniel Barbará , Hector Garcia-Molina, The Demarcation Protocol: A Technique for Maintaining Linear Arithmetic Constraints in Distributed Database Systems, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.373-388, March 23-27, 1992
• 4: P. A. Bernstein, B. T. Blaustein, and E. M. Clarke. Fast maintenance of semantic integrity assertions using redundant aggregate data. In Proc. VLDB, 1980.
• 5: D. Carney, U. Cetintemel, M. Cherniack, C. Convey, S. Lee, G. Seidman, M. Stonebraker, N. Tatbul, and S. Zdonik. Monitoring streams - a new class of data management applications. In Proc. VLDB, 2002.
• 6: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 7: M. Dilman and D. Raz. Efficient reactive monitoring. In Proc. InfoCom, 2001.
• 8: D. Estrin, L. Girod, G. Pottie, and M. Srivastava. Instrumenting the world with wireless sensor networks. In Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2001.
• 9: Ashish Gupta , Jennifer Widom, Local verification of global integrity constraints in distributed databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.49-58, May 25-28, 1993, Washington, D.C., United States
• 10: A. Householder, A. Manion, L. Pesante, and G. Weaver. Managing the threat of denial-of-service attacks. Technical report, CMU Software Engineering Institute CERT Coordination Center, Oct. 2001. http://www.cert.org/archive/pdf/ Managing DoS.pdf.
• 11: Nam Huyn, Maintaining Global Integrity Constraints in DistributedDatabases, Constraints, v.2 n.3-4, p.377-399, 1997 [doi>10.1023/A:1009703814570]
• 12: J. M. Kahn , R. H. Katz , K. S. J. Pister, Next century challenges: mobile networking for “Smart Dust”, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.271-278, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313558]
• 13: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 14: C. T. Lawrence, J. L. Zhou, and A. L. Tits. User's guide for CFSQP version 2.5. Technical report TR-94-16r1, Institute for Systems Research, University of Maryland, 1997.
• 15: Jane W. S. Liu , Kwei-Jay Lin , Wei-Kuan Shih , Albert Chuang-shi Yu , Jen-Yao Chung , Wei Zhao, Algorithms for Scheduling Imprecise Computations, Computer, v.24 n.5, p.58-68, May 1991 [doi>10.1109/2.76287]
• 16: Ling Liu , Calton Pu , Wei Tang, Continual Queries for Internet Scale Event-Driven Information Delivery, IEEE Transactions on Knowledge and Data Engineering, v.11 n.4, p.610-628, July 1999 [doi>10.1109/69.790816]
• 17: S. Madden and M. J. Franklin. Fjording the stream: An architecture for queries over streaming sensor data. In Proc. ICDE, 2002.
• 18: Samuel Madden , Mehul Shah , Joseph M. Hellerstein , Vijayshankar Raman, Continuously adaptive continuous queries over streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564698]
• 19: D. L. Mills. Internet time synchronization: the network time protocol. IEEE Transactions on Communications, 39(10), 1991.
• 20: Rex Min , Manish Bhardwaj , Seong-Hwan Cho , Eugene Shih , Amit Sinha , Alice Wang , Anantha Chandrakasan, Low-Power Wireless Sensor Networks, Proceedings of the The 14th International Conference on VLSI Design (VLSID '01), p.205, January 03-07, 2001
• 21: Sue B. Moon , Jim Kurose , Don Towsley, Packet audio playout delay adjustment: performance bounds and algorithms, Multimedia Systems, v.6 n.1, p.17-28, Jan. 1998 [doi>10.1007/s005300050073]
• 22: R. Motwani, J. Widom, A. Arasu, B. Babcock, S. Babu, M. Datar, G. Manku, C. Olston, J. Rosenstein, and R. Varma. Query processing, resource management, and approximation in a data stream management system. In Proc. First Biennial Conference on Innovative Data Systems Research (CIDR), 2003.
• 23: C. Olston, J. Jiang, and J. Widom. Adaptive filters for continuous queries over distributed data streams. Technical report, Stanford University Computer Science Department, 2002. http://dbpubs.stanford.edu/pub/2002-55.
• 24: Chris Olston , Boon Thau Loo , Jennifer Widom, Adaptive precision setting for cached approximate values, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.355-366, May 21-24, 2001, Santa Barbara, California, United States
• 25: Chris Olston , Jennifer Widom, Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data, Proceedings of the 26th International Conference on Very Large Data Bases, p.144-155, September 10-14, 2000
• 26: Chris Olston , Jennifer Widom, Best-effort cache synchronization with source cooperation, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564701]
• 27: Vern Paxson , Sally Floyd, Wide area traffic: the failure of Poisson modeling, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.226-244, June 1995 [doi>10.1109/90.392383]
• 28: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 29: S. Shah, A. Bernard, V. Sharma, K. Ramamritham, and P. Shenoy. Maintaining temporal coherency of cooperating dynamic data repositories. In Proc. VLDB, 2002.
• 30: T. Skalicky. Laspack reference manual, 1996. http://www.tudresden.de/mwism/skalicky/laspack/laspack.html.
• 31: Nandit Soparkar , Abraham Silberschatz, Data-valued partitioning and virtual messages (extended abstract), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.357-367, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298587]
• 32: R. van Renesse and K. Birman. Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining. Technical report, Cornell University, 2001.
• 33: S. Vutukury and J. Garcia-Luna-Aceves. A traffic engineering approach based on minimum-delay routing. In Proc. IEEE International Conference on Computer Communications and Networks, 2000.
• 34: Annita N. Wilschut , Peter M. G. Apers, Dataflow query execution in a parallel main-memory environment, Proceedings of the first international conference on Parallel and distributed information systems, p.68-77, December 1991, Miami, Florida, United States
• 35: Takao Yamashita, Dynamic Replica Control Based on Fairly Assigned Variation of Data with Weak Consistency for Loosely Coupled Distributed Systems, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.280, July 02-05, 2002
• 36: Haifeng Yu , Amin Vahdat, Efficient Numerical Error Bounding for Replicated Network Services, Proceedings of the 26th International Conference on Very Large Data Bases, p.123-133, September 10-14, 2000

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing; Query processing

General Terms:
Algorithms, Design, Experimentation, Performance