Publications-Proceedings

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 Continuous probabilistic skyline queries over uncertain data streams
作者 Su, H.Z.;Wang, E.T.;Chen, Arbee L. P.
陳良弼
貢獻者 資科系
關鍵詞 Continuous data; Continuous queries; Data objects; Data stream; Dominance relation; New structures; Probabilistic skyline; Re-computing; Skyline query; Sliding Window; Uncertain data; Uncertain data streams; Uncertain datas; Algorithms; Data communication systems; Data structures; Experiments; Expert systems; Hydraulics; Probability; Problem solving; Query processing; Data mining
日期 2010
上傳時間 17-Apr-2015 17:20:22 (UTC+8)
摘要 Recently, some approaches of finding probabilistic skylines on uncertain data have been proposed. In these approaches, a data object is composed of instances, each associated with a probability. The probabilistic skyline is then defined as a set of non-dominated objects with probabilities exceeding or equaling a given threshold. In many applications, data are generated as a form of continuous data streams. Accordingly, we make the first attempt to study a problem of continuously returning probabilistic skylines over uncertain data streams in this paper. Moreover, the sliding window model over data streams is considered here. To avoid recomputing the probability of being not dominated for each uncertain object according to the instances contained in the current window, our main idea is to estimate the bounds of these probabilities for early determining which objects can be pruned or returned as results. We first propose a basic algorithm adapted from an existing approach of answering skyline queries on static and certain data, which updates these bounds by repeatedly processing instances of each object. Then, we design a novel data structure to keep dominance relation between some instances for rapidly tightening these bounds, and propose a progressive algorithm based on this new structure. Moreover, these two algorithms are also adapted to solve the problem of continuously maintaining top-k probabilistic skylines. Finally, a set of experiments are performed to evaluate these algorithms, and the experiment results reveal that the progressive algorithm much outperforms the basic one, directly demonstrating the effectiveness of our newly designed structure. © 2010 Springer-Verlag.
關聯 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
資料類型 conference
DOI http://dx.doi.org/10.1007/978-3-642-15364-8_8
dc.contributor 資科系
dc.creator (作者) Su, H.Z.;Wang, E.T.;Chen, Arbee L. P.
dc.creator (作者) 陳良弼zh_TW
dc.date (日期) 2010
dc.date.accessioned 17-Apr-2015 17:20:22 (UTC+8)-
dc.date.available 17-Apr-2015 17:20:22 (UTC+8)-
dc.date.issued (上傳時間) 17-Apr-2015 17:20:22 (UTC+8)-
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/74688-
dc.description.abstract (摘要) Recently, some approaches of finding probabilistic skylines on uncertain data have been proposed. In these approaches, a data object is composed of instances, each associated with a probability. The probabilistic skyline is then defined as a set of non-dominated objects with probabilities exceeding or equaling a given threshold. In many applications, data are generated as a form of continuous data streams. Accordingly, we make the first attempt to study a problem of continuously returning probabilistic skylines over uncertain data streams in this paper. Moreover, the sliding window model over data streams is considered here. To avoid recomputing the probability of being not dominated for each uncertain object according to the instances contained in the current window, our main idea is to estimate the bounds of these probabilities for early determining which objects can be pruned or returned as results. We first propose a basic algorithm adapted from an existing approach of answering skyline queries on static and certain data, which updates these bounds by repeatedly processing instances of each object. Then, we design a novel data structure to keep dominance relation between some instances for rapidly tightening these bounds, and propose a progressive algorithm based on this new structure. Moreover, these two algorithms are also adapted to solve the problem of continuously maintaining top-k probabilistic skylines. Finally, a set of experiments are performed to evaluate these algorithms, and the experiment results reveal that the progressive algorithm much outperforms the basic one, directly demonstrating the effectiveness of our newly designed structure. © 2010 Springer-Verlag.
dc.format.extent 176 bytes-
dc.format.mimetype text/html-
dc.relation (關聯) Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.subject (關鍵詞) Continuous data; Continuous queries; Data objects; Data stream; Dominance relation; New structures; Probabilistic skyline; Re-computing; Skyline query; Sliding Window; Uncertain data; Uncertain data streams; Uncertain datas; Algorithms; Data communication systems; Data structures; Experiments; Expert systems; Hydraulics; Probability; Problem solving; Query processing; Data mining
dc.title (題名) Continuous probabilistic skyline queries over uncertain data streams
dc.type (資料類型) conferenceen
dc.identifier.doi (DOI) 10.1007/978-3-642-15364-8_8
dc.doi.uri (DOI) http://dx.doi.org/10.1007/978-3-642-15364-8_8