Continuous skyline queries on multicore architectures. (19th May 2016)

• Record Type: Journal Article
• Authors: De Matteis, Tiziano; Di Girolamo, Salvatore; Mencagli, Gabriele
• Other Names: Notare Mirela Sechi Moretti Annoni guestEditor.; Lengauer Christian guestEditor.; Bougé Luc guestEditor.; Träff Jesper Larsson guestEditor.
• Is Part Of: Concurrency and computation. Volume 28:Number 12(2016)
• Page Start: 3503
• Page End: 3522
• Publication Date: 2016-05-19
• Subjects: data stream processing -- skyline queries -- sliding windows -- multicore programming; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.3866
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: The emergence of real‐time decision‐making applications in domains like high‐frequency trading, emergency management, and service level analysis in communication networks has led to the definition of new classes of queries. Skyline queries are a notable example. Their results consist of all the tuples whose attribute vector is not dominated (in the Pareto sense) by one of any other tuple. Because of their popularity, skyline queries have been studied in terms of both sequential algorithms and parallel implementations for multiprocessors and clusters. Within the Data Stream Processing paradigm, traditional database queries on static relations have been revised in order to operate on continuous data streams. Most of the past papers propose sequential algorithms for continuous skyline queries, whereas there exist very few works targeting implementations on parallel machines. This paper contributes to fill this gap by proposing a parallel implementation for multicore architectures. We propose (i) a parallelization of the eager algorithm based on the notion of Skyline Influence Time, (ii) optimizations of the reduce phase and load‐balancing strategies to achieve near‐optimal speedup, and (iii) a set of experiments with both synthetic benchmarks and a real dataset in order to show our implementation effectiveness. Copyright © 2016 John Wiley & Sons, Ltd.