Data sketches are approximate succinct summaries of long streams. They are widely used for processing massive amounts of data and answering statistical queries about it in real-time. Existing libraries producing sketches are very fast, but do not allow parallelism for creating sketches using multiple threads or querying them while they are being built. We present a generic approach to parallelising data sketches efficiently, while bounding the error that such parallelism introduces. Utilising relaxed semantics and the notion of strong linearisability we prove our algorithm's correctness and analyse the error it induces in two specific sketches. Our implementation achieves high scalability while keeping the error small.


翻译:数据草图是长流的大致简洁摘要。 它们被广泛用于处理大量数据并实时回答关于这些数据的统计问题。 现有的图书馆制作草图非常快, 但不允许使用多条线条制作草图, 或者在建建中时用多条线条来查询这些草图。 我们提出了一个通用的方法来有效地平行数据草图, 同时将这种平行主义带来的错误捆绑起来。 利用宽松的语义和强线性概念, 我们证明了算法的正确性, 并在两个具体的草图中分析了它引起的错误。 我们的落实在保持小错误的同时, 实现了高度的可缩放性 。

0
下载
关闭预览

相关内容

FAST:Conference on File and Storage Technologies。 Explanation:文件和存储技术会议。 Publisher:USENIX。 SIT:http://dblp.uni-trier.de/db/conf/fast/
【深度学习视频分析/多模态学习资源大列表】
专知会员服务
89+阅读 · 2019年10月16日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
186+阅读 · 2019年10月10日
[综述]深度学习下的场景文本检测与识别
专知会员服务
76+阅读 · 2019年10月10日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
LibRec 精选:从0开始构建RNN网络
LibRec智能推荐
5+阅读 · 2019年5月31日
LibRec 精选:近期15篇推荐系统论文
LibRec智能推荐
5+阅读 · 2019年3月5日
LibRec 精选:推荐系统的常用数据集
LibRec智能推荐
17+阅读 · 2019年2月15日
LibRec 精选:推荐系统的论文与源码
LibRec智能推荐
14+阅读 · 2018年11月29日
LibRec 精选:基于LSTM的序列推荐实现(PyTorch)
LibRec智能推荐
50+阅读 · 2018年8月27日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
LibRec 精选:推荐系统9个必备数据集
LibRec智能推荐
6+阅读 · 2018年3月7日
LibRec 每周精选:10篇每个人都应该读的RecSys文章
LibRec智能推荐
5+阅读 · 2018年1月1日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
A Sketch-Based System for Semantic Parsing
Arxiv
4+阅读 · 2019年9月12日
Arxiv
5+阅读 · 2018年5月1日
Arxiv
5+阅读 · 2018年3月6日
Arxiv
4+阅读 · 2018年1月29日
Arxiv
3+阅读 · 2017年12月14日
VIP会员
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
LibRec 精选:从0开始构建RNN网络
LibRec智能推荐
5+阅读 · 2019年5月31日
LibRec 精选:近期15篇推荐系统论文
LibRec智能推荐
5+阅读 · 2019年3月5日
LibRec 精选:推荐系统的常用数据集
LibRec智能推荐
17+阅读 · 2019年2月15日
LibRec 精选:推荐系统的论文与源码
LibRec智能推荐
14+阅读 · 2018年11月29日
LibRec 精选:基于LSTM的序列推荐实现(PyTorch)
LibRec智能推荐
50+阅读 · 2018年8月27日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
LibRec 精选:推荐系统9个必备数据集
LibRec智能推荐
6+阅读 · 2018年3月7日
LibRec 每周精选:10篇每个人都应该读的RecSys文章
LibRec智能推荐
5+阅读 · 2018年1月1日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
Top
微信扫码咨询专知VIP会员