PIPES - a Public Infrastructure for Processing and Exploring Streams

Latest News

Motivation

Research Topics

• Adaptive memory managemant, scheduling and query optimization inside a generic runtime infrastructure
• Stream maintenance as well as indexing for historical queries
• Maintainance of nonparametric estimators over data streams
• Adaption of data mining techniques for data streams
• Static and dynamic multi-query optimization
• Sort-based multi-way joins over data streams

People

Faculty: Prof. Dr. Bernhard Seeger

Additionally, we want to thank all people not listed above that actively supported the development of PIPES with their ideas, programming, and master theses.

Download

Overview

The infrastructure PIPES is composed of several interacting frameworks. The core framework allows to construct directed acyclic query graphs based on a publish-subscribe mechanism integrated into the graph nodes. We distinguish between three different types of graph nodes: A source transfers its elements to a set of subscribed sinks. A sink can subscribe and unsubscribe to multiple sources, respectively. During its subscription, it processes all incoming elements delivered by its sources. All operators satisfy the interface pipe that combines the functionality of a sink and a source. Hence, a pipe processes the incoming elements and transfers its outgoing elements to all subscribed sinks. A powerful and generic operator algebra provides the basis for the query construction framework. It relies on a well-defined, deterministic temporal semantics over time intervals that guarantees snapshot-equivalence. As a result, PIPES covers the functionality of the Continuous Query Language (CQL). Our operator algebra supports all operations known from the extended relational algebra, except sorting, whereas the operators are independent from concrete data types due to a parameterization with user-defined functions and predicates. Their data-driven implementation relies on time-based sliding windows and an incremental evaluation to ensure a non-blocking behavior. The current state of an operator is maintained by employing so-called SweepAreas, highly dynamic data structures with efficient insertion, retrieval, and reorganization capabilities managing the content of a sliding window. By adjusting the window size, the resource requirements of an operator can be controlled at runtime.
In order to build a DSMS, PIPES also contains separate frameworks that establish a basis for other essential runtime components, namely the scheduler, the memory manager, and the query optimizer. These components are controlled by flexible strategies which typically incorporate operator metadata maintained at runtime, e.g. mean stream rates or operator selectivities. Therefore, each node in a query graph continuously collects and updates relevant metadata information that is maintained in an online manner.
The scheduling framework provided by PIPES consists of a 3-layer architecture. In the lowest layer, multiple successive nodes in a query graph can be combined as a virtual node with an inherently push-based processing. This novel approach substantially reduces the communication overhead since it does not require any inter-operator queues. The middle layer allows to schedule virtual nodes within a single thread by decoupling successive virtual nodes with the help of an operator that buffers elements. In the top layer, all threads of the middle layer are scheduled. This hybrid approach benefits from neither being restricted to a single thread for scheduling nor assigning a separate thread per operator. Due to dynamic system load caused by varying stream rates and frequent query graph modifications, scalability may suffer from limited memory resources.
To overcome this problem, the memory manager offers a flexible framework for an adaptive memory management. It globally assigns and redistributes the available memory among stateful operators at runtime. Furthermore, it takes approximate query answers into account by applying user-defined load-shedding techniques whenever an operator exceeds its memory consumption limit. The query optimizer is based on the semantics of our temporal operator algebra that retains most traditional transformation rules. Therefore, we are currently developing a rule-based query optimizer that is able to integrate a new continuous query into the running query graph, while sharing preferably large subgraphs. This is achieved by heuristically choosing from a set of snapshot-equivalent query plans the best one according to a cost model.

Demo

We have developed an online version of our demo of PIPES at SIGMOD 2004. This demo shows how PIPES can be used to execute continuous queries in two completely different application domains, namely traffic management and online auctions. Both scenarios are plausible as they are similar or rely on presently developed benchmarks: Linear Road Benchmark NEXMark Benchmark Running the demo requires Java Web Start. See our help file for additional information.

Please click here to start our demo of PIPES.

