Algorithms and data structures

Handy algorithms and data structures – e.g., for approximations

The Log-Structured Merge-Tree (LSM Tree)

~ Adrian Colyer ~ 3 Comments
The Log-Structured Merge-Tree (LSM Tree) - O'Neil et al. '96. Log-Structured Merge is an important technique used in many modern data stores (for example, BigTable, Cassandra, HBase, Riak, ...). Suppose you have a hierarchy of storage options for data - for example, RAM, SSDs, Spinning disks, with different price/performance characteristics. Furthermore, you have a large ... Continue Reading

The Boom Hierarchy

~ Adrian Colyer ~ Leave a comment
The Boom Hierarchy - Bunkenberg In honour of the CodeMesh conference this week, and as recommended in a recent tweet by Eric Meijer, today's paper gives insight on some of our most fundamental data structures and the operations on them. The Boom Hierarchy is the family of data structures tree, list, bag, and set, to ... Continue Reading

Patience is a virtue

~ Adrian Colyer ~ 2 Comments
Patience is a virtue: revisiting merge and sort on modern processors - Chandramouli and Goldstein 2014 This is a wonderful story. The seeds of an algorithm laid down over 50 years ago, rediscovered, brought up to date, and found to be highly relevant. Our investigation has resulted in some surprising discoveries about a mostly ignored ... Continue Reading