Compact Data Structures: A Practical ApproachCambridge University Press, 2016 M09 8 Compact data structures help represent data in reduced space while allowing it to be queried, navigated, and operated in compressed form. They are essential tools for efficiently handling massive amounts of data by exploiting the memory hierarchy. They also reduce the resources needed in distributed deployments and make better use of the limited memory in low-end devices. The field has developed rapidly, reaching a level of maturity that allows practitioners and researchers in application areas to benefit from the use of compact data structures. This first comprehensive book on the topic focuses on the structures that are most relevant for practical use. Readers will learn how the structures work, how to choose the right ones for their application scenario, and how to implement them. Researchers and students in the area will find in the book a definitive guide to the state of the art in compact data structures. |
Contenido
5 | |
11 | |
14 | |
2 | 20 |
3 | 27 |
Arrays | 39 |
3 | 40 |
5 | 41 |
15 | 197 |
Trees | 211 |
3 | 214 |
9 | 228 |
Applications | 245 |
18 | 248 |
1 | 266 |
Graphs | 279 |
7 | 46 |
1 | 52 |
Bitvectors | 64 |
Building a perfect hash function | 94 |
Permutations | 103 |
6 | 110 |
Sequences | 120 |
8 | 133 |
13 | 146 |
Parentheses | 167 |
3 | 168 |
9 | 184 |
2 | 283 |
9 | 298 |
Summary | 338 |
1 | 344 |
Grids | 347 |
7 | 358 |
1 | 396 |
Dynamic Structures | 450 |
Recent Trends | 501 |
549 | |
Otras ediciones - Ver todas
Términos y frases comunes
Algorithm Allocate alphabet assume biconnected components binary search binary tree bit array bits of space bitvector block Canonical Huffman code Cartesian tree cells Chapter chunk close(B compact data structures compressed compute constant constant-time corresponding decode DFUDS edges efficient elements encoding Example extra space Figure grayed grid Huffman code Huffman tree implementation Input insert integers inverted index k2-tree labeled leaf left child LOUDS representation mapped minimum Navarro neighbors number of bits O(log logn obtain occurrences operations optimal ordinal tree Output parentheses perfect hash function permutation planar graphs pointers points popcount position prefix prefix code preorder Proc pseudocode queries range rank and select rank1 recursively represent right child rmM-tree root sampled Section select(B sequence Shannon entropy shows solve string subtree suffix array suffix tree symbol traverse undirected graphs values wavelet matrix wavelet tree worst-case entropy zero-order