3.1.2 亚线性空间算法
以数据流算法为代表的亚线性空间算法也是处理大规模数据的有效手段。在这个场景里，输入以一个包含元素更新的序列形式呈现：对于图数据流，这些元素对应于图中的边；对于几何数据流，这些元素可能是欧氏空间中的点；对于数据串数据，元素可能对于于某个整数。我们的目标是使用尽可能少的空间来分析数据。由于存储空间有限，我们希望在扫描一次（或少量几次）输入流之后，可以较为准确的推断大数据的性质或结构。数据流算法的代表性工作之一曾在2005年获得了理论计算机科学领域著名的哥德尔奖。流算法能大幅度降低服务器的运算开销，被谷歌, 网飞等公司广泛运用于数据的分析与处理中。此外，流算法无需存储数据的特点也能有效保护用户数据的隐私。
在数据流算法中，有许多经典问题，其中包括向量的频率矩和信息熵等。为了解决这些问题，学者们提出了一系列抽样和勾勒等算法框架。典型的抽样方法包括重要性采样、拒绝采样、重采样等。勾勒技术在大数据处理和实时分析中扮演着重要角色，它允许使用较少的内存和计算资源在数据流中获得近似的答案，同时支持回答一些有趣的查询。由于数据处理过程中持续不断地有数据到达，无法将全部数据存储在内存中，因此通过使用勾勒技术，我们可以在有限的内存和计算资源下对数据进行摘要和近似处理，从而实现高效的数据分析和查询。此外，勾勒技术在优化、联邦学习等领域也发挥着重要作用。在优化问题中，勾勒技术可以加速动态数据结构的更新，从而提高优化算法的效率；在联邦学习中，勾勒技术可以帮助保护隐私并减少通信开销，同时仍然能够进行有意义的模型聚合和更新。
在图数据算法方面，当网络规模过大而无法完全容纳在计算机的主内存中，并且边以数据流的形式出现时，我们希望能够对网络结构进行近似分析。特别是在网络相对密集的情况下，半流算法提供了一种重要的空间高效（相对于输入大小）的处理方式。对于图中的最大匹配等问题，设计高近似比的半流算法仍然是当前研究的热点问题。