一种适应于动态环境范围查询的数据立方体

A Data Cube for Range Queries in Dynamic Environments

范围查询是对数据立方体进行数据分析的有效方法,预计算技术可以提高数据立方体范围查询的速度,实现快速的用户响应.近年来研究人员基于多维联机分析处理(MOLAP)预计算的研究主要以prefix sum及分块技术为基础,本文对分块方案及如何组织块内单元实施prefix sum方法进行探索,提出了前缀区域数据立方体结构(Prefix Region Cube,PRC),采用基于前缀区域的不规则的分块方案,这种分块方法利于从起始单元开始的前缀区域范围查询的实现.另外PRC在分块及对划分后的块内单元实施prefix sum时都采用回归分割技术,在不增加额外立方体空间的前提下,实现范围查询和数据更新的代价都为O(logdn).

Range query is a very effective method to analyze data in data cubes. Pre-computing can improve the speed of range query in data cube and result in non-interactive response times. The researchers on pre-computing on MOLAP （Multi-Dimensional On Line Analytical Processing） are mostly based on technology of partition and prefix sum recently. The partition scheme and how to organize cells and carry on prefix sum in partitions are probed on in this paper and the Prefix Region data Cube structure （PRC） is proposed. PRC partitions data cube into several irregular boxes in favor of pre-com- puting of prefix region. In addition the technology of recursive partition is used to partition data cube and organize cells of partitions to carry prefix sum in PRC. Both of the range query and update costs of PRC are O （log^dn） and not adding any space overhead compared to storing the original arrav.