Quality of service in stateful information filters

ABSTRACT

Information Filters play an important role in processing streams of events, both for filtering as well as routing events based on their content. Stateful information filters like AGILE [15], Cayuga [13] and SASE [24] have gained a significant amount of attention recently. Such filters not only consider the data of a single event, but also additional state such as a sequence of previous events or a context state. Applications for Wireless Sensors and RFID data are particularly prominent examples for the need for stateful information filtering, with use cases like event correlation or sensor data affecting the routing of other events. While quality of service has been researched fairly thoroughly for networking systems and general data stream management systems, no comprehensive work exists for information filters. The goal of this work is to present QoS criteria for stateful information filters and to examine how QoS control methods established in other areas can be applied to information filters.

REFERENCES

• 1: http://www.tibco.com.
• 2: Java Message Service. http://java.sun.com/products/jms.
• 3: Microsoft BizTalk. http://www.microsoft.com/biztalk/.
• 4: Oracle Streams. http://www.oracle.com/technology/products/dataint/index.html.
• 5: Websphere MQ. http://www-306.ibm.com/software/integration/wmq/.
• 6: Brian Babcock , Mayur Datar , Rajeev Motwani, Load Shedding for Aggregation Queries over Data Streams, Proceedings of the 20th International Conference on Data Engineering, p.350, March 30-April 02, 2004
• 7: Jochen Van den Bercken , Bernhard Seeger, An Evaluation of Generic Bulk Loading Techniques, Proceedings of the 27th International Conference on Very Large Data Bases, p.461-470, September 11-14, 2001
• 8: S. Blake , D. Black , M. Carlson , E. Davies , Z. Wang , W. Weiss, An Architecture for Differentiated Service, RFC Editor, 1998
• 9: Nicolas Bruno , Nick Koudas , Divesh Srivastava, Holistic twig joins: optimal XML pattern matching, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564727]
• 10: Antonio Carzaniga , David S. Rosenblum , Alexander L. Wolf, Design and evaluation of a wide-area event notification service, ACM Transactions on Computer Systems (TOCS), v.19 n.3, p.332-383, Aug. 2001 [doi>10.1145/380749.380767]
• 11: C. Y. Chan, P. Felber, M. N. Garofalakis, and R. Rastogi. Efficient Filtering of XML Documents with XPath Expressions. In ICDE, 2002.
• 12: Yun Chi , Haixun Wang , Philip S. Yu, Loadstar: load shedding in data stream mining, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 13: A. J. Demers, J. Gehrke, M. Hong, M. Riedewald, and W. M. White. Towards expressive publish/subscribe systems. In EDBT, 2006.
• 14: Yanlei Diao , Mehmet Altinel , Michael J. Franklin , Hao Zhang , Peter Fischer, Path sharing and predicate evaluation for high-performance XML filtering, ACM Transactions on Database Systems (TODS), v.28 n.4, p.467-516, December 2003 [doi>10.1145/958942.958947]
• 15: Jens-Peter Dittrich , Peter M. Fischer , Donald Kossmann, AGILE: adaptive indexing for context-aware information filters, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066183]
• 16: Françoise Fabret , H. Arno Jacobsen , François Llirbat , Joăo Pereira , Kenneth A. Ross , Dennis Shasha, Filtering algorithms and implementation for very fast publish/subscribe systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.115-126, May 21-24, 2001, Santa Barbara, California, United States
• 17: P. M. Fischer. Adaptive Optimization Techniques for Context-Aware Information Filters. PhD thesis, ETH Zurich, 2006.
• 18: Peter M. Fischer , Donald Kossmann, Batched Processing for Information Filters, Proceedings of the 21st International Conference on Data Engineering, p.902-913, April 05-08, 2005 [doi>10.1109/ICDE.2005.25]
• 19: Sally Floyd , Van Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.397-413, Aug. 1993 [doi>10.1109/90.251892]
• 20: Ashish Kumar Gupta , Dan Suciu, Stream processing of XPath queries with predicates, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872809]
• 21: J. Nagle, Congestion control in IP/TCP internetworks, RFC Editor, 1984
• 22: P. Pietzuch and S. Bhola. Congestion Control in a Reliable Scalable Message-Oriented Middleware. In ACM/IFIP/USENIX International Middleware Conference, 2003.
• 23: Nesime Tatbul , Uğur Çetintemel , Stan Zdonik , Mitch Cherniack , Michael Stonebraker, Load shedding in a data stream manager, Proceedings of the 29th international conference on Very large data bases, p.309-320, September 09-12, 2003, Berlin, Germany
• 24: Eugene Wu , Yanlei Diao , Shariq Rizvi, High-performance complex event processing over streams, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142520]