大数据——前　　言

本书是在Anand Rajaraman和Jeff Ullman于斯坦福大学教授多年的一门季度课程的材料基础上总结而成的。该课程名为“Web挖掘”（编号CS345A），尽管它已经成为高年级本科生能接受并感兴趣的课程之一，但其原本是一门为高年级研究生设计的课程。 本书内容 简单来说，本书是关于数据挖掘的。但是，本书主要关注极大规模数据的挖掘，也就是说这些数据大到无法在内存中存放。由于重点强调数据的规模，所以本书的例子大都来自Web本身或者Web上导出的数据。另外，本书从算法的角度来看待数据挖掘，即数据挖掘是将算法应用于数据，而不是使用数据来“训练”某种类型的机器学习引擎。 本书的主要内容包括： (1) 分布式文件系统以及已成功应用于大规模数据集并行算法构建的Map-Reduce工具； (2) 相似性搜索，包括最小哈希和局部敏感哈希的关键技术； (3) 数据流处理以及面对快速到达、须立即处理、易丢失的数据的专用处理算法； (4) 搜索引擎技术，包括谷歌的PageRank、链接作弊检测及计算网页导航度（hub）和权威度（authority）的HITS方法； (5) 频繁项集挖掘，包括关联规则挖掘、购物篮分析、A-Priori及其改进算法； (6) 大规模高维数据集的聚类算法； (7) Web应用中的两个关键问题：广告管理及推荐系统。 先修课程 尽管从编号CS345A看，本课程属于高年级研究生课程，但是我们发现高年级本科生和低年级硕士生也能接受该课程。该课程将来可能会分配一个介于高年级研究生和低年级硕士生水平之间的编号。 CS345A的先修课程包括： (1) 数据库系统的首期课程，包括基于SQL及其他数据库相关语言（如XQuery）的应用编程； (2) 大二的数据结构、算法及离散数学课程； (3) 大二的软件系统、软件工程及编程语言课程。 习题 本书包含大量的习题，基本每节都有对应习题。较难的习题或其中较难的部分都用惊叹号“！”来标记，而最难的习题则标有双惊叹号“！！”。 Web上的支持 读者可以从下列网址获得该课程过去提供的材料：http://infolab.stanford.edu/~ ullman/mining / mining.html。 在该网址下，读者可以找到课件、课后作业及项目作业等材料，某些情况下可能还有试题。 致谢 本书封面由Scott Ullman设计。感谢Foto Afrati和Arun Marathe精心阅读本书初稿并提出建设性的意见。感谢Leland Chen、Shrey Gupta、Xie Ke、Haewoon Kwak、Brad Penoff、Philips Kokoh Prasetyo、Mark Storus、Tim Triche Jr.及Roshan Sumbaly指出了本书中的部分错误。当然，剩余错误均由我们负责。 A. R. J. D. U. 加利福尼亚州帕洛阿尔托 2011年6月