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

    Skyband queries are very important for decision-making applications. To incorporate the Skyband operator into the database system, the problem of Skyband cardinality estimation must be solved, i.e., estimating the number of the Skyband elements returned by Skyband queries, which is very important for extending the query optimizer’s cost model to accommodate Skyband queries. This paper proposes a space and time efficient approach to estimate the Skyband cardinality, which is based on the generalized form of the Inclusion-Exclusion Principle. Experimental results show that the proposed approach can estimate the Skyband cardinality accurately.

    Reference
    [1] B?rzs?nyi S, Kossmann D, Stocker K. The Skyline operator. In: Proc. of the 17th Int’l Conf. on Data Engineering. Heidelberg: IEEE Computer Society, 2001. 421?430. http://www.informatik.uni-trier.de/~ley/db/conf/icde/icde2001.html
    [2] Papadias D, Tao YF, Fu G, Seeger B. Progressive Skyline computation in database systems. ACM Trans. on Database Systems, 2005,30(1):41?82. [doi: 10.1145/1061318.1061320]
    [3] Hjaltason GR, Samet H. Distance browsing in spatial databases. ACM Trans. on Database Systems, 1999,24(2):265?318. [doi: 10.1145/320248.320255]
    [4] Buchta C. On the average number of maxima in a set of vectors. Information Processing Letters, 1989,33(2):63?65. [doi: 10.1016/ 0020-0190(89)90156-7]
    [5] Markl V, Megiddo N, Kutsch M, Tran TM, Haas PJ, Srivastava U. Consistently estimating the selectivity of conjuncts of predicates. In: Proc. of the 31st Int’l Conf. on Very Large Data Bases. Trondheim: ACM, 2005. 373?384.
    [6] Rosen KH. Discrete Mathematics and Its Applications. 5th ed., Boston: McGraw-Hill, 2002.
    [7] 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?816.
    [8] Godfrey P, Shipley R, Gryz J. Maximal vector computation in large data sets. In: B?hm K, Jensen CS, Haas LM, Kersten ML, Larson P, Ooi BC, eds. Proc. of the 31st Int’l Conf. on Very Large Data Bases. Trondheim: ACM, 2005. 229?240.
    [9] Godfrey P, Shipley R, Gryz J. Algorithms and analyses for maximal vector computation. The VLDB Journal, 2007,16(1):5?28.
    [10] Tan KL, Eng PK, Ooi BC. Efficient progressive Skyline computation. In: Proc. of the 27th Int’l Conf. on Very Large Data Bases. Roma: Morgan Kaufmann Publishers, 2001. 301?310.
    [11] Eng PK, Ooi BC, Tan KL. Indexing for progressive skyline computation. Data & Knowledge Engineering, 2003,46(2):169?201. [doi: 10.1016/S0169-023X(02)00208-2]
    [12] Kossmann D, Ramsak F, Rost S. Shooting stars in the sky: An online algorithm for skyline queries. In: Bressan S, Chaudhri AB, Lee ML, Yu JX, Lacroix Z, eds. Proc. of the 28th Int’l Conf. on Very Large Data Bases. Hong Kong: Morgan Kaufmann Publishers, 2002. 275?286.
    [13] Papadias D, Tao YF, Fu G, Seeger B. An optimal and progressive algorithm for Skyline queries. In: Halevy Y, Ives ZG, Doan AH, eds. Proc. of the 2003 ACM SIGMOD Int’l Conf. on Management of Data. San Diego: ACM, 2003. 467?478.
    [14] Wei XJ, Yang J, Li CP, Chen H. Skyline query processing. Journal of Software, 2008,19(6):1386?1400 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/19/1386.htm [doi: 10.3724/SP.J.1001.2008.01386]
    [15] Bentley JL, Kung HT, Schkolnick M, Thompson CD. On the average number of maxima in a set of vectors and applications. Journal of the ACM, 1978,25(4):536?543. [doi: 10.1145/322092.322095]
    [16] Godfrey P. Skyline cardinality for relational processing. In: Seipel D, Torres JMT, eds. Proc. of the 3rd Int’l Symp. on Foundations of Information and Knowledge Systems. Wilhelminenburg Castle: Springer-Verlag, 2004. 78?97.
    [17] Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. 2nd ed., Cambridge: MIT Press, 2001.
    附中文参考文献: [14] 魏小娟,杨婧,李翠平,陈红.Skyline查询处理.软件学报,2008,19(6):1386?1400. http://www.jos.org.cn/1000-9825/19/1386.htm [doi: 10.3724/SP.J.1001.2008.01386]
    Cited by
Get Citation

赵加奎,杨冬青,陈立军.基于容斥原理的Skyband基数估计方法.软件学报,2010,21(7):1550-1560

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:September 16,2008
  • Revised:March 31,2009
You are the firstVisitors
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