XXL-Viewer

The XXL-Viewer offers an intuitive way of visual Java programming. We already presented this powerful tool at the SIGMOD conference 2004. Feel free to start our online version. In order to become familiar with the XXL-Viewer, read our tutorial (soon also available in english) that describes the basic steps. Since our library XXL is completely developed in Java, the XXL-Viewer provides an easy access to the functionality of XXL. Just add xxl.jar to the classpath by calling "Add jar" in the explorer of the XXL-Viewer and you can explore XXL. In order to get familiar with the XXL-Viewer, examine a simple awt example by opening this file with the XXL-Viewer. A more complex example modeling a continuous query over traffic data is illustrated here. Note that running the XXL-Viewer requires Java Web Start.

Publications

2007

• Christoph Heinz, Bernhard Seeger:
  Adaptive Wavelet Density Estimators over Data Streams,
  to appear in Proc. of SSDBM, Banff, Canada, July 2007
• Michael Cammert, Christoph Heinz, Jürgen Krämer, Bernhard Seeger, Sonny Vaupel, Udo Wolske:
  Flexible Multi-Threaded Scheduling for Continuous Queries over Data Streams,
  to appear in Proc. of First International Workshop on Scalable Stream Processing Systems, Istanbul, Turkey, April 2007.
• Michael Cammert, Jürgen Krämer, Bernhard Seeger:
  Dynamic Metadata Management for Scalable Stream Processing Systems,
  to appear in Proc. of First International Workshop on Scalable Stream Processing Systems, Istanbul, Turkey, April 2007.

2006

• Christoph Heinz, Bernhard Seeger:
  Towards Kernel Density Estimation over Streaming Data,
  In Proc. of COMAD, Delhi, India, December 2006
• Christoph Heinz, Bernhard Seeger:
  Stream Mining via Density Estimators: A concrete Application,
  In Proc. of COMAD, Delhi, India, December 2006
• Yin Yang, Jürgen Krämer, Dimitris Papadias, Bernhard Seeger:
  HybMig: A Hybrid Approach to Dynamic Plan Migration for Continuous Queries,
  IEEE Transactions on Knowledge and Data Engineering (TKDE), to appear.
• Christoph Heinz, Bernhard Seeger:
  Resource-Aware Kernel Density Estimators over Streaming Data,
  In Proc. of CIKM, Arlington, Virginia, USA, November 2006; Technical Report No. 50, Department of Mathematics and Computer Science, University of Marburg, 2006
• Jürgen Krämer, Bernhard Seeger, Thomas Penzel, Richard Lenz:
  PIPESmed: Ein flexibles Werkzeug zur Verarbeitung kontinuierlicher Datenströme in der Medizin,
  In 51. Jahrestagung der Deutschen Gesellschaft für Medizinische Informatik, Biometrie und Epidemiologie (GMDS), 2006.
• Christoph Heinz, Bernhard Seeger:
  Statistical Modeling of Sensor Data and its Application to Outlier Detection,
  Technical Report 2006/07, University of Stuttgart; 5. GI/ITG KuVS Fachgespräch "Drahtlose Sensornetze", Stuttgart, July 2006
• Christoph Heinz, Bernhard Seeger:
  Exploring Data Streams with Nonparametric Estimators,
  In Proc. of SSDBM, Vienna, Austria, July 2006
• Michael Cammert, Jürgen Krämer, Bernhard Seeger, Sonny Vaupel:
  A Cost Model for Adaptive Resource Management in Data Stream Systems,
  Technical Report No. 52, Department of Mathematics and Computer Science, University of Marburg, 2006.
• Jürgen Krämer, Yin Yang, Michael Cammert, Bernhard Seeger, Dimitris Papadias:
  Dynamic Plan Migration for Snapshot-Equivalent Continuous Queries in Data Stream Systems ,
  In Proc. of the International Conference on Semantics of a Networked World (ICSNW), March 2006, Munich, Germany.
• Michael Cammert, Jürgen Krämer, Bernhard Seeger, Sonny Vaupel:
  An Approach to Adaptive Memory Management in Data Stream Systems,
  Technical Report No. 49, Department of Mathematics and Computer Science, University of Marburg, 2005.
  In Proc. of the ICDE 2006, April 2006.
• Michael Cammert, Christoph Heinz, Jürgen Krämer, Tobias Riemenschneider, Maxim Schwarzkopf, Bernhard Seeger, Alexander Zeiss:
  Stream Processing in Production-to-Business Software,
  In Proc. of the ICDE 2006 (demonstration), April 2006.

2005

• Sonny Vaupel:
  Zeitfensterskalierung zur adaptiven Speicherverwaltung in Datenstrommanagementsystemen,
  BTW Studierendenprogramm 2005, Karlsruhe - Germany, March, 1.
• Michael Cammert, Christoph Heinz, Jürgen Krämer, Bernhard Seeger:
  Sortierbasierte Joins über Datenströmen,
  Technical Report No. 42, Department of Mathematics and Computer Science, University of Marburg, 2004, BTW 2005, Karlsruhe - Germany, March, 2-4.
• Björn Blohsfeld, Christoph Heinz, Bernhard Seeger:
  Maintaining Nonparametric Estimators over Data Streams,
  Technical Report No. 39, Department of Mathematics and Computer Science, University of Marburg, August 2004, BTW 2005, Karlsruhe - Germany, March, 2-4.
• Christoph Heinz, Bernhard Seeger:
  Wavelet Density Estimators over Data Streams (Extended Abstract),
  ACM Symposium on Applied Computing, Santa Fe - New Mexico, 2005.
• Jürgen Krämer, Bernhard Seeger:
  A Temporal Foundation for Continuous Queries over Data Streams,
  Technical Report, No. 38, Department of Mathematics and Computer Science, University of Marburg, July 2004.
  11th International Conference on Management of Data (COMAD), January 6-8, Goa - India.

2004

• Jürgen Krämer, Bernhard Seeger:
  A Temporal Foundation for Continuous Queries over Data Streams (Extended Version) ,
  Technical Report, No. 45, Department of Mathematics and Computer Science, University of Marburg, September 2004.
• Christoph Heinz, Bernhard Seeger:
  Adaptive Wavelet Density Estimators over Data Streams (revised version),
  Technical Report No. 43, Department of Mathematics and Computer Science, University of Marburg, 2004.
• Bernhard Seeger:
  Datenströme - Kurz erklärt. Datenbank-Spektrum 9: 30-33 (2004)
• Michael Cammert, Christoph Heinz, Jürgen Krämer, Bernhard Seeger:
  Anfrageverarbeitung auf Datenströmen,
  Datenbank-Spektrum 11: 5-13, (2004).
• Jürgen Krämer, Bernhard Seeger:
  PIPES–A Public Infrastructure for Processing and Exploring Data Streams.
  Proc. SIGMOD 2004 (Demo), submitted version.
  

2003

• Michael Cammert, Christoph Heinz, Jürgen Krämer, Martin Schneider, Bernhard Seeger:
  A Status Report on XXL - A Software Infrastructure for Efficient Query Processing.
  Data Engineering Bulletin 26(2): 12-18 (2003)
  
• Michael Cammert, Christoph Heinz, Jürgen Krämer, Bernhard Seeger:
  Datenströme im Kontext des Verkehrsmanagements.
  Workshop des GI-Arbeitskreises Mobile Datenbanken und Informationssysteme, Zürich, 2003.
• Michael Cammert, Christoph Heinz, Jürgen Krämer, Alexander Markowetz, Bernhard Seeger:
  PIPES: A Multi-Threaded Publish-Subscribe Architecture for Continuous Queries over Streaming Data Sources.
  Technischer Bericht 32, Fachbereich Mathematik und Informatik, Universität Marburg, 2003.
  

Acknowledgements