海量数据近似top-k查询算法研究

发布时间：2021-01-21 20:18

　　信息科技的飞速发展使得全球数据量爆炸增长,在海量数据中快速、有效地检索到目标数据的top-k查询方法是当前计算机研究的热点问题。在海量数据中,使用传统的top-k查询方法返回精确结果往往需要很长的响应时间。因此,以牺牲精度为代价来换取更快响应速度的近似top-k查询具有重要的研究意义。本文主要从确定性保证和概率性保证两方面对海量数据上的近似top-k查询算法展开研究。在具有确定性保证的近似top-k查询研究中,本文提出了基线算法BACG算法,基线算法在经典TA算法中加入近似因子?,放宽了阈值界限,使得返回的近似查询结果具有确定性保证。为了避免随机访问带来过大的时空开销,本文提出了基于有序列表的具有确定性保证的近似top-k查询算法AQCG算法,AQCG算法包括预处理、增长阶段和收缩阶段。在AQCG算法的增长阶段加入偏好扫描,使在扫描过程中能跳过属性列上的不必要元组,尽快收敛到阈值,进入收缩阶段。为了尽早结束查询过程,加入增长剪切和收缩剪切,剪切大部分元组,大大减少了I/O次数。通过实验验证,AQCG算法可以有效计算确定性近似top-k查询结果。在具有概率性保证的近似top-k查询研究中... 

【文章来源】：哈尔滨工业大学黑龙江省 211工程院校 985工程院校

【文章页数】：65 页

【学位级别】：硕士

【部分图文】：

城市酒店数据示例图

哈尔滨工业大学工学硕士学位论文-26-宽(bandwidth)，反映了KDE曲线整体的平坦程度，带宽越大，观察到的数据点在最终形成的曲线形状中所占比重越小，KDE整体曲线就越平坦，带宽过大或过小都会影响估计结果。(a)轮询扫描(b)偏好扫描图3-4扫描方式对当前的有序列表进行分块，前面一部分用于预计算，找到一个近似top-k阈值，假设tscore是top-k预计算近似结果分数的下界，根据属性的概率分布来扫描有序列表，根据当前元组的PI值，索引哈希表，如果返回null，则表明哈希表中没有此元组，将此元组插入到哈希表中。若top-k候选集未满，则将此元组加入top-k候选集，并置=；否则，比较当前元组的下界()与堆顶元素tscore的大小，若()>，使用当前元组替换堆顶元组，并置=。如果当前元组已存在哈希表中，则在哈希表中更新该元组；若top-k候选集未满，检查该元组flag值，若=，将该元组插入top-k候选集，否则，根据PI值在top-k候选集中找到并更新该元组的下界；若top-k候选集已满，检查该元组flag值，若=且该元组满足()>，使用当前元组替换堆顶元组，否则，更新top-k候选集中该元组的下界。

哈尔滨工业大学工学硕士学位论文-27-图3-5有序列表扫描示意图对每一个扫描的元组执行此过程，如果哈希表当前存储的元组数超过了预设值，则将哈希表中的数据输出到磁盘上，并且与之前指定的缓存文件合并，然后清空哈希表中的数据，继续执行接下来的操作，通过这个方法实现处理维护的元组数量超过内存最大值的情况，但是该方法延长了近似top-k增长阶段的执行时间，因为在两次文件合并之间，当前哈希表存储的不是增长阶段已经看到的所有元组信息，而只是上次哈希表清空后看到的部分元组信息，只有当下一次文件合并操作时，才可以更新已经看到的所有元组信息。在增长阶段中，判断是否要将当前元组添加到top-k候选元组集中时，AQCG算法加入了增长剪切，如果当前元组的聚合值的上界小于top-k候选集中最小的元组的聚合值的下界，则当前元组一定不会是最终的top-k查询结果，可以直接剪切这样的元组，不需要进入top-k候选元组集中，这样可以减少比较次数，同时降低了需要维护的候选元组的数量成本，减少内存消耗，大大降低了I/O的次数。在处理过程中，通过不断更新当前的阈值和top-k候选集中的下界，当满足(1+)×≥时，增长阶段结束，算法进入收缩阶段，此时哈希表中保存着所有已扫描过的元组。3.2.4收缩剪枝在收缩阶段中，通过计算分数上界={(),∈}，分数上界不断与top-k候选集中最小的元组的聚合值的下界进行比较，如果<，将top-k候选集中最小的元组从候选集中剔除，继续下一次扫描，直到>，收缩阶段结束，返回堆中的元组作为确定性近似top-k查询的最终结果。

【参考文献】：
期刊论文
[1]分布式网络下改进的Top-k查询算法[J]. 杨浩,林喜军,曲海鹏.  计算机工程. 2017(02)
[2]基于压缩的海量不完整数据近似查询方法[J]. 王妍,刘赓浩,王俊陆,宋宝燕.  计算机研究与发展. 2016(03)



本文编号：2991825