Progressive and Approximate Join Algorithms on Data Streams

In this chapter, we discuss the design and implementation of join algorithms for data streaming systems, wherememory is often limited relative to the data that needs to be processed.We first focus on progressive join algorithms for various data models. We introduce a framework for progressive join processing, called the Result Rate based Progressive Join (RRPJ) framework which can be used for join processing for various data models, and discuss its various instantiations for processing relational, high-dimensional, spatial and XML data.

We then consider progressive and approximate join algorithms. The need for approximate join algorithms is motivated by the observation that users often do not require complete set of answers. Some answers, which we refer to as an approximate result, are often sufficient. Users expect the approximate result to be either the largest possible or the most representative (or both) given the resources available. We discuss the tradeoffs between maximizing quantity and quality of the approximate result. To address the different tradeoffs, we discuss a family of algorithms for progressive and approximate join processing.