计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (17): 140-144.

• 数据库、信号与信息处理 • 上一篇    下一篇

一种高效流立方体结构

袁正午,程宇翔,梁均军,李 林   

  1. 重庆邮电大学 计算机科学与技术学院 中韩合作GIS研究所,重庆 400065
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-06-11 发布日期:2011-06-11

Effective data stream cube structure

YUAN Zhengwu,CHENG Yuxiang,LIANG Junjun,LI Lin   

  1. Sino-Korea Chongqing GIS Research Center,College of Computer Science & Technology,Chongqing University of Posts and Telecommunications,Chongqing 400065,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-06-11 Published:2011-06-11

摘要: 流立方体是一种通过H-tree结构实现的,通过H-cubing算法计算每个立方单元格的立方体结构。由于H-tree中的子节点是无序的,H-cubing算法的局限性导致其不能有效地进行数据流的查询和在线分析以及等高级操作。针对这一问题,提出一种新的基于ANH-tree的流立方体实现方法,该方法在H-tree的基础上,使用平衡二叉树索引无序节点并在相关节点直接建立链接来加快节点访问速度和立方单元格的计算速度,并在此基础上给出了与新结构对应的创建和查询算法,实验表明ANH-tree结构在CPU时间和内存空间等方面的性能远远优于H-tree。

关键词: 数据流, 流立方体, 在线分析处理, 基于平衡二叉及节点连接的多层次树(ANH-tree), 多层次树(H-tree)

Abstract: Stream cube is stored by H-tree and uses H-cubing to compute each cuboid.However,as it is expensive to construct data cube in OLAP,efficient data structure,query method and validated algorithms are urgently needed.Examining stream cube,as H-tree layout is disorderly and H-cubing efficiency is limited,the performance is affected.ANH-tree(based on H-tree and improved by AVL-tree and Node-links) is proposed to index nodes of each layer of tree structure by binary tree,which facilitates the retrieval operation in the construction,and links a node to its descendant,which facilitates the direct search cuboid about an ad-hoc query.Relevant algorithms have been designed and implemented.As a proof,the performance study validates the ideas with respect to the factors such as time and memory space usage.

Key words: data stream, stream cube, On-Line Analytical Processing(OLAP), AVL and Node links based Hyper-tree(ANH-tree), Hyper-tree(H-tree)