分布式不确定skyline查询处理关键技术研究

With the new data model such as Social Networking, Location-based services and so on finding their way into our life,data's characters which are uncertain and massive volume have been paied extensive attention.How to manage the abundant and uncertain data effectively has been one of the most hop topics in information science.As an important problem of data management, uncertain skyline query is applied widely in the area of decision support,data mining and environmental monitoring.However, most of the current research fruits about uncertain skyline query are for centralized databases. It is lack of attention on the distributed uncertain skyline query technology. Hence,in this topic we will study the key technologies of distributed uncertain skyline query.Fistsly, we will propose new models for the uncertain skyline query and its two extended problems, top k uncertain skyline query and uncertain k-Dominant skyline query, according to different data types and application scenarios respectively. Secondly, effective spatial and probabilistic pruning strategies will be given to reduct the problem's computational complexity.Then the classical algorithm design strategies of the fuzzy mathmatical and the game theory will be introduced to the distributed algorithms for the problems above respectively. Furthermore, we will analyze the presented algorithms' communication cost and the execution time. It is worth to notice that this study will not only provide new insights into uncertain skyline query, but also enrich the research content of data managemen.

数据呈现出海量性和不确定性，大规模不确定数据的有效管理已成为当前信息学科研究最活跃的领域之一。不确定skyline查询是数据管理中的重要研究技术，在决策支持、数据挖掘和环境监控等方面的应用极为普遍。当前不确定skyline查询的相关研究成果大多面向集中式数据库，对于分布式数据库的研究还比较少。本课题中，我们将研究分布式不确定skyline查询处理关键技术。首先针对不同的数据类型及应用场景，分别提出不确定skyline查询模型和top k不确定skyline查询、不确定k支配skyline查询的新模型；其次，分别设计高效的空间和概率剪枝策略，降低问题的计算复杂度；随后，引入模糊数学、博弈论中的算法设计技术，分别设计以上问题的分布式算法。并根据通信成本及执行时间两大性能指标对算法进行分析。本课题的研究不仅能够为不确定skyline查询算法的设计提供新思路, 还将丰富传统分布式数据处理的研究内容。

分布式不确定skyline查询处理关键技术研究，分别提出不确定skyline查询模型和top-k不确定skyline查询、不确定k支配skyline查询的新模型；其次，分别设计高效的空间和概率剪枝策略，降低问题的计算复杂度；随后，引入模糊数学、博弈论中的算法设计技术，分别设计以上问题的分布式算法。课题研究不仅能够为不确定skyline查询算法的设计提供 新思路, 还将丰富传统分布式数据处理的研究内容。.（1）从提高算法的通用性、效率和渐进性出发，首先提出了一种新的分布式不确定Skyline查询处理框架；其次设计了一种自适应的分布式不确定Skyline查询算法；最后大量的实验结果表明本文算法的性能显著优于已有算法。.（2）基于传统的不确定Skyline 查询定义，提出了一种新的不确定Skyline (MPS) 查询；其次提出了有效的MPS 查询算法；接着探讨了基于规模约束的MPS (MMPS)查询，并将MPS 查询算法进行扩展用于解决MMPS 查询；最后通过大量的实验验证了算法的有效性和可扩展性。.（3）形式化定义了一种更通用的不确定数据的动态Skyline 查询，依据其特性提出一系列有效的剪枝策略和查询算法，并通过理论分析和实验验证了算法的有效性和可扩展性。.（4）研究了基于规模约束的不确定动态Skyline 查询。首先形式化定义了一种基于组用户偏好的查询操作，即Top-k 用户最满意的产品(TFPP) 查询；其次为了有效处理TFPP查询，提出TFPP 算法及并行TFPP (ParTFPP)算法；最后从理论分析和实验验证两个方面证明了所提算法的有效性和可扩展性。