论文部分内容阅读
近年来,随着社会特别是互联网的发展,造成应用数据量急剧增大,致使数据库查询技术得以快速发展和广泛应用。由于Skyline查询在多目标决策等应用上比较具有优势而被引入到数据库领域,并且已成为数据库查询领域的一个研究热点。然而,目前的Skyline查询多是针对单个用户情景下设计的,仅局限于返回单一的结果集,或者在分别由不同维度组成的多个子空间下进行的Skyline查询,并返回多个结果集。随着技术应用的发展以及新需求的出现,实际应用中需要考虑到不同用户的不同需求。他们可能感兴趣的是全局数据中不同局部的数据,这些数据具有局部内相似且局部间相异之特征。在分析现有的Skyline查询算法解决该问题不足的基础上,提出了一种基于K-中心点聚类的Skyline查询算法。该算法能够应用于诸多重要领域,比如推荐系统、传感器网络、数据分析等等。比如能够处理:用户在购买商品时,对同类不同层次的多个商品优化选择问题;无线传感网中,满足不同条件的传感器节点的多目标优化问题。本文研究的内容主要集中在如下方面:(1)在介绍了传统Skyline查询的相关算法时,分析了不同算法的优缺点,以及它们的运算效率。(2)针对现有算法并未顾及数据间相似性问题,提出了基于K-中心点聚类的Skyline查询算法。把相似的数据聚类成一个簇,相异的数据分别聚类到不同的簇,使得簇内数据相似,簇间数据相异。(3)简要介绍和分析了维数灾难问题,并按照数据不同维度之间的相关性,对数据的维度进行正相关降维。因此又在基于K-中心点聚类的Skyline查询算法的基础上进行了改良,提出了基于降维的K-中心点聚类Skyline查询算法。本文实验部分共分两部分:第一部分设计了六组实验,通过将基于K-中心点聚类得到的Skyline点平均数与BNL(块嵌套算法)求解得到的Skyline点的平均数进行对比实验。实验结果显示,基于K-中心点聚类得到的Skyline点平均数要比BNL算法求解得到的Skyline点平均数要有更多的选择性。第二部分设计了一个实验,通过比较发现,改进的基于K-中心点聚类的Skyline算法在时间消耗上明显优于未改进之前的Skyline算法。同时,通过具体案例对提出的算法进行了验证性演示。