一种新的优化串行直方图构造算法  

A New Algorithm of Constructing Optimal Serial Histograms

作　　者：严君达[1] 王于同[1] 

机构地区：[1]杭州电子工业学院,浙江杭州310037

出　　处：《计算机工程与科学》2003年第6期70-73,共4页Computer Engineering & Science

摘　　要：串行直方图是基于频度排列对关系进行优化分区构造而成的,其连接结果大小估计是最优的,并可用于等值和范围查询结果大小估计。但是,串行直方图的构造算法复杂,影响了实际应用。本文从实用的角度出发,设计了一种构造优化串行直方图的算法BOS,该算法的时间复杂度大大降低,且估计精度接近最优直方图,从而使其具有较高的实用价值。A serial histogram is constructed based on relation frequencies and its join query size estimation is optimal, but its complex algorithm prevents it from application to practical estimations. Here we assume a new algorithm named BOS to solve this problem, and presents both theoretical and experimental results on the new algorithm.

关 键 词：串行直方图 构造算法 优化 频度排列 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]