With the rapid growth of uncertain data available in many real life applications, a probabilistic skyline query, namely P-skyline query, has been developed and received widespread concern. However, the P-skyline query usually reports results, which have dominant relationship. This contradicts with the incomparable property of skyline queries. Motivated by this, we extend the P-skyline query and formulate an EP-skyline (EPS) query. Thereafter, to develop the processing performance of EPS query, we utilize an index, PR-tree, to organize uncertain datasets and employ efficient pruning strategies to reduce the search space. Moreover, an effective algorithm is developed for the EPS query. Extensive experiments verify that our EPS query could always return better query results than P-skyline query with much less CPU cost, I/O cost and memory cost.
AggarwalC.C. and YuP.S., A survey of uncertain data algorithms and applications, Knowledge and Data Engineering, IEEE Transactions on21(5) (2009), 609–623.
2.
LeeM.K. Y.W. and LeeK.Y., Efficient processing of multiple continuous skyline queries over a data stream, Information Sciences221(2) (2013), 316–337.
3.
TongY., ChenL., ChengY. and YuP.S., Mining frequent itemsets over uncertain databases, Proceedings of the VLDB Endowment5(11) (2012), 1650–1661.
4.
WangY., LiX., LiX. and WangY., A survey of queries over uncertain data, Knowledge and Information Systems37(3) (2013), 485–530.
5.
YongH., LeeJ., KimJ. and HwangS.-W., Skyline ranking for uncertain databases, Information Sciences273 (2014), 247–262.
6.
ZhangY., LinX., TaoY., ZhangW. and WangH., Efficient computation of range aggregates against uncertain location-based queries, Knowledge and Data Engineering, IEEE Transactions on24(7) (2012), 1244–1258.
7.
PeiJ., JiangB., LinX. and YuanY., Probabilistic skylines on uncertain data, in Proceedings of the 33rd International Conference on Very Large Data Bases, VLDB Endowment, 2007, pp. 15–26.
8.
AtallahM.J. and QiY., Computing all skyline probabilities for uncertain data, in Proceedings of the Twenty-Eighth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, ACM, 2009, pp. 279–287.
9.
DingX. and JinH., Efficient and progressive algorithms for distributed skyline queries over uncertain data, Knowledge and Data Engineering, IEEE Transactions on24(8) (2012), 1448–1462.
10.
LianX. and ChenL., Efficient processing of probabilistic group subspace skyline queries in uncertain databases, Information Systems38(3) (2013), 265–285.
11.
LianX. and ChenL., Reverse skyline search in uncertain databases, ACM Transactions on Database Systems (TODS)35(1) (2010), 3–.
12.
ZhangW., LinX., ZhangY., WangW., ZhuG. and XuJ., Yu, Probabilistic skyline operator over sliding windows, Information Systems38(8) (2013), 1212–1233.
13.
LiuX., YangD.-N., YeM. and LeeW.-C., U-skyline: A new skyline query for uncertain databases, Knowledge and Data Engineering, IEEE Transactions on25(4) (2013), 945–960.
14.
YiuM.L., MamoulisN., DaiX., TaoY. and VaitisM., Efficient evaluation of probabilistic advanced spatial queries on existentially uncertain data, Knowledge and Data Engineering, IEEE Transactions on21(1) (2009), 108–122.
15.
DaiX., YiuM.L., MamoulisN., TaoY. and VaitisM., Probabilistic spatial queries on existentially uncertain data, in Advances in Spatial and Temporal Databases, Springer, 2005, pp. 400–417.
16.
GaoY., LiuQ., ZhengB. and ChenG., On efficient reverse skyline query processing, Expert Systems with Applications41(7) (2014), 3237–3249.
17.
JiangT., GaoY., ZhangB., LinD. and LiQ., Monochromatic and bichromatic mutual skyline queries, Expert Systems with Applications41(4) (2014), 1885–1900.
18.
ZhangS., MamoulisN. and CheungD.W., Scalable skyline computation using object-based space partitioning, in Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, ACM, 2009, pp. 483–494.
19.
ZhuL., TaoY. and ZhouS., Distributed skyline retrieval with low bandwidth consumption, Knowledge and Data Engineering, IEEE Transactions on21(3) (2009), 384–400.
20.
FuhryD., JinR. and ZhangD., Efficient skyline computation in metric space, in Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, ACM, 2009, pp. 1042–1051.
21.
Yunjun GaoB.Z.L.M.G.C.Q.L. and LiuQ., On processing reverse k-skyband and ranked reverse skyline queries ąî ąîąî, Information Sciences (2015), p. 11ĺC34.
22.
TaoY., XiaoX. and PeiJ., Efficient skyline and top-k retrieval in subspaces, Knowledge and Data Engineering, IEEE Transactions on19(8) (2007), 1072–1088.
23.
ImH. and ParkS., Group skyline computation, Information Sciences188 (2012), 151–169.
24.
HanX., LiJ., YangD. and WangJ., Efficient skyline computation on big data, Knowledge and Data Engineering, IEEE Transactions on25(11) (2013), 2521–2535.
25.
Xiaofeng DingL.C.H.J. and LianX, Continuous monitoring of skylines over uncertain data streams, Information Sciences184(1) (2012), 196–214.
26.
ZhouX., LiK.L., ZhouY.T. and LiK.Q., Adaptive processing for distributed skyline queries over uncertain data, IEEE Trans on Knowledge and Data Engineering2015. DOI.10.1109/TKDE.2015.2475764
27.
XiaZ., WangX., SunX. and WangQ., A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data, IEEE Transactions on Parallel and Distributed Systems. doi: 10.1109/TPDS.2015.2401003
28.
XiaoG.Q., LiK.L., LiK.Q. and ZhouX., Efficient top-range query processing for uncertain data based on multicore architectures, Distributed and Parallel Databases33(3) (2015), 381–413.
29.
TangZ., ZhouJ., LiK. and LiR., A mapreduce task scheduling algorithm for deadline constraints, Cluster Computing16(4) (2013), 651–662.
30.
TangZ., LiuM., AmmarA., LiK. and LiK., An optimized mapreduce workflow scheduling algorithm for heterogeneous computing, The Journal of Supercomputing (2014), 1–21.
31.
TangZ., JiangL., YangL., LiK. and LiK., Crfs based parallel biomedical named entity recognition algorithm employing mapreduce framework, Cluster Computing18(2) (2015), 493–505.
