Skip to content

Latest commit

 

History

History
50 lines (38 loc) · 3.16 KB

ds.md

File metadata and controls

50 lines (38 loc) · 3.16 KB
Raw

数据结构

数据结构是计算机中存储、组织数据的方式。 数据结构包括数据值和数据的操作。

紧凑数据结构

本课程教授用于处理大数据（尤其是网络大数据）的紧凑数据结构及相应的算法、概率方法和统计工具。 目前最大的大数据或许就是因特网上的数据流了。 对这个大数据的分析能为提高网络性能、网络应用的用户体验及网络安全提供理论基础。 然而网络大数据无法保留。 在这个背景下，本课程讲授一系列在过去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。 学生不但将掌握这些数据结构和算法，而且要学习它们在网络数据测量、安全、及其它领域中的应用。 不但将掌握相关理论知识，而且要实现一部分算法，并在实际网络数据上应用。

succinct data structures

In computer science, a succinct data structure is a data structure which uses an amount of space that is "close" to the information-theoretic lower bound, but (unlike other compressed representations) still allows for efficient query operations.