导　　师： 闵华清

学科专业： H1203

授予学位： 硕士

作　　者： ;

机构地区： 华南理工大学

摘　　要： 随着信息化时代的到来，数据库技术不断发展，数据库中存储的数据量急剧增加，如何从海量数据中找出人们最感兴趣的信息，为人们做出有效的决策服务，成为了一项重要的研究课题。SKYLINE计算就是从一个数据库中抽取不被其它任何数据对象支配的数据对象集合。因为在多目标决策、数据挖掘、数据库可视化等方面的潜在应用，近年来SKYLINE计算引起了越来越多研究者的关注。
　　 随着空间维度的增长，不仅导致了SKYLINE点计算的难度增加，同时，当得到的SKYLINE点数量不断增长时，SKYLINE查询带来的价值也逐渐减少，对于用户作出决策无法提供准确、直观的依据。K-支配SKYLINE的出现目的就在于从高维数据空间中如何找出更具有意义的SKYLINE。本文在研究了SKYLINE查询的国内外研究现状的基础上，针对现有K-支配SKYLINE查询算法存在的不足，提出了基于排序索引的K-支配SKYLINE查询算法，并通过实验验证了该算法的高效性。
　　 本文主要从以下方面作出贡献：
　　 1．集中研究了国内外SKYLINE查询算法及其扩展应用的研究现状，分析了高维环境下K-支配SKYLINE查询能得到更有意义的结果集，针对现有K-支配SKYLINE查询算法的不足，提出了相关的取点排序优化策略和剪枝策略。
　　 2．基于排序索引，本文提出了相关定理，基于这些定理和优化策略，提出了高效K-支配SKYLINE查询算法，并着重分析了算法的渐进性和正确性，同时对算法在时间和空间上的性能也进行了分析。
　　 3．设置实验对上述算法进行验证，实验中采用了两种数据进行验证：人工合成的数据和真实的NBA球员数据。通过分析实验结果发现，基于索引的K-支配SKYLINE查询算法能渐进地返回完整的SKYLINE结果，在各种影响算法性能的因素变化情况下均能保证查询结果准确有效。

关 键 词： 高维数据 排序索引 查询算法 数据挖掘

分 类 号： [TP301.6 TP311.131]

领　　域： [自动化与计算机技术] [自动化与计算机技术] [自动化与计算机技术] [自动化与计算机技术]