数据方体系统设计中的优化问题

摘要

支持实时查询的联机分析处理系统的设计是当前一个很重要的研究问题.其中常用的方法是使用数据方体来实现.对于出现频率较高的查询,可以给出对应的数据方体集,使得每个查询都可以直接得到回答.但是在设计基于方体的系统时,需要考虑以下两个问题:(1)数据方体的维护成本,(2)回答频繁查询的响应时间.在用户给出了维护成本上限和响应时间上限后,需要对数据方体集进行优化,使得系统能够满足用户的要求,并回答尽可能多的查询.文章给出了数据方体系统设计优化问题的定义,这是一个NP完全问题,并提出了贪心删除和贪心合并的近似算法.实验表明了算法的有效性.