微信服务号

微信订阅号

2025-4-24- 19
Home > Archive>Volume 23, Issue 3, 2012 >550-564. DOI:10.3724/SP.J.1001.2012.04050
PDF HTML XML Export Cite reminder
Efficient Probabilistic Skyline Computation Against n-of-N Data Stream Model
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [18]
    • |
  • Related
    • | | |
  • Comments
    Abstract:

    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.

    Reference
    [1] Borzsonyi S, Kossmann D, Stocker K. The skyline operator. In: Ehrgott M, Greco S, Figueira J, eds. Proc. of the 17th Int’l Conf. on Data Engineering. Heidelberg: IEEE Computer Society, 2001. 421-430. [doi: 10.1109/ICDE.2001.914855]
    [2] Chomicki J, Godfrey P, Gryz J, Liang D. Skyline with presorting. In: Dayal U, Ramamritham K, Vijayaraman TM, eds. Proc. of the 19th Int’l Conf. on Data Engineering. Bangalore: IEEE Computer Society, 2003. 717-719. [doi: 10.1109/ICDE.2003.1260846]
    [3] Tan KL, Eng PK, Ooi BC. Efficient progressive skyline computation. In: Apers PMG, Atzeni P, Ceri S, Paraboschi S, Ramamohanarao K, Snodgrass RT, eds. Proc. of the 27th Int’l Conf. on Very Large Data Bases (VLDB 2001). Rome: Morgan Kaufmann Publishers, 2001. 301-310.
    [4] Kossmann D, Ramsak F, Rost S. Shooting stars in the sky: an online algorithm for skyline queries. In: Bernstein PA, Loannidis YE, Ramakrishnan R, eds. Proc. of the 28th Int’l Conf. on Very Large Data Bases (VLDB 2002). Hong Kong: Morgan Kaufmann Publishers, 2002. 275-286.
    [5] Chan CY, Eng PK, Tan KL. Stratified computation of skylines with partially-ordered domains. In: Ozcan F, ed. Proc. of the 2005 ACM SIGMOD Int’l Conference on Management of Data (SIGMOD 2005). Maryland: ACM Press, 2005. 203-214. [doi: 10.1145/ 1066157.1066181]
    [6] Balke WT, Güntzer U, Zheng JX. Efficient distributed skylining for Web information systems. In: Bertino E, Christodoulakis S, Plexousakis D, Christophides V, Koubarakis M, Bohm K, Ferrari E, eds. Advances in Database Technology, Proc. of the 9th Int’l Conf. on Extending Database Technology (EDBT 2004). Heraklion: Springer-Verlag, 2004. 256-273. [doi: 10.1007/978-3-540- 24741-8_16]
    [7] Huang ZY, Jensen CS, Lu H, Ooi BC. Skyline queries against mobile lightweight devices in MANETs. In: Liu L, Reuter A, Whang K, Zhang J, eds. Proc. of the 22nd Int’l Conf. on Data Engineering (ICDE 2006). Atlanta: IEEE Computer Society, 2006. 66. [doi: 10.1109/ICDE.2006.142]
    [8] Tao YF, Papadias D. Maintaining sliding window skylines on data streams. IEEE Trans. on Knowledge and Data Engineering, 2006, 18(3):377-391. [doi: 10.1109/TKDE.2006.48]
    [9] Pei J, Jiang B, Lin XM, Yuan YD. Probabilistic skylines on uncertain data. In: Koch C, Gehrke J, Garofalakis MN, Srivastava D, Aberer K, Deshpande A, Florescu D, Chan CY, Ganti V, Kanne C, Klas W, Neuhold EJ, eds. Proc. of the 33rd Int’l Conf. on Very Large Data Bases (VLDB 2007). Vienna: ACM Press, 2007. 15-26.
    [10] Lin XM, Lu HJ, Xu J, Yu J X. Continuously maintaining quantile summaries of the most recent n elements over a data stream. In: Proc. of the 20th Int’l Conf. on Data Engineering (ICDE 2004). Boston: IEEE Computer Society, 2004. 362-374.
    [11] Lin XM, Yuan YD, Wang W, Lu HJ. Stabbing the sky: Efficient skyline computation over sliding windows. In: Proc. of the 21st Int’l Conf. on Data Engineering (ICDE 2005). Tokyo: IEEE Computer Society, 2005. 502-513. [doi: 10.1109/ICDE.2005.137]
    [12] Zhang WJ, Lin XM, Zhang Y, Wang W, Yu JX. Probabilistic skyline operator over sliding windows. In: Proc. of the 25th Int’l Conf. on Data Engineering (ICDE 2009). Shanghai: IEEE Computer Society, 2009. 1060-1071. [doi: 10.1109/ICDE.2009.83]
    [13] Sun SL, Li JJ, Zhu YY. Efficient processing of continuous skyline query over distributed data streams. Journal of Software, 2009, 20(7):1839-1853 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3340.htm [doi: 10.3724/SP.J.1001.2009. 03340]
    [14] Tian L, Zou P, Li AP, Jia Y. Grid index based algorithm for continuous skyline computation. Chinese Journal of Computers, 2008, 31(6):998-1012 (in Chinese with English abstract).
    [15] Sun SL, Dai DB, Huang ZH, Zhang QX, Zhou LX. Algorithm on computing skyline over probabilistic data stream. Acta Electronica Sinica, 2009,37(2):285-293 (in Chinese with English abstract).
    [16] Beckmann N, Kriegel HP, Schneider R, Seeger B. The R*-tree: An efficient and robust access method for points and rectangles. In: Garcia-molina H, Jagadish HV, eds. Proc. of the ’90 ACM SIGMOD Int’l Conf. on Management of Data. Atlantic City: ACM Press, 1990. 322-311. [doi: 10.1145/93597.98741]
    [17] Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. 2nd ed., Cambridge: The MIT Press, 2001. 273-301.
    [18] de Berg M, Cheong O, vam Kreveld M, Overmars M. Computational Geometry: Algorithms and Applications. 3rd ed., Springer-Verlag, 2008. 220-225.
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

杨永滔,王意洁.n-of-N 数据流模型上高效概率Skyline 计算.软件学报,2012,23(3):550-564

Copy
Share
Article Metrics
  • Abstract:3966
  • PDF: 5613
  • HTML: 0
  • Cited by: 0
History
  • Received:February 10,2010
  • Revised:August 13,2010
  • Online: March 05,2012
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2038222Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063