图 书 馆
HyperLogLog超扩展:凹次线性频率统计草图HyperLogLog Hyperextended: Sketches for Concave Sublinear Frequency Statistics |
|
| 课程网址: | http://videolectures.net/kdd2017_cohen_hyperloglog/ |
| 主讲教师: | Edith Cohen |
| 开课单位: | 视频讲座网 |
| 开课时间: | 2017-10-09 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | One of the most common statistics computed over data elements is the number of distinct keys. A thread of research pioneered by Flajolet and Martin three decades ago culminated in the design of optimal approximate counting sketches, which have size that is double logarithmic in the number of distinct keys and provide estimates with a small relative error. Moreover, the sketches are composable, and thus suitable for streamed, parallel, or distributed computation. We consider here all statistics of the frequency distribution of keys, where a contribution of a key to the aggregate is concave and grows (sub)linearly with its frequency. These fundamental aggregations are very common in text, graphs, and logs analysis and include logarithms, low frequency moments, and capping statistics. We design composable sketches of double-logarithmic size for all concave sublinear statistics. Our design combines theoretical optimality and practical simplicity. In a nutshell, we specify tailored mapping functions of data elements to output elements so that our target statistics on the data elements is approximated by the (max-) distinct statistics of the output elements, which can be approximated using off-the-shelf sketches. Our key insight is relating these target statistics to the {em complement Laplace} transform of the input frequencies. |
| 关 键 词: | 统计数据; 计数草图; 相对误差; 并行计算 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2022-11-30：chenxin01 |
| 最后编审: | 2022-11-30：chenxin01 |
| 阅读次数: | 21 |