微信服务号

微信订阅号

2025年5月12日 19:35 星期一
首页 > 过刊浏览>2011年第22卷第2期 >258-268. DOI:10.3724/SP.J.1001.2011.03771
PDF HTML阅读 XML下载 导出引用 引用提醒
Graph OLAPing 的建模、设计与实现
作者:
基金项目:

国家自然科学基金(600773169); 国家科技支撑计划(2006BAI05A01); 高等学校博士学科点基金(20090181120064)


Modeling, Design and Implementation of Graph OLAPing
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [22]
    • |
  • 相似文献
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    提出了一系列Graph 的OLAP 模型和算法,实现了以Graph 数据为中心度量的OLAP 操作.主要贡献包括:(1) 提出了面向Graph 的数据仓库概念模型——双星模型;(2) 提出了Graph 的数据立方概念和创建过程;(3) 设计了信息维聚集算法I-OLAPing;(4) 设计了拓扑维聚集算法T-OLAPing;(5) 实现了Graph OLAP 的原型系统GraphOLAPer1.0.实验结果表明,设计和实现的Graph OLAPing 算法及原型系统Graph OLAPer1.0 能够有效地进行科研合作网分析.

    Abstract:

    This paper presents a series of models and algorithms to implement OLAPing on graph data. The major contributions include (1) proposing a graph-oriented data warehouse model, called a double star model, (2) proposing the concept of graph data cube and its building algorithm, (3) designing an informational OLAPing algorithm, I-OLAPing, (4) designing topological dimensional OLAPing algorithm, T-OLAPing, and (5) building a Graph OLAPing prototype, Graph OLAPer1.0, based on the proposed approaches. Experimental results show that the Graph OLAPing algorithms designed and implemented in this paper, together with Graph OLAPing prototype, Graph OLAPer1.0 can work effectively on Co-Author Networks.

    参考文献
    [1] Harinarayan V, Rajaraman A, Ullman JD. Implementing data cubes efficiently. In: Jagadish HV, ed. Proc. of the SIGMOD. New York: ACM, 1996. 205?216. [doi: 10.1145/233269.233333]
    [2] Gray J, Chaudhuri S, Bosworth A, Layman A, Reichart D, Venkatrao M, Pellow F, Pirahesh H. Data cube: A relational aggregation operator generalizing group-by, cross-by, cross-tab and sub-totals. In: Su SYW, ed. Proc. of the ICDE. New Orleans: IEEE Computer Society, 1996. 152?159. [doi: 10.1109/ICDE.1996. 492099]
    [3] Chaudhuri S, Dayal U. An overview of data warehousing and OLAP technology. SIGMOD Record, 1997,26(1):65?74. [doi: 10.1145/248603.248616]
    [4] Vassiliadis P, Sellis T. A survey of logical models for OLAP databases. SIGMOD Record, 1999,28(4):64?69. [doi: 10.1145/ 344816.344869]
    [5] Beyer KS, Ramakrishnan R. Bottom-Up computation of sparse and iceberg cubes. In: Delis A, Faloutsos C, Ghandeharizadeh S, eds. Proc. of the SIGMOD Conf. Philadelphia: ACM Press, 1999. 359?370. [doi: 10.1145/304182.304214]
    [6] Gupta A, Mumick IS. Materialized Views: Techniques, Implementations, and Applications. MIT Press, 1999.
    [7] Zhao YH, Deshpande PM, Naughton JF. An array-based algorithm for simultaneous multidimensional aggregates. In: Peckham J, ed. Proc. of the SIGMOD Conf. Tucson: ACM Press, 1997. 159?170. [doi: 10.1145/253260.253288]
    [8] Beyer KS, Ramakrishnan R. Bottom-Up computation of sparse and iceberg cubes. In: Delis A, Faloutsos C, Ghandeharizadeh S, eds. Proc. of the SIGMOD Conf. Philadelphia: ACM Press, 1999. 359?370. [doi: 10.1145/304182.304214]
    [9] Lu HP, Shi Y. Complexity of public transport networks. Tsinghua Science and Technology, 2007,12(2):204?213. [doi: 10.1016/ S1007-0214(07)70029-9]
    [10] Xu J, Chen H. Criminal network analysis and visualization: A data mining perspective. Communications of the ACM, 2005,48(6): 100?107. [doi: 10.1145/1064830.1064834]
    [11] Papadias D, Kalnis P, Zhang J, Tao Y. Efficient OLAP operations in spatial data warehouses. In: Jensen CS, Schneider M, Seeger B, Tsotras VJ, eds. Proc. of the 6th Int’l Symp. on Spatial and Temporal Databases. London: Springer-Verlag, 2001. 443?459.
    [12] Chakrabarti D, Faloutsos C. Graph mining: Laws, generators, and algorithms. ACM Computing Surveys, 2006,38:Article 2.
    [13] Tian Y, Hankins RA, Patel JM. Efficient aggregation for graph summarization. In: Lakshmanan LVS, ed. Proc. of the SIGMOD. New York: ACM, 2008. 567?580. [doi: 10.1145/1376616.1376675]
    [14] Raghavan S Garcia-Molina H. Representing Web graphs. In: Dayal U, Ramamritham K, Vijayaraman TM, eds. Proc. of the ICDE. Bangalore: IEEE Computer Society, 2003. 405?416. [doi: 10.1109/ICDE.2003. 1260809]
    [15] Boldi P, Vigna S. The WebGraph framework I: Compression techniques. In: Feldman SI, Uretsky M, Najork M, Wills CE, eds. Proc. of the WWW. New York: ACM, 2004. 595?602. [doi: 10.1145/ 988672.988752]
    [16] Wu AY, Garland M, Han J. Mining scale-free networks using geodesic clustering. In: Kim W, Kohavi R, Gehrke J, DuMouchel W, eds. Proc. of the KDD. Seattle: ACM, 2004. 719?724. [doi: 10.1145/1014052.1014146]
    [17] Archambault D, Munzner T, Auber D. Topolayout: Multilevel graph layout by topological features. IEEE Trans. on Visualization and Computer Graphics, 2007,13(2):305?317. [doi: 10.1109/TVCG.2007.46]
    [18] Navlakha S, Rastogi R, Shrivastava N. Graph summarization with bounded error. In: Wang JTL, ed. Proc. of the SIGMOD Conf. Vancouver: ACM, 2008. 419–432. [doi: 10.1145/1376616.1376661]
    [19] Ng AY, Jordan MI, Weiss Y. On spectral clustering: Analysis and an algorithm. In: Dietterich TG, Becker S, Ghahramani Z, eds. Proc. of the NIPS. Vancouver: MIT Press, 2001. 849?856.
    [20] Gibson D, Kumar R, Tomkins A. Discovering large dense subgraphs in massive graphs. In: B?hm K, Jensen CS, Haas LM, Kersten ML, Larson P?, Ooi BC, eds. Proc. of the VLDB. Trondheim: ACM, 2005. 721?732.
    [21] Herman I, Melancon G, Marshall MS. Graph visualization and navigation in information visualization: A survey. IEEE Trans. on Visualization and Computer Graphics, 2000,6(1):24?43.
    [22] Chen C, Yan XF, Zhu FD, Han JW, Yu PS. Graph OLAP: Towards online analytical processing on graphs. In: Proc. of the ICDM Conf. 2008. 103?112. [doi: 10.1109/ICDM.2008.30]
    相似文献
    引证文献
引用本文

李川,赵磊,唐常杰,陈瑜,李靓,赵小明,刘小玲. Graph OLAPing 的建模、设计与实现.软件学报,2011,22(2):258-268

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2009-07-29
  • 最后修改日期:2009-11-04
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号