What do you think?
Rate this book
Compact Data Structures: A Practical Approach
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.
570 pages, Hardcover
Published September 12, 2016
6 people are currently reading
53 people want to read
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 of 1 review
June 29, 2024
I used this book as an introduction and reference over the last years as my main focus were succinct arrays, bitvectors, and graphs for my side project
The first chapter on entropy and coding was excellent, too. I can't say much about the other chapters as I've only skimmed them.
On bitvectors I would have loved a better separation between data structures modifying the bitvector itself e.g. for interleaving partial ranks and those who keep their auxiliary data separate from the original bitvector.
On graphs it would have been great to mention that the adjacency lists are sorted and we can compress them using techniques from the encodings chapter in addition to using a bitvector to indicate the adjacency list start positions.
As of writing this in 2024 a few things have changed and I recommend folks interested in succinct rank-select enabled bitvectors to check out the following research:
"SPIDER: Improved Succinct Rank and Select Performance" to summarize and improve on state of the art
"Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors"
"A Fast x86 Implementation of Select"
And Vigna's seminal broadword paper with rank9, select9, and simple-select is still a very good start.
On the implementation side of things we now have POPCNT and PDEP hardware instructions on x86 and it looks like rank and select within a cache line of 64 bytes are best handled with repeated popcounts and it's not even worth anymore precomputing. This is where theory and practice meets.
Overall a solid book for an introduction and as a reference - but make sure to keep up with latest developments in this moving field.
The first chapter on entropy and coding was excellent, too. I can't say much about the other chapters as I've only skimmed them.
On bitvectors I would have loved a better separation between data structures modifying the bitvector itself e.g. for interleaving partial ranks and those who keep their auxiliary data separate from the original bitvector.
On graphs it would have been great to mention that the adjacency lists are sorted and we can compress them using techniques from the encodings chapter in addition to using a bitvector to indicate the adjacency list start positions.
As of writing this in 2024 a few things have changed and I recommend folks interested in succinct rank-select enabled bitvectors to check out the following research:
"SPIDER: Improved Succinct Rank and Select Performance" to summarize and improve on state of the art
"Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors"
"A Fast x86 Implementation of Select"
And Vigna's seminal broadword paper with rank9, select9, and simple-select is still a very good start.
On the implementation side of things we now have POPCNT and PDEP hardware instructions on x86 and it looks like rank and select within a cache line of 64 bytes are best handled with repeated popcounts and it's not even worth anymore precomputing. This is where theory and practice meets.
Overall a solid book for an introduction and as a reference - but make sure to keep up with latest developments in this moving field.
Displaying 1 of 1 review
Can't find what you're looking for?
Get help and learn more about the design.