数据结构是计算机中存储、组织数据的方式。 数据结构包括数据值和数据的操作。
- https://zhuanlan.zhihu.com/p/38194127
- https://cs.uwaterloo.ca/~imunro/Durhamo4.ppt
- http://www.lirmm.fr/mastodons/talks/Gog-indexing-2014.pdf
- http://www.eecs.tufts.edu/~aloupis/comp150/topics.html
- http://stevehanov.ca/blog/?id=120
- https://arxiv.org/abs/1902.09228
- http://www-erato.ist.hokudai.ac.jp/alsip2012/
- https://www.cise.ufl.edu/~sgchen/Research.html
- https://users.dcc.uchile.cl/~gnavarro/
- https://users.dcc.uchile.cl/~gnavarro/publ.html
本课程教授用于处理大数据(尤其是网络大数据)的紧凑数据结构及相应的算法、概率方法和统计工具。 目前最大的大数据或许就是因特网上的数据流了。 对这个大数据的分析能为提高网络性能、网络应用的用户体验及网络安全提供理论基础。 然而网络大数据无法保留。 在这个背景下,本课程讲授一系列在过去30年里逐渐发展起来的紧凑数据结构和它们的理论分析, 这些数据结构可以用来把大数据变小,以便于存储和应用。 本课程的数据结构和算法可以分为两类:
- 计数与计模,包括probabilistic counting, bitmap algorithms, FM sketch, hyperloglog sketch, virtual bitmap, virutal FM sketch, virtual hyperloglog, countMin, counter braids, randomized counter sharing, and virtual counters;
- 成员查找与分类,包括Bloom filters, counting Bloom filters, Bloomier filters, blocked Bloom filters, multi-set filters, and multi-hashing tables。 学生不但将掌握这些数据结构和算法,而且要学习它们在网络数据测量、安全、及其它领域中的应用。 不但将掌握相关理论知识,而且要实现一部分算法,并在实际网络数据上应用。
- 紧凑数据结构与大数据 Compact Data Structures for Big Data
- 02951 Compact Data Structures
- http://latin2016.natix.org/wp-content/uploads/2016/04/tutorial.pdf
- http://fenris.cs.ucr.edu/pipermail/cpm-spire-l/2018-March/000457.html
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.
- https://www.cs.helsinki.fi/group/suds/
- http://simongog.github.io/
- http://algo2.iti.kit.edu/gog/homepage/index.html
- https://arxiv.org/abs/1904.02809
- https://github.com/simongog/sdsl-lite
- https://github.com/simongog/sdsl-lite/wiki/Literature
- https://github.com/simongog/sdsl-lite
- Succinct Data Structures-Exploring succinct trees in theory and practice
- Presentation "COBS: A Compact Bit-Sliced Signature Index" at SPIRE 2019 (Best Paper Award)