论文部分内容阅读
Top-k支配查询返回指定数据集中支配其他数据点最多的前k个数据点。该查询结合了Top-k查询和Skyline查询的优点。由于在很多决策支持应用中的重要作用,Top-k支配查询近年受到了很多学者和业界的重视。然而,已有的算法大多默认数据集是完整的,所以不能运用在不完整数据上。在实际数据库中由于设备故障、隐私保护、数据丢失等原因,很容易出现不完整数据。这就需要针对不完整数据上的查询提出有效的算法。本文分析了不完整数据上的Top-k支配查询定义的局限性,提出了两个更加灵活的不完整数据上的宽松和基于聚合函数的Top-k支配查询问题,以满足相应的应用需求。鉴于此,本文着重研究了处理这两种查询的算法,主要内容包括如下四个方面: 1.引入了基于位图的索引结构来支持不完整对象的快速支配关系判断。 2.首次引入了不完整数据上的宽松Top-k支配查询,给出了其形式化定义,并提出了有效的算法来处理该查询。 3.首次引入了不完整数据上的聚合Top-k支配查询,给出了其形式化定义,并根据聚合函数的特点,分别对sum、max、min这三个聚合函数提出了有效的查询算法。 4.分析了本文所提出算法的正确性和时间复杂度,并在真实和合成数据集上对各个参数下算法的性能进行测试,验证了算法的有效性和稳定性。