计算机科学与探索 ›› 2012, Vol. 6 ›› Issue (9): 797-809.DOI: 10.3778/j.issn.1673-9418.2012.09.004

• 学术研究 • 上一篇    下一篇

在线图处理:面向信息网络的在线分析处理

徐洪宇1,2,李  川1,2+,唐常杰1,2,李洋涛1,2,代术成1,2,杨  宁1,2   

  1. 1. 四川大学 计算机学院,成都 610065
    2. 国家空管自动化系统技术重点实验室,成都 610065
  • 出版日期:2012-09-01 发布日期:2012-09-03

On-Line Graphic Processing: Information Network Oriented On-Line Analytical Processing

XU Hongyu1,2,  LI Chuan1,2+,  TANG Changjie1,2,  LI Yangtao1,2,  DAI Shucheng1,2,  YANG Ning1,2   

  1. 1. College of Computer Science, Sichuan University, Chengdu 610065, China
    2. National Key Laboratory of Air Control Automation System Technology, Chengdu 610065, China
  • Online:2012-09-01 Published:2012-09-03

摘要: 对信息网络数据集进行面向主题、多维、多层次的在线分析处理(on-line analytical processing,OLAP)面临数据规模爆炸,问题复杂性剧增等技术难题,传统OLAP技术不再适用。提出了面向信息网络的在线图处理(on-line graphic processing,OLGP)模型,OLGP包含节点集合、边集合、信息维集合,每个节点包含拓扑维集合;设计并实现了OLGP模型的核心操作(信息维上卷、拓扑维上卷、异步上卷)算法。对含有17 431位作者的12 499篇ACM论文的真实合作者网络数据集进行了相关分析处理,结果表明,信息维上卷仅需要113 ms,拓扑维上卷仅需要61 ms。

关键词: 信息网络, 信息网络数据立方, 信息网络基方体, 在线图处理(OLGP), 异步上卷

Abstract: There remain some technical problems, such as data size explosion, dramatic increase in the complexity of problems, when dealing with subject-oriented, multi-dimensional and multi-layer on-line analytical processing (OLAP) of the information network dataset. Thus traditional OLAP technology and tools are no longer applicable. This paper proposes the on-line graphic processing (OLGP) model based on the information network dataset. The OLGP includes node set, edge set and informational dimension set, and node set includes topological dimension set. Then, the paper designs and implements the?core operating?algorithm?of?the?OLGP which includes informational dimension roll-up, topological dimension roll-up and asynchronous roll-up. Experimental results?show?that the algorithm costs only 113 ms on informational roll-up and only 61 ms on topological roll-up to analyze and process a real collaboration network dataset of 17,431 authors and 12,499 papers.

Key words: information network (InfoNetwork), InfoNetCube, InfoNetBaseCube, on-line graphic processing (OLGP), asynchronous roll-up