Parallel continuous skyline query over high-dimensional data stream windows

Abstract

Real-time multi-criteria decision-making applications in fields like high-speed algorithmic trading, emergency response, and disaster management have driven the development of new types of preference queries. This is an example of a skyline search. Multi-criteria decision-making utilizes the skyline operator to extract highly significant tuples or useful data points from extensive sets of multi-dimensional databases. The user’s settings determine the results, which include all tuples whose attribute vector remains undefeated by another tuple. The extracted tuples are commonly known as the skyline set. Lately, there has been a growing trend in research studies to perform skyline queries on data stream applications. These queries consist of extracting desired records from sliding windows and removing outdated records from incoming data sets that do not meet user requirements. The datasets in these applications are extremely large and exhibit a wide range of dimensions that vary over time. Consequently, the skyline query is considered a computationally demanding task, with the challenge of achieving a real-time response within an acceptable duration. We must transport and process enormous quantities of data. Traditional skyline algorithms have faced new challenges due to limitations in data transmission bandwidth and latency. The transfer of vast quantities of data would affect performance, power efficiency, and reliability. Consequently, it is imperative to make alterations to the computer paradigm. Parallel skyline queries have attracted the attention of both scholars and the business sector. The study of skyline queries has focused on sequential algorithms and parallel implementations for multicore processors, primarily due to their widespread use. While previous research has focused on sequential algorithms, there is a limitation to comprehensive studies that specifically address modern parallel processors. While numerous articles have been published regarding the parallelization of regular skyline queries, there is a limited amount of research dedicated specifically to the parallel processing of continuous skyline queries. This study introduces PRSS, a continuous skyline technique for multicore processors specifically designed for sliding window-based data streams. The efficacy of the proposed parallel implementation is demonstrated through tests conducted on both real-world and synthetic datasets, encompassing various point distributions, arrival rates, and window widths. The experimental results for a dataset characterized by a large number of dimensions and cardinality demonstrate significant acceleration.