Efficient probabilistic skyline computation against n-of-N data stream model

被引：2
|
作者：
机构：
[1] National Key Laboratory for Parallel and Distributed Processing, College of Computer, National University of Defense Technology
来源：
Yang, Y.-T. (ytyang@nudt.edu.cn) | 1600年 / Chinese Academy of Sciences卷 / 23期
关键词：
Continuous query; N-of-N model; Probabilistic data stream; Skyline; Sliding window;
D O I：
10.3724/SP.J.1001.2012.04050
中图分类号：
学科分类号：
摘要：
This paper studies the problem of computing q-skylines against probabilistic data streams. Compared with the existing methods, which only support the sliding window model, this method can support the more general n-of-N data stream model. This method of transforming q-skyline queries is used for the stabbing queries on an interval tree to support n-of-N model. The paper proposes an algorithm, named PnNM, to maintain the data structures, which is needed for supporting n-of-N model. The PnNM algorithm can efficiently handle the update of the candidate set of uncertain data objects and the updates of the intervals. An algorithm, named PnNCont, is also proposed to handle continuous q-skyline queries against n-of-N model. The theoretical analyses and extensive experiments demonstrate that this algorithms can be very efficient in handing q-skyline queries against probabilistic data streams under n-of-N model. © 2012 ISCAS.
引用
收藏
页码：550 / 564
页数：14
相关论文
共 18 条
  • [1] Borzsonyi S., Kossmann D., Stocker K., The skyline operator, Proc. of the 17th Int'l Conf. on Data Engineering, pp. 421-430, (2001)
  • [2] Chomicki J., Godfrey P., Gryz J., Liang D., Skyline with presorting, Proc. of the 19th Int'l Conf. on Data Engineering, pp. 717-719, (2003)
  • [3] Tan K.L., Eng P.K., Ooi B.C., Efficient progressive skyline computation, Proc. of the 27th Int'l Conf. on Very Large Data Bases (VLDB 2001), pp. 301-310, (2001)
  • [4] Kossmann D., Ramsak F., Rost S., Shooting stars in the sky: An online algorithm for skyline queries, Proc. of the 28th Int'l Conf. on Very Large Data Bases (VLDB 2002), pp. 275-286, (2002)
  • [5] Chan C.Y., Eng P.K., Tan K.L., Stratified computation of skylines with partially-ordered domains, Proc. of the 2005 ACM SIGMOD Int'l Conference on Management of Data (SIGMOD 2005), pp. 203-214, (2005)
  • [6] Balke W.T., Guntzer U., Zheng J.X., Efficient distributed skylining for Web information systems, Advances in Database Technology, Proc. of the 9th Int'l Conf. on Extending Database Technology (EDBT 2004), pp. 256-273, (2004)
  • [7] Huang Z.Y., Jensen C.S., Lu H., Ooi B.C., Skyline queries against mobile lightweight devices in MANETs, Proc. of the 22nd Int'l Conf. on Data Engineering (ICDE 2006), (2006)
  • [8] Tao Y.F., Papadias D., Maintaining sliding window skylines on data streams, IEEE Trans. on Knowledge and Data Engineering, 18, 3, pp. 377-391, (2006)
  • [9] Pei J., Jiang B., Lin X.M., Yuan Y.D., Probabilistic skylines on uncertain data, Proc. of the 33rd Int'l Conf. on Very Large Data Bases (VLDB 2007), pp. 15-26, (2007)
  • [10] Lin X.M., Lu H.J., Xu J., Yu J.X., Continuously maintaining quantile summaries of the most recent n elements over a data stream, Proc. of the 20th Int'l Conf. on Data Engineering (ICDE 2004), pp. 362-374, (2004)
12