3 ms·

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 diff

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.

js8 6y ago
Also, I would say the whole concept of https://en.wikipedia.org/wiki/Succinct_data_structure https://en.wikipedia.org/wiki/Succinct_data_structure is fundamentally new. (And looking at citations, they are not yet 35 years old.)
- williamkuszmaul 6y ago
  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).
  - iainmerrick 6y ago
    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.
    - psykotic 6y ago
      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.
      - iainmerrick 6y ago
        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.
dmoldavanov 6y ago
Cache-Oblivious B-Tree is a variant of B-Tree The title says "fundamentally new"
- williamkuszmaul 6y ago
  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.)
williamkuszmaul 6y ago
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.
ajfjrbfbf 6y ago
There's Judy arrays too, I'm not sure if it's already included in one of those data structures.
root_axis 6y ago
You remember the dates of when these data structures were first published off the top of your head? Are you a computer science professor?
- boyobo 6y ago
  A quick google shows that the OP is indeed in academia.
  - root_axis 6y ago
    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.
froh 6y ago
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 https://en.wikipedia.org/wiki/Suffix_array)
- psykotic 6y ago
  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.

js8 6y ago

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

williamkuszmaul 6y ago
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).
- iainmerrick 6y ago
  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.
  - psykotic 6y ago
    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.
    - iainmerrick 6y ago
      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.

dmoldavanov 6y ago

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

williamkuszmaul 6y ago
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.)

williamkuszmaul 6y ago

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.

ajfjrbfbf 6y ago

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

root_axis 6y ago

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

boyobo 6y ago
A quick google shows that the OP is indeed in academia.
- root_axis 6y ago
  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.

froh 6y ago

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 https://en.wikipedia.org/wiki/Suffix_array)

psykotic 6y ago
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.