译者序

随着信息技术与互联网技术的快速发展，因特网、社交网络、移动互联网、物联网等众多应用催生出了大规模的数据。针对大数据技术的国际竞争日趋激烈，面向大数据分析算法与系统软件的研究成为当前国内外学术前沿的热点。

面对大规模数据的分析，现实中常存在计算和存储的限制，导致无法完全对大数据进行准确计算。例如在面向计算机网络流量的测量分析中，海量高速的网络数据包和网络路由器有限的硬件资源之间的矛盾导致网络数据包难以实现全量实时的捕获和存储。网络路由器有限的硬件资源决定了其可缓存的网络数据包数量有限，面对主干网高速的网络流量，路由器处理每个数据包的时间非常有限。因而，针对每个数据包仅限于简单的运算和操作，否则会影响后续数据包的正常转发，导致出现网络丢包、网络拥塞等现象，从而造成网络性能的急剧下降。除此之外，大规模的网络流量数据也难以全量存储，40 Gbit/s网络链路满负荷运行每天产生的网络流量约为432 TB，实时存储和分析如此大规模的数据面临巨大的挑战和高昂的成本。因此，目前基于软件定义的网络路由器采用基于概率统计的近似估计方法来实现对网络流量态势的测量。

本书介绍的概率数据结构是针对大规模数据近似计算专门设计的。不同于常规确定性数据结构，概率数据结构总是提供近似的答案以及估计结果的误差范围。本书的作者Andrii Gakhov博士曾在哈尔科夫国立大学计算机科学学院任教多年，目前在产业界从事软件研发，具有丰富的产学研经验。本书详细介绍的概率数据结构和算法包括集合成员查询、集合基数计算、数据流频数统计、相似性快速查找等众多实际应用中面临的典型问题，并提供了相关的免费开放源代码Python库。本书涉及的基础知识与众多理工科大学生必修的课程“数据结构与算法”和“概率论”有关，因此本书可以作为相关课程的课外读物。同时，本书也为软件架构师、开发人员等技术从业人员提供了良好的理论和实践材料。