论文部分内容阅读
本文针对ScopeOLAP系统中格的产生算法和实例化视图选择算法的不足之处加以改进和优化，使其更加实用。ScopeOLAP系统中的格产生算法递归调用程序，时间复杂度很大。为改善其性能，本文采用两集合法来实现，实际上就是借助一个队列采用宽度优先化递归为非递归，第二个集合主要是用来存储结果节点编号，以便于后面查找它对应的节点。ScopeOLAP系统中的实例化视图选择算法采用简单贪心算法，它的主要缺点是计算复杂性过高，即针对规模较大的问题而言，计算时间太长。每次选入一个视图之前，都要重新计算所有尚未入选的视图的单位收益，从中选出最好的那个，这样做保证了结果的质量，但缺陷是算法复杂度太高。本文利用实例化收益的单调性对简单贪心算法进行改进，使其在结果精度不变的情况下复杂度大大降低。