Premium
Parallelizing uncertain skyline computation against n ‐of‐ N data streaming model
Author(s) -
Liu Jun,
Li Xiaoyong,
Ren Kaijun,
Song Junqiang
Publication year - 2018
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.4848
Subject(s) - skyline , computer science , sliding window protocol , online aggregation , query optimization , data stream mining , data mining , spatial query , set (abstract data type) , uncertain data , tree (set theory) , scalability , computation , window (computing) , web search query , web query classification , database , information retrieval , search engine , algorithm , mathematical analysis , mathematics , programming language , operating system
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.