Parallelizing uncertain skyline computation against n‐of‐N data streaming model. (6th November 2018)

• Record Type: Journal Article
• Authors: Liu, Jun; Li, Xiaoyong; Ren, Kaijun; Song, Junqiang
• Is Part Of: Concurrency and computation. Volume 31:Number 4(2019)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2018-11-06
• Subjects: data streams -- n‐of‐N model -- parallel queries -- skyline queries -- uncertain data; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.4848
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: The skyline query over uncertain data streams, as an important aspect of big data analysis, plays a significant role in domains such as environment monitoring, decision‐making, and data mining. The skyline query over uncertain data streams with sliding window model always focuses on the most recent N streaming items, which cannot meet the query requirements of different window scales at the same time. To improve the query flexibility and efficiency, we propose an efficient parallel method for processing uncertain n ‐of‐ N skyline queries; that is, computing the skyline for the most recent n (∀ n ≤ N ) items in parallel. Specifically, we first propose a framework for parallelizing the query computation for uncertain n ‐of‐ N skylines. Furthermore, we put forward a sliding window partitioning strategy as well as a streaming items mapping strategy to realize the load balance for each node. In addition, we define a spatial index structure R S T based on R ‐tree to organize the elements within each individual sliding window and candidate set in each which can significantly improve the dominance tests. Most importantly, we provide an encoding interval scheme to transform the n ‐of‐ N query into stabbing query in each compute node, which can greatly minimize the query scope and improve the query efficiency. In addition, we use a red‐black tree named R B I to store all stabbing intervals. Extensive experimental results demonstrate that the proposals are efficient and can greatly meet the query requirement of users in real applications.