DataSketches Research Directions
https://datasketches.github.io/docs/Research.html 来源与雅虎的开源项目，翻译ｂｙ Titanssword 结合自己研究方向，可合并摘要，分位数, k 均值聚类的流式算法, 有关图流处理算法, 有关滑动窗口流算法 Introduction 在分析海量数据集时，即使对数据进行非常基本的查询，也可能需要巨大的计算资源（内存和计算时间）。这种查询的例子包括识别频繁项目，唯一计数查询，分位数和直方图查询，矩阵分析任务（例如主成分分析和潜在语义分析）以及更复杂的下游机器学习任务。一旦数据量大了之后，这些计算任务将变得十分困难。也达不到实时性的要求。 然而，在许多情况下，只要近似误差被仔细控制，近似的答案是可以接受的。例如，如果数据是嘈杂的，那么比数据中已经存在的噪声更少的错误的答案与确切的算法一样有用。即使数据是无噪声的，许多高层次的商业决策也不需要对数据有精确的了解：在特定的时间内，有多少唯一身份用户访问某个网站时，可以知道多达 1％的错误，这通常与确切的答案一样有效。 当大致的答案是可以接受的，系统设计人员已经掌握了关于流算法的大量文献。这些算法一次处理海量数据集，并计算数据集的非常小的摘要（也称为草图），从中可以得出准确（但近似）的查询答案。许多流式传输算法甚至对 PB 级大小的数据集也只用了几千字节的空间，并且能够对每个数据进行定时处理，从而实现实时分析。 Mergeable Summaries 理想情况下，数据流算法将生成可合并的摘要，这意味着可以独立处理许多不同的数据流，然后可以快速组合每个数据流计算出的摘要，以获得各种数据集组合的精确摘要（联合，交叉等）。可合并摘要使大量数据集能够以完全分布式和并行的方式自动处理，通过在许多机器上任意分割数据，汇总每个分区，并无缝结合结果。除了与精确的方法相比，大大减少了内存使用量，计算时间和延迟，可合并的摘要也极大地简化了系统架构。它们允许非加性查询（如唯一计数查询）被视为加法，两个草图的 “总和” 是它们的合并。这意味着数据可以分割成片段，每个片段分别勾画，草图存储在简单的数据集市架构中，并在查询时合并。 合并摘要的最终重要应用是在外围设备较弱的情况下节能。例如，物联网（IoT）的主要优势之一是它可以监控和聚合物联网设备（如传感器和设备）的数据。这样的设备往往是功率受限的，所以必须最小化必须从每个设备发送到聚合中心的数据量。可合并摘要启用了这一点：每个设备可以自己计算自己数据的摘要，并只将摘要发送给聚合中心，聚合中心将所有接收到的摘要合并，以获取所有设备数据集的全局摘要。 Agarwal 等人在其 Mergeable Summaries 可合并摘要论文 中讨论了不同类型的可合并摘要 The Data Sketches Open Source Library 该库从一开始就被设计为高性能和高质量的产品，适用于需要处理海量数据的大型数据处理系统。该库是用 Java 编写的，包含了各种基本查询类的最新算法，包括识别频繁项目，唯一计数查询，计算分位数和直方图以及采样。它很快将包含像 PCA 这样的矩阵分析任务的算法。库中的所有算法都会生成可合并的摘要，并对返回的答案的准确性提供正式的保证。 目前，该库的核心贡献者是 Lee Rhodes，Kevin Lang，Jon Malkin 和 Alex Saydakov（全部来自 Yahoo / Oath），Justin Thaler（乔治敦大学计算机系助理教授）和 Edo Liberty（首席科学家在亚马逊网络服务和亚马逊 AI 算法组的经理） 该库已经在整个行业和政府进行了调整。例如，在雅虎被设计和创建的地方，该库在内部被广泛使用，以减少许多任务的处理时间从几天到几秒。在 SpliceMachine 中，它用于数据库查询计划和优化。它也深深嵌入到一个叫做 Druid 的低延迟开源数据存储中，还有一个由英国情报机构 GCHQ 维护的叫做 Gaffer 的开源图形数据库。 除了在部署系统中的实用性之外，开发数据草图库的开发过程导致了有趣的研究。这既涉及流算法的理论，也涉及解决真实世界流引擎中至关重要的问题，但在学术文献中经常被忽略。这些问题包括可合并性，以及处理加权流更新（即每个数据片带有相关重要性度量的数据流）。 特别是在数据草图库上的工作已经导致了新颖的算法实现用于识别数据流中频繁项目的最新实用性能 [ABL + 17] 和用于唯一计数查询的可合并摘要 [DLRT16]。在理论层面上，该库的工作导致了分位数查询的流近似算法的空间复杂度的解决，这是一个长期以来的开放性问题 [KLL16]Optimal quantile approximation in streams，也是解决识别频繁项集的问题 [LMTU16]Space lower bounds for itemset frequency sketches。*...