What Data Structure or Algorithm’s Invention Sped Up a Certain Task Significantly?

Rate this post

In a way, most new algorithms either solved a previously unsolved problem or improved efficiency (in terms of memory overhead, speed, or other characteristics) of the previous solution.

This is the fundamental cycle of scientific research.

The binary tree data structure sped up database lookups significantly. Later B-Trees did the same thing.

Dijkstra’s algorithm sped up shortest path computation in 1956. 50 years later, a German research group published a paper with the idea of “transit-node routing” which accelerates shortest path computation by orders of magnitude in comparison to Dijkstra’s algorithm. They again sped up shortest path computation. And so did thousands of other research papers which ultimately pushed down real-world shortest path computation on large road networks to the milliseconds.

Dive into any computer science area and you will find a plethora of algorithmic improvements in terms of runtime and efficiency.

Leave a Comment