Read Efficient Data Structures

Frank Rosner on April 29, 2018

Introduction The previous blog post introduced the RUM conjecture. It describes the trade-off between read (RO), update (UO), and memo... [Read Full]
markdown guide

Great post Frank! I've read your article with a pleasure. Nowadays developers which are working with objective languages like C# or Java are now aware what mechanism are placed behind HashSet built-in type. Your post explains how the algorithms are working, their pros and cons and last but not the least the comparison with build type in Java. Great work. I'm waiting for rest articles from the series.


Thank you so much Rafal. I already started working on the next part so stay tuned :)


This is really a great post, i enjoyed reading it (Waiting with passion for the coming posts) but i really find it very abstract using the RUM conjecture as a metric. I didn't make any research about this notion (that is new to me) but i don't know whether there is a quantitative approach to this notion or it is just a conceptual model (unlike complexity that have very well defined computational model). Just one request Frank, is it possible for you to write about concurrent data structures that are widely used in industry ? Thank you.


Hi Karim! Glad you enjoyed the post.

I stumbled upon the RUM paper and I also didn't hear about it before. I think the conjecture is more a conceptual model. However it helped me to look at different data structures and their design from a different angle. The fact that you can "optimize" the design for the different overheads makes trade-offs more visible.

Also the paper contains a lot of references to other papers that I added to my reading list, triggering the blog post series.

Regarding the request for a post about concurrent data structures, I added it to my todo list :)


It was a bit to long for my taste. A serie would have been better.


Thanks for the reply! I agree with you it turned out to be longer than optimal. It is already part of a series though and I wanted to dedicate one post for each of the overheads (read, update, memory). The next ones are shorter so let me know what you think :)

code of conduct - report abuse