Comment by williamkuszmaul | Hacker News Reader

Comment by williamkuszmaul | Hacker News Reader

Parent Full thread

williamkuszmaul

For perspective, here are some examples of other data structures in the past 35 years that are fundamentally new. (I am only including data structures that differ significantly from their predecessors)

B-epsilon trees: These allow asymptotic speedups for insert/update/delete operations on search trees in external memory (Introduced in 2002 by the paper, Lower Bounds for External Memory Dictionaries)

Cache-Oblivious B-Trees: This is an external-memory search tree that exhibits optimal behavior on a cache with any (possibly unknown) cache-size and cache-line size parameters. (Introduced in 2000 by the paper Cache-Oblivious B trees)

Fusion trees: This allows for search operations in a small binary tree (i.e., a tree whose size is polynomial in the machine word size) to be performed in constant time, rather than logarithmic time. (Introduced in 1990 by the paper Blasting through the Information Theoretic Barrier with Fusion Trees.)

Cuckoo hashing: This is a hash table design introduced in 2001. In 2009, the paper De-amortized Cuckoo Hashing showed how to make all operations in Cuckoo hashing take truly constant time with high probability. This remains (as far as I know) the only known technique for guaranteeing constant-time operation for a hash table without the use of bit manipulation tricks or the method of four Russians.

These are just examples off the top of my head. I'm sure there are many more.

Also, I would say the whole concept of https://en.wikipedia.org/wiki/Succinct_data_structure is fundamentally new. (And looking at citations, they are not yet 35 years old.)

I agree. Related to this, sketches (i.e., small data structures that can be used to recover information about large data sets) are also fundamentally new (and most of the techniques are from the 21-st century).

Confluent/persistent data structures, which I believe was novel research by Chris Okasaki in the late 90s (at least that’s when I first heard of it -- I was in CS academia at the time).

Edit to add: I’m not a Clojure expert, but I believe you could trace a direct line to Clojure’s core immutable data structures from Okasaki’s doctoral thesis. But maybe I’m wrong! Would love to hear about another other takes on this or links to other research strands I’m not aware of.

The term 'persistent data structure' goes back to papers by Tarjan, et al in the 80s but the path copying technique is much older. My favorite technique from one of those papers, the in-place v2 trick, is an alternative to path copying that achieves amortized O(1) space per update as opposed to O(depth) space per update for path copying; this only gives you partial persistence (linear history like an MVCC database system, not branching history like a purely functional data structure or Git) but often that's all you need. (There's also an extension of the trick to full persistence but it's not very practical.)

> I’m not a Clojure expert, but I believe you could trace a direct line to Clojure’s core immutable data structures from Okasaki’s doctoral thesis.

I believe the direct inspiration for Clojure's persistent vectors and maps are Bagwell's papers on HAMTs, which weren't so much a new data structure as an example of data structure engineering. Okasaki's thesis has several contributions but its main theme is how you can apply amortization in the purely functional setting if you have laziness or memoization, which is in a very different direction.

Thank you! So I was looking at it from a purely functional point of view, without accounting for the earlier non-pure work in the literature. That makes sense; I was deep in the early Haskell world at the time.

Suffix Arrays: with their meanwhile linear time construction they allow for very efficient pattern matching, indexing and more efficient compression algorithms. (introduced around 1990 https://en.wikipedia.org/wiki/Suffix_array)

It's an important theoretical result, but the optimized library almost everyone uses (libdivsufsort) is based on an O(n log n) time algorithm; I haven't seen any competitive implementations of the linear-time algorithms.

Another example is locality sensitive hashing (introduced in late 1990s), which can be used as a data structure to efficiently solve the nearest-neighbor problem.

There's Judy arrays too, I'm not sure if it's already included in one of those data structures.

Cache-Oblivious B-Tree is a variant of B-Tree The title says "fundamentally new"

No, cache-oblivious B-trees are not a variant of B-trees (although I can see why you might think the name suggests that). I classify them as fundamentally new because they technique they introduce was fundamentally different than past data structures. (Their fractal-like layout allows for them to achieve optimal behavior on an arbitrarily parameterized cache.)

You remember the dates of when these data structures were first published off the top of your head? Are you a computer science professor?

A quick google shows that the OP is indeed in academia.

Oh. Well that's pretty impressive. I typically don't look up people's usernames on the site, but I guess I should more often.

Reply on news.ycombinator.com