论文部分内容阅读
随着人类社会的进步和计算机网络技术的发展，数据信息与物质和能量并列成为世界三大资源。在现今信息爆炸的时代，为了从大规模数据中提取关键信息，迫切需要高效的查询处理技术。Skyline查询作为一种重要的数据管理操作，它在多目标决策支持、环境监控、数据分析、GPS导航等领域发挥着重要的作用。此外，在众多实际应用如传感器网络、基于位置服务(LBS)、射频识别电子标签(RFID)和Web服务中，由于数据采集设备的局限、隐私保护的需求或网络传输延迟等原因，数据广泛具有不确定性。不确定数据处理技术业已成为数据库研究领域的重要研究热点。为此，本文针对不确定Skyline查询相关技术进行深入研究，主要工作和创新点如下: (1)研究了分布式环境下的不确定Skyline查询问题。现有的分布式不确定Skyline查询算法中定义的近似全局Skyline概率不适用于局部查询结果间存在支配关系的情况、未考虑最小化总的查询时间、且每次迭代过程中最多只能返回一个最终查询结果。为此，本文从提高算法的通用性、效率和渐进性出发，首先提出了一种新的分布式不确定Skyline查询处理框架;其次设计了一种自适应的分布式不确定Skyline查询算法;最后大量的实验结果表明本文算法的性能显著优于已有算法。 (2)研究了基于不确定数据的静态Skyline查询问题。现今最通用的不确定Skyline查询定义(P-skyline查询)中返回的查询结果取决于选取的概率阈值，且结果集中包含不理想的数据点。此外，处理大规模数据或高维数据时，P-skyline查询常返回大量结果，从而不能为用户提供有效的决策支持。为此，本文首先基于传统的不确定Skyline查询定义，提出了一种新的不确定Skyline(MPS)查询;其次提出了有效的MPS查询算法;接着探讨了基于规模约束的MPS(MMPS)查询，并将MPS查询算法进行扩展用于解决MMPS查询;最后通过大量的实验验证了算法的有效性和可扩展性。 (3)探讨了基于不确定数据的动态Skyline查询问题。动态Skyline查询能够依据用户的个性化偏好，筛选出更加满足用户需求的产品信息。不确定数据的动态Skyline查询的研究还处于起步阶段，且已有的不确定数据的动态Skyline查询返回的结果取决于概率阈值，时常返回不理想的查询结果。为此，本文形式化定义了一种更通用的不确定数据的动态Skyline查询，依据其特性提出一系列有效的剪枝策略和查询算法，并通过理论分析和实验验证了算法的有效性和可扩展性。 (4)探讨了基于规模约束的不确定动态Skyline查询。不确定动态Skyline查询在处理大规模或高纬度数据时，时常返回大量的查询结果，从而不能为用户提供有意义的启发信息。为此，本文研究了基于规模约束的不确定动态Skyline查询。首先形式化定义了一种基于组用户偏好的查询操作，即Top-k用户最满意的产品(TFPP)查询;其次为了有效处理TFPP查询，提出TFPP算法及并行TFPP(ParTFPP)算法;最后从理论分析和实验验证两个方面证明了所提算法的有效性和可扩展性。 本文工作不仅具有一定的理论价值，丰富了数据管理方面的研究内容，而且推动了不确定数据管理的实用化进程，具有巨大的应用价值和实际意义。