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。*
将新的和更丰富的查询类型的算法结合到库中，以及提高已经实现的算法的效率是主要的机会。
Improved Algorithms for Unique Counting
在最近的数据草图库 [Lan17] 的工作中，Kevin Lang 描述了几种用于估计数据流中不同元素数量的流式算法。该算法比先前的算法 Hyperloglog（HLL）[FFGM07] 具有更好的空间 / 精度折衷，该算法在近十年来一直被认为是该问题实际性能的黄金标准。具体而言，对于给定的准确度水平，Lang 的算法使用的空间比 HLL 草图的熵少 20％，因此比任何可能的 HLL 实现少 20％的空间。
关于运行时间，Lang 的预打印显示他的一些算法具有与 HLL 的直接实现相当的速度，但比重度优化的 HLL 实现要慢一些。重要的研究仍然是优化新算法的速度，确定哪种变体算法在真实数据上表现最好，最适合于生产环境，最终产生该算法的生产质量实现。
Algorithms For Anomaly Detection
处理海量数据流的共同目标是识别异常事件或数据点。例如，在线广告商或内容提供商可能会尝试识别点击流数据中的欺诈行为，网络运营商可能会尝试快速识别网络入侵者或 DDoS 攻击，或者数据分析师可能会在运行后续学习算法之前尝试清除数据集中的异常值。
数据草图库已经包含了几种对数据流异常检测有用的算法。一个例子是图书馆用于回答分位数查询的算法。* 在分位数问题中，流指定了一个实数列表，并且（例如）顶部或底部百分位数中的任何流更新（根据定义）是在外值或异常值。如上所述，Data Sketches 团队已经解决了流分位数计算的渐近空间复杂度 [KLL16]，目前正在完成文献中已经提出的各种分位数算法的仔细实证研究。对于异常检测有用的库中的第二个算法是其用于识别频繁项目的新颖算法 [ABL + 17]A high-performance algorithm for identifying frequent items in data streams：构成异常大部分数据集的任何项目本质上是异常的。*
展望未来，Data Sketches 团队将整合适用于异常检测的其他查询类别的算法。主要目标包括熵计算 [CCM10，Tha07]，层级重击者 [MST12] 的识别和超级扩频器的识别 [VSGB05]（所有这些都已经在检测网络流量异常的情况下进行了深入的研究）。
针对所有这三个问题的最为人所知的流式算法使得黑箱使用用于识别频繁项目的更简单任务的算法。由于库为后一项任务提供了最先进的算法，因此团队将为这些更复杂的问题开发高效的解决方案。
尽管用于识别分层重击和超分割的现有流媒体算法产生可合并的摘要，但是唯一已知的用于熵计算的实际算法 [CCM10] 不能。 Data Sketches 团队将尝试解决的一个具有挑战性的问题是开发了一种熵计算的实用可合并草图算法。
## Matrix and Clustering Algorithms
对于矩阵的低秩逼近在包括 PCA 在内的许多无监督学习任务中是有用的。通过识别数据矩阵的 “最有说服力的方向”，低秩近似有效地揭示数据集中的潜在结构。他们还加快了下游的学习任务，因为这些任务可以在低秩近似上运行，而不是在原始矩阵上运行。在 [Lib13]Simple and deterministic matrix sketching 中，Liberty 提出了一种用低秩矩阵来近似数据矩阵的近似最优流算法。该算法假定数据矩阵是以行方式流式传输的，意味着每个流更新以原子方式指定矩阵的新行。
计算矩阵的低秩近似可以被看作是识别矢量流中的 “频繁方向”，并且 Liberty 的算法可以被看作是用于识别项目流中的频繁项目的算法的直接泛化。基于 [ABL + 17] 中描述的并且已经在数据草图库中实现的频繁项目算法，Data Sketches 团队即将完成 Liberty 算法的生产质量实现。一旦这个实现完成，正在进行的研究将确定额外的优化，以进一步提高算法的速度和准确性，并将执行一个仔细的经验比较其性能相对于文献中的替代算法。 Data Sketches 团队还将开发能够处理数据矩阵的更一般类型更新（而不仅仅是行更新）的算法。
团队将在不久的将来追求的相关方向是 开发用于 k 均值聚类的流式算法的生产质量实现。低秩矩阵近似和聚类问题是密切相关的（参见，例如，[CEM + 15]）Dimensionality reduction for k-means clustering and low rank approximation，我们相信低秩矩阵近似的思想对于开发有效的聚类算法是有用的。
Graph Algorithms
非常大的图形无处不在。它们出现在诸如社交网络分析和网络流量日志之类的设置中，例如亚马逊虚拟私有云所捕获的设置。* 有关图流处理算法的丰富的理论文献（参见 McGregor [McG14] 的综述） Graph stream algorithms: a survey.，尽管在这样的算法上应用的工作相对较少。*
开发图形流的生产质量算法是 Data Sketches 团队在不远的将来追求的一个关键方向。* 一个主要的目标问题是图稀疏化，其中一个在密集图中抛弃了大部分边，但是这样做是非常谨慎的，所以得到的稀疏图继承了许多与原密集图相同的属性。稀疏图可以看作是原密集图的近似值，可以代替聚类和社区检测等任务下游的密集图。当在稀疏图上运行时，这些下游算法将需要少得多的计算能力，而稀疏图上的结果将可证明地近似原始密集图上的结果。*
Sliding Windows
在许多应用程序中，数据最终会变得陈旧或过时，因此查询应该被限制在相对较新的数据中。可合并摘要可以简单地解决这个问题：将数据分成相对较小的块（每个块覆盖一个小时的时间段），分别勾画每个块，并在查询时合并仅最近的摘要块。
这个解决方案在一些应用中是足够的，但是对于其他应用来说，块必须更细粒度（例如，当检测到持续数秒或数分钟而不是数小时的异常或现象时）。在这些设置中，基于可合并摘要的幼稚方法在内存使用和延迟方面变得非常昂贵。对于这样的设置，理想的解决方案是一个流式算法，在数据过期时自动“忘记”数据。这个设置已经在有关滑动窗口流传输算法的文献中进行了研究。已经研究了用于频繁项目（例如[GDD + 03]） Approximate counts and quantiles over sliding windows. ，唯一计数（例如[GT02]）和分位数（例如[AM04]）的滑动窗算法的工作。就像Data Sketches库中的工作已经在标准（非滑动窗口）流设置中针对这些问题中的每一个开发高效算法一样，导致了显着的最近进展，我们相信相关的想法将导致滑动窗口设置也是如此。