Efficient processing of skyline queries has been an area of growing interest. Many of the earlier skyline techniques assumed that the skyline query is applied to a single data table. Naturally, these algorithms were not suitable for many applications in which the skyline query may involve attributes belonging to multiple data sources. In other words, if the data used in the skyline query are stored in multiple tables, then join operations would be required before the skyline can be searched. The task of computing skylines on multiple data sources has been coined as the skyline-join problem and various skyline-join algorithms have been proposed. However, the current proposals suffer several drawbacks: they often need to scan the input tables exhaustively in order to obtain the set of skyline-join results; moreover, the pruning techniques employed to eliminate the tuples are largely based on expensive pairwise tuple-to-tuple comparisons. In this article, we aim to address these shortcomings by proposing two novel skyline-join algorithms, namely skyline-sensitive join (S 2 J) and symmetric skyline-sensitive join (S 3 J), to process skyline queries over two data sources. Our approaches compute the results using a novel layer/region pruning technique ( LR-pruning ) that prunes the join space in blocks as opposed to individual data points, thereby avoiding excessive pairwise point-to-point dominance checks. Furthermore, the S 3 J algorithm utilizes an early stopping condition in order to successfully compute the skyline results by accessing only a subset of the input tables. In addition to S 2 J and S 3 J, we also propose the S 2 J-M and S 3 J-M algorithms. These algorithms extend S 2 J's and S 3 J's two-way skyline-join ability to efficiently process skyline-join queries over more than two data sources. S 2 J-M and S 3 J-M leverage the extended concept of LR-pruning , called M -way LR-pruning , to compute multi-way skyline-joins in which more than two data sources are integrated during skyline processing. We report extensive experimental results that confirm the advantages of the proposed algorithms over state-of-the-art skyline-join techniques.

The problem of finding interesting tuples in a data set, more commonly known as the skyline problem, has been extensively studied in scenarios where the data is static. More recently, skyline research has moved towards data streaming environments, where tuples arrive/expire in a continuous manner. Several algorithms have been developed to track skyline changes over sliding windows; however, existing methods focus on skyline analysis in which all required skyline attributes belong to a single incoming data stream. This constraint renders current algorithms unsuitable for applications that require a real-time “join” operation to be carried out between multiple incoming data streams, arriving from different sources, before the skyline query can be answered. Based on this motivation, in this paper, we address the problem of computing skyline-window-join (SWJ) queries over pairs of data streams, considering sliding windows that take into account only the most recent tuples. In particular, we propose a Layered Skyline-window-Join (LSJ) operator that (a) partitions the overall process into processing layers and (b) maintains skyline-join results in an incremental manner by continuously monitoring the changes in all layers of the process. We combine the advantages of existing skyline methods (including those that efficiently maintain skyline results over a single stream, and those that compute the skyline of pairs of static data sets) to develop a novel iteration-fabric skyline-window-join processing structure. Using the iteration-fabric, LSJ eliminates redundant work across consecutive windows by leveraging shared data across all iteration layers of the windowed skyline-join processing. To the best of our knowledge, this is the first paper that addresses join-based skyline queries over sliding windows. Extensive experimental evaluations over real and simulated data show that LSJ provides large gains over naive extensions of existing schemes which are not designed to eliminate redundant work across multiple processing layers.

Efficient processing of skyline queries has been an area of growing interest over both static and stream environments. Most existing static and streaming techniques assume that the skyline query is applied to a single data source. Unfortunately, this is not true in many applications in which, due to the complexity of the schema, the skyline query may involve attributes belonging to multiple data sources. Recently, in the context of static environments, various hybrid skyline-join algorithms have been proposed. However, these algorithms suffer from several drawbacks: they often need to scan the data sources exhaustively in order to obtain the set of skyline-join results; moreover, the pruning techniques employed to eliminate the tuples are largely based on expensive pairwise tuple-to-tuple comparisons. On the other hand, most existing streaming methods focus on single stream skyline analysis, thus rendering these techniques unsuitable for applications that require a real-time "join" operation to be carried out before the skyline query can be answered. Based on these observations, we introduce and propose to demonstrate SkySuite: a framework of skyline-join operators that can be leveraged to efficiently process skyline-join queries over both static and stream environments. Among others, SkySuite includes (1) a novel Skyline-Sensitive Join (SSJ) operator that effectively processes skyline-join queries in static environments, and (2) a Layered Skyline-window-Join (LSJ) operator that incrementally maintains skyline-join results over stream environments.

Efficient processing of skyline queries has been an area of growing interest. Most existing techniques assume that the skyline query is applied to a single data table. Unfortunately, this is not true in many applications where, due to the complexity of the schema, the skyline query may involve attributes belonging to multiple tables. Recently, various hybrid skyline-join algorithms have been proposed. However, the current proposals suffer from several drawbacks: they often need to scan the input tables exhaustively in order to obtain the set of skyline-join results; moreover, the pruning techniques employed to eliminate the tuples are largely based on expensive pairwise tuple-to-tuple comparisons. In this paper, we aim to address these shortcomings by proposing two novel skyline-join algorithms, namely skyline-sensitive join (S 2J) and symmetric skyline-sensitive join (S 3J), to process skyline queries over multiple tables. Our approaches compute the results using a novel layer/region pruning technique (LR-pruning) that prunes the join space in blocks as opposed to individual data points, thereby avoiding excessive pairwise point-to-point dominance checks. Furthermore, the S 3J algorithm utilizes an early stopping condition in order to successfully compute the skyline results by accessing only a subset of the input tables. We report extensive experimental results that confirm the advantages of the proposed algorithms over the state-of-the-art skyline-join techniques.

The popularity of batch-oriented cluster architectures like Hadoop is on the rise. These batch-based systems successfully achieve high degrees of scalability by carefully allocating resources and leveraging opportunities to parallelize basic processing tasks. However, they are known to fall short in certain application domains such as large scale media analysis. In these applications, the utility of a given data element plays a vital role in a particular analysis task, and this utility most often depends on the way the data is collected or interpreted. However, existing batch data processing frameworks do not consider data utility in allocating resources, and hence fail to optimize for ranked/top-k query processing in which the user is interested in obtaining a relatively small subset of the best result instances. A naïve implementation of these operations on an existing system would need to enumerate more candidates than needed, before it can filter out the k best results. We note that such waste can be avoided by utilizing utility-aware task partitioning and resource allocation strategies that can prune unpromising objects from consideration. In this demonstration, we introduce RanKloud, an efficient and scalable utility-aware parallel processing system built for the analysis of large media datasets. RanKloud extends Hadoop's MapReduce paradigm to provide support for ranked query operations, such as k-nearest neighbor and k-closest pair search, skylines, skyline-joins, and top-k join processing.