基于最小计数和频率概要的大域数据流缺失值填充

"一种大域数据流中缺失值的填充方法 (2011年)" 在大数据分析和实时监控领域，如网络流量监控，数据流处理是至关重要的。数据流中的某些属性，例如IP地址，可能拥有极大的值域，使得存储全部数据变得不切实际。为了有效地管理这些大域数据流，通常会维护一个小型的数据概要，而不是保留全部数据集。然而，这种情况下，处理数据流中的缺失值成为一项挑战，因为传统的邻近值填充方法不再适用，同时删除缺失值也可能导致重要信息丢失。 最小计数概要（Minimum Count Sketch, MCS）是一种针对大域数据流的轻量级数据概要技术，它能够高效地提供数据流中的频繁项估计。本文提出了一种名为最小频率概要（Minimum Frequency Sketch, MFS）的新概念，它是基于MCS的扩展，用于更好地填充大域数据流中的缺失值。这种方法的关键在于设计一组相互独立的Hash函数家族，这些函数将数据流的属性值（例如网络流量）映射并累积到一个非大域的二维表中，从而构建出数据流的计数概要和频率概要。 计数概要记录了特定时间段内的累计数据量（例如网络总流量），而频率概要则保存了对应数据包或事件的到达次数。通过比较最小计数概要与最小频率概要之间的比例，可以估算出缺失值（例如，单个数据包的流量）。这种方法的优势在于，它能够在处理大规模数据时保持相对高的精度，而且填充误差会随着数据属性值定义域的变化呈现出非单调性特征。 实验结果表明，基于最小计数/频率概要的填充方法在通用软硬件环境下具有高精度。尽管随着数据量的增加，填充误差会逐渐增大，但其增长速度逐渐放缓，最终趋于一个稳定的误差水平。对于给定的误差参数，该填充算法的时间和空间复杂度有明确的界限，部分特定应用的处理时间界限也有理论依据。 关键词：大域数据流，不确定性，缺失值填充，最小计数概要，最小频率概要，数据流处理，Hash函数，数据概要，网络流量监控。