论文部分内容阅读
随着当代计算机技术和信息技术的不断发展和应用,数据收集手段越来越多,数据存储量越来越大,如何从海量数据中排除一些不会被用户考虑的信息并找出用户最感兴趣的信息,从而为用户做出有效的决策服务,成为了一项重要的研究课题。轮廓查询就是从目标数据集中抽取不被其它任何数据对象支配的数据对象集合,其查询结果能够反映目标数据集的整体轮廓,有利于用户查询到自己感兴趣的目标。因为其在多目标决策、数据挖掘、数据库可视化等方面的潜在应用,近年来轮廓查询引起了越来越多研究者的关注。
近十年来国内外对轮廓查询及其相关问题进行了深入广泛的研究,对轮廓查询的研究大体可以分为五个方面:单表的轮廓查询,多表连接的轮廓查洵,轮廓子查询,不同数据类型上的轮廓查询以及轮廓查询的扩展。现有的对轮廓查询的研究大多集中在对单表关系模型的研究上,在特殊的数据模犁上的轮廓查询研究较少,比说星型模型。数据仓库中主要的模型是星型模犁,另外星型模型数据在数据流中也广泛存在。所以研究星型模型数据的轮廓查询算法,有着很人的应用价值。
在星型模型中的轮廓查询算法面临的问题主要有:(1)需要处理多表连接;(2)需要考虑连接中事实表和维度表的差别;(3)需要处理星型模型这种高维数据模型;(4)需要有针对星型模型的索引机制。传统的算法无法适应这些需求。
本文利用星型模型的特性设计其在不同的应用环境下的轮廓查询算法。在内存环境中,利用事实表中的外键信息将事实表分组,对分组方式的不同,将算法分为SNG、SVG和SDG算法。在外存环境下,利用维度表信息建立起SNTree和SNVTree索引树索引外存块,提出SNTreeIO和SNVTreeIO外存算法以减少轮廓查询中的I/O的次数。在数据流环境下,利用SNTree和SNVTree索引树索引实时数据,并利用SNTreeDS和SNVTreeDS算法计算出实时轮廓。实验表明,这些算法能很好的应用于具有不同数据特征的数据环境下,并且每个算法在其各自的数据结构上表现出较好的性能。