论文部分内容阅读
Skyline查询能够返回用户更感兴趣的数据,是数据库研究领域的研究热点之一,在航班查询、商品推荐、住宿选择等诸多领域得到了广泛的应用。作为skyline查询的一种变体,skyline-join查询能够解决多个数据集上的skyline查询问题。Skyline-join查询一般基于完整数据库进行,然而由于自动信息提取和聚合的广泛使用,不完整的数据集已成为一种常见现象。当获取的信息的属性存在缺失时,现有的不完整数据集上skyline-join查询算法一般基于概率或基于打分的方式进行处理。为了更能真实反映现实情况和更以用户为中心,本文提出一种基于众包的方法来解决不完整数据的skyline-join查询。主要思想是当元组中某些属性的值未知时,利用众包来推断元组之间的成对偏好。具体而言,提出的解决方案考虑了现有的启用众包的算法中使用的2个关键因素,即通过使用元组在已知属性上的偏好关系来最小化众包成本和通过并行处理向人群提出的问题来减少等待时间的轮数。根据skyline-join查询在不完整数据库中是否包括已知属性值的属性维度将基于众包的skyline-join查询分为两类,即基于众包的部分skyline-join查询和基于众包的全局skyline-join查询。基于众包的部分skyline-join查询表示对于skyline-join查询的两个数据集,一个数据集的所有属性都是已知的,而另一个数据集的一个属性是未知的,其中skyline-join查询仅涉及到需要众包的未知属性和连接属性。而基于众包的全局skyline-join查询在不完整数据库上除了包含需要众包的未知属性和连接属性,还涉及到其它属性值已知的属性。本文的主要内容总结如下:(1)针对基于众包的部分skyline-join查询,本文提出基于众包的部分skyline-join查询处理方法(Partial Skyline-Join with Crowdsourcing Algorithm,PSJCrowd)。首先,采用BNL算法过滤数据属性均已知的数据集;其次,采用成对比较的锦标赛算法过滤不完整数据集;最后,依据完整数据集上的属性偏好建立跨层偏好树索引(level-preference-tree-index),过滤全局数据并返回skyline-join查询结果。(2)针对基于众包的全局skyline-join查询,本文提出了基于众包的全局skyline-join查询处理方法。首先,过滤已知数据集;其次,在不完整数据集上,基于不完整数据集的已知属性构建跨层偏好树索引;再次,提出单一数据集全局skyline-join算法(All Skyline-Join with Crowdsourcing on single dataset Algorithm,ASJCrowd-single),对不完整数据集进行过滤;最后,基于不完整数据集和完整数据集的已知属性构建全局跨层偏好树索引,提出多数据集skyline-join算法(All Skyline-Join with Crowdsourcing on multiple datasets Algorithm,ASJCrowd-multiple),基于全局跨层偏好树索引和每一轮众包的结果对连接的元组进行过滤。(3)通过实验证明了本文不完整数据集skyline-join算法在减少众包代价和众包时延上的有效性,实验从属性维度数量变化和数据基数变化变化两个方面分析了算法运行时众包成本和时延的变化,并在单一数据集上与CrowdSky算法做对比试验,通过对比实验证明了两种算法具有很高的性能,与基线方法和CrowdSky算法相比,PSJCrowd算法和ASJCrowd算法存在明显的优势。