科研之友
微信
新浪微博
Facebook
分享链接
摘要
针对流数据的Top-k查询问题,为降低对存储容量和处理时间的要求,利用概率近似正确(PAC)原理,提出了一种实时查询算法,通过随机抽样近似地估计流数据中最大的k个数据,并保证误差和可信度均在规定的范围内。该算法设置k个随机独立排序器,每个排序器独立地抽取N个数据并返回各自不同的最大值d,然后用这k个最大值排序获得该流数据集合当前的Top-k序列。证明了在给定误差β、可信度γ的条件下,当抽取的样本数量N满足N+1≥log (1-kγ1/2)/log (1-β)时,所得到的Top-k序列即可满足要求的误差和可信度,样本复杂度仅与误差和可信度有关,与当前数据总量无关。在生成的随机浮点数流数据集上进行了实验验证,在给定误差β=0.01的情况下,当抽样数为450时,Top-1查询(即最大数据查询)可以达到γ=0.992的可信度;当抽样数为700时,Top-10查询可以达到0.992的可信度。
- 单位
