Welcome to Tong Yang's Homepage

紧凑数据结构与大数据
Compact Data Structures for Big Data

本课程教授用于处理大数据（尤其是网络大数据）的紧凑数据结构及相应的算法、概率方法和统计工具。 目前最大的大数据或许就是因特网上的数据流了。 对这个大数据的分析能为提高网络性能、网络应用的用户体验及网络安全提供理论基础。然而网络大数据无法保留。 在这个背景下，本课程讲授一系列在过去30年里逐渐发展起来的紧凑数据结构和它们的理论分析，这些数据结构可以用来把大数据变小，以便于存储和应用。 本课程的数据结构和算法可以分为两类：

（1）计数与计模，包括probabilistic counting, bitmap algorithms, FM sketch, hyperloglog sketch, virtual bitmap, virutal FM sketch, virtual hyperloglog, countMin, counter braids, randomized counter sharing, and virtual counters；

（2）成员查找与分类，包括Bloom filters, counting Bloom filters, Bloomier filters, blocked Bloom filters, multi-set filters, and multi-hashing tables。 学生不但将掌握这些数据结构和算法，而且要学习它们在网络数据测量、安全、及其它领域中的应用。 不但将掌握相关理论知识，而且要实现一部分算法，并在实际网络数据上应用。

陈世刚（1971年5月生，sgchen8@gmail.com），佛罗里达大学正教授（2002年入校）、博士生导师、IEEE Fellow、ACM Distinguished Scientist、IEEE Communication Society Distinguished Lecturer、佛罗里达大学计算机系网络实验室主任，长期从事网络与信息安全的研究，在网络大数据、网络算法、射频标签、网络安全、物联网等方向研究取得了一系列开拓性成果。以优异教学和科研获2017年University of Florida Term Professorship。发表专著5部，期刊会议论文180余篇，CCF A类69篇，总引用数超过9700余次（Google Scholar），引用超过1000次的论文3篇。拥有12项美国授权专利，其中作为主要发明人的10项专利应用在思科安全策略管理软件中（Cisco Secure Policy Manager，CSPM）中。

杨仝，北京大学信息科学技术学院助理研究员。目前主要从事网络大数据研究，包括网络流量测量、Bloom filters、路由表查找、Sketches、键值存储系统、哈希表等。在国际著名会议上发表多篇论文，包括SIGCOMM、VLDB、ICDE、ICNP、ICDCS、IWQoS等。作为项目负责人主持国家自然科学基金项目2项、作为分课题负责人负责重点研发项目一项。

基本目的

  1. 学生将在课程结束时掌握一系列（尤其是网络大数据）的紧凑数据结构及相应的算法、概率方法和统计工具。
  2. 学生不但将掌握相关理论知识，而且要学习它们在网络数据测量、安全、及其及其它领域中的应用，并且要实现一部分算法。
  3. 帮助学生理解和分析大数据，培养和训练学生的研究能力。

内容提要及相应学时分配：

Introduction to Big Data and Compact Data Structures 2学时

Counting and Cardinality Algorithms

Membership Lookup and Classification

教学方式

课堂授课为主，课后练习、编程为辅。

学生成绩评定办法

平时（30%），编程（40%），考试（30％）

作者 书名/论文名称 出版社 出版年
1

Shigang Chen, Min Chen, Qingjun Xiao

Traffic Measurement for Big Network Data

Springer, ISBN 978-3-319-47340-6

2016
2

Tao Li, Shigang Chen

Traffic Measurement on the Internet

Springer, ISBN: 978-1-4614-4850-1

2012
3

Kyu-young Whang, Brad T. Vander-Zanden, Howard M. Taylor

A Linear-Time Probabilistic Counting Algorithm for Database Applications

ACM Transactions on Database Systems, Vol. 15, No. 2

1990
4

Cristian Estan, George Varghese, Mike Fisk

Bitmap Algorithms for Counting Active Flows on High Speed Links

ACM Internet Measurement Conference

2003
5

Peter Lieven, Bj¨orn Scheuermann

High-Speed Per-Flow Traffic Measurement with Probabilistic Multiplicity Counting

IEEE INFOCOM

2010
6

Philippe Flajolet,  Éric Fusy, Olivier Gandouet and Frédéric Meunier

HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm

Conference on Analysis of Algorithms

2007
7

Qingjun Xiao, Shigang Chen, Min Chen, Yibei Ling

Hyper-Compact Virtual Estimators for Big Network Data Based on Register Sharing

ACM SIGMETRICS

2015
8

Yi Lu, Andrea Montanari, Balaji Probhakar, Sarang Dharmapurikar, and Abdul Kabbani

Counter Braids: A Novel Counter Architecture for Per-Flow Measurement

ACM SIGMETRICS

2008
9

Andrei Brodery, Michael Mitzenmacherz

Network Applications of Bloom Filters: A Survey

Internet mathematics

2004
10

Fang Hao, Murali Kodialam, T. V. Lakshman,

and Haoyu Song

Fast Dynamic Multiple-Set Membership Testing

Using Combinatorial Bloom Filters

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 20, NO. 1

2012