VLDB summer school(一)近似查询处理2——数学基础

VLDB summer school(一)近似查询处理2

这是 近似查询处理 系列的第二部分:AQP数学基础
有幸参加VLDB Summer School 2017,7天数据相关课程,收获良多,将知识记录并与大家分享。

一、近似查询处理(AQP)概括介绍

http://blog.csdn.net/kevinbetterq/article/details/76285606

二、AQP数学基础

简单抽样 :
<3,4,5,6,9,10,12,13,15,19>计算总值

开始抽样
- 模拟一个10面的骰子转动5次
- 每一次转动得到的数即为所给10个数中的相应位置的数
- 假设我们转到<6,3,5,3,9>,则为<10,5,9,5,15>
- 计算样本总值:44
- 放大倍数因子2
- 得到值为88(真实值为96)

这是最简单的抽样

Central Limit Theorem(中心极限定理):

中心极限定理指的是给定一个任意分布的总体。我每次从这些总体中随机抽取 n 个抽样,一共抽 m 次。 然后把这 m 组抽样分别求出平均值。 这些平均值的分布接近正态分布。

推荐一个讲的很好的网址:https://zhuanlan.zhihu.com/p/25241653

Next:
这里写图片描述
这里写图片描述
这里写图片描述

Horvitz-Thompson估计 :

这里写图片描述

从偏差和方差到准确性 :

如何转化方差和偏差为准确性?我们需要一个“confidence bound”,形式的概率保证。
以下有几种方法:

这里写图片描述

这里写图片描述

这里写图片描述

三、通过取样的预测

四、从数据库中抽取样本

五、Bootstrap的介绍

六、Sketching的介绍


版权声明:本文为KevinBetterQ原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。