无须附加空间的数据立方体联机聚集
作者:
基金项目:

Supported by the Key Technology R&D Programe Foundation of China under Grant No.2002BA407B01-2 (国家科技攻关计划); the Special Science Foundation of Beijing Jiaotong University of China under Grant No.2003SZ003 (北京交通大学科技专项基金)


Online Aggregation on Data Cubes Without Auxiliary Information
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [13]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    以往在数据立方体上实现的联机聚集往往需要附加空间来存储联机聚集估算所需要的信息,极大地影响了数据立方体的存储和维护性能.提出了基于QC-Tree的用于范围查询处理的联机聚集PE(progressively estimate)算法以及它与简单聚集算法相结合的混合聚集算法HPE(hybrid progressively estimate);还提出了一种能够同时处理多个范围查询的联机聚集算法MPE(multiple progressively estimate).与以往联机聚集算法不同,这些算法不需要任何附加空间,而是利用QC-Tree自身保存的聚集数据和语义关系来估算聚集结果.由于QC-Tree是一种极为高效的数据立方体存储结构,因此能够以较理想的性能实现数据立方体上的联机聚集.对算法的分析和实验结果表明,所提出的算法具有较好的性能.

    Abstract:

    Typically, online aggregation algorithms on multi-dimensional data need additional auxiliary data for estimation, which make the performance of the storage and maintenance of the data cube worse. This paper presents the PE (progressively estimate) and HPE (hybrid progressively estimate) to progressively estimate the answers for range queries in the QC-Trees. MPE (multiple progressively estimate) is also proposed to simultaneously evaluate batches of range-sum queries. The difference between the algorithms and other online aggregation algorithms on data cubes is that these algorithms do not need any auxiliary information. The idea of this estimation method is to utilize the data stored in the QC-Tree itself. As a result, this algorithm will not deteriorate the performance of the storage and maintenance of the data cubes. Analysis and experimental results show that the algorithms provide an accurate estimation in far less time than the normal algorithms.

    参考文献
    [1]Lakshmanan LV,Pei J,Zhao Y.QC-Trees:An efficient summary structure for semantic OLAP.In:Halevy AY,ed.Proc.of the 2003 ACM SIGMOD Int'l Conf.on Management of Data.San Diego:ACM,2003.64-75.
    [2]Hahn CJ,Warren SG,London J.Edited synoptic cloud reports from ships and land stations over the globe,1982-1991.1996.http://cdiac.est.ornl.gov/ftp/ndp026b/SEP85L.Z
    [3]Hellerstein JM,Haas PJ,Wang HJ.Online aggregation.In:Peckham J,ed.Proc.of the 1997 ACM SIGMOD Int'l Conf.on Management of Data.Tucson:ACM Press,1997.171-182.
    [4]Wang W,Lu HJ,Feng JL,Yu JX.Condensed cube:An efficient approach to reducing data cube size.In:Proc.of the 18th Int'l Conf.on Data Engineering.San Jose:IEEE Computer Society,2002.155-165.
    [5]Sismanis Y,Deligiannakis A,Roussopoulos N,Kotidis Y.Dwarf:Shrinking the PetaCube.In:Franklin MJ,Moon B,Ailamaki A,eds.Proc.of the 2002 ACM SIGMOD Int'l Conf.on Management of Data.Madison:ACM Press,2002.464-475.
    [6]Lakshmanan LV,Pei J,Han JW.Quotient cube:How to summarize the semantics of a data cubes.In:Bressan S,Chaudhri A,Lee ML,Yu JX,Lacroix Z,eds.Proc.of the 28th Int'l Conf.on Very Large Data Bases.Hong Kong:Springer-Verlag,2002.778-789.
    [7]Ho CT,Agrawal R,Megiddo N,Srikant R.Range queries in OLAP data cubes.In:Peckham J,ed.Proc.of the ACM SIGMOD Int'l Conf.on Management of Data.Tucson:ACM Press,1997.73-88.
    [8]Poon CK.Dynamic orthogonal range queries in OLAP.Theoretical Computer Science,2003,296(3):487-510.
    [9]Acharya S,Gibbons PB,Poosala V,Ramaswamy S.The aqua approximate query answering system.In:Delis L,Faloutsos C,Ghandeharizadeh S,eds.Proc.of the 1999 ACM SIGMOD Int'l Conf.on Management of Data.Philadelphia:ACM Press,1999.574-576.
    [10]Chakrabarti K,Garofalakis MN,Rastogi R,Shim K.Approximate query processing using wavelets.The VLDB Journal,2001,10(2-3):199-223.
    [11]Lazaridis I,Mehrotra S.Progressive approximate aggregate queries with a multi-resolution tree structure.In:Aref WG,ed.Proc.of the 2001 ACM SIGMOD Int'l Conf.on Management of Data.Santa Barbara:ACM Press,2001.401-412.
    [12]Riedewald M,Agrawal D,Abbadi AE.pCube:Update-Efficient online aggregation with progressive feedback and error bounds.In:Gunther O,Lenz HJ,eds.Proc.of the 12th Int'l Conf.on Scientific and Statistical Database Management.Berlin:IEEE Computer Society,2000.95-108.
    [13]Schmidt RR,Shahabi C.How to evaluate multiple range-sum queries progressively.In:Popa L,ed.Proc.of the 21st ACM SIGACT-SIGMOD-SIGART Symp.on Principles of Database Systems.Madison:ACM Press,2002.133-141.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

李红松,黄厚宽.无须附加空间的数据立方体联机聚集.软件学报,2006,17(4):806-813

复制
分享
文章指标
  • 点击次数:4007
  • 下载次数: 4939
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2005-03-30
  • 最后修改日期:2005-10-10
文章二维码
您是第19763182位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号