Which data structures changed the world?
November 1, 2014 4:30 PM Subscribe
In my last question, I asked for algorithms that changed the world. Now I'd like to know, what are the data structures that changed the world?
I've always felt that how your input data is organized informs algorithm design, and so I want to know about the history of data structures as they emerged.
I'm not necessarily looking for 'structures every computer programmer should know' or the stuff we should teach in CS 101. A structure's impact on the world (and on the field) should be the primary criteria, rather than practitioner familiarity, or pedagogical use.
I've always felt that how your input data is organized informs algorithm design, and so I want to know about the history of data structures as they emerged.
I'm not necessarily looking for 'structures every computer programmer should know' or the stuff we should teach in CS 101. A structure's impact on the world (and on the field) should be the primary criteria, rather than practitioner familiarity, or pedagogical use.
Best answer: B-trees are at the heart of most modern databases.
Graphs explain everything from maps to routing problems to stochastic processes.
Bayesian networks turned what was previously considered completely intractable (probabilistic reasoning) and turned it into an efficient method for inference that now dominates AI.
posted by chbrooks at 4:54 PM on November 1, 2014 [1 favorite]
Graphs explain everything from maps to routing problems to stochastic processes.
Bayesian networks turned what was previously considered completely intractable (probabilistic reasoning) and turned it into an efficient method for inference that now dominates AI.
posted by chbrooks at 4:54 PM on November 1, 2014 [1 favorite]
linked list
posted by NoDef at 5:14 PM on November 1, 2014 [1 favorite]
posted by NoDef at 5:14 PM on November 1, 2014 [1 favorite]
+1 linked list
any contemporary data structures text will include the fundamentals: stack, queue, list, graph, tree (subtype of graph)...
not a data structure, but a method well matched to graph and tree traversal: recursion.
all the web monkeys you know can only think in lists and love associative arrays (lists with named elements). that's why json is so ubiquitous* - it does this plainly.
i once had to display an undirected graph in a ui. the pm *insisted* there was a root node, and that i always put that at the top of the ui "and make it like a tree." i have a headache in my eye.
* I know, it's also smaller than xml, and parses easier than xml (as long as string literals EVERYWHERE are your idea of style). web monkeys do not give a shit about message size.
posted by j_curiouser at 5:35 PM on November 1, 2014 [2 favorites]
any contemporary data structures text will include the fundamentals: stack, queue, list, graph, tree (subtype of graph)...
not a data structure, but a method well matched to graph and tree traversal: recursion.
all the web monkeys you know can only think in lists and love associative arrays (lists with named elements). that's why json is so ubiquitous* - it does this plainly.
i once had to display an undirected graph in a ui. the pm *insisted* there was a root node, and that i always put that at the top of the ui "and make it like a tree." i have a headache in my eye.
* I know, it's also smaller than xml, and parses easier than xml (as long as string literals EVERYWHERE are your idea of style). web monkeys do not give a shit about message size.
posted by j_curiouser at 5:35 PM on November 1, 2014 [2 favorites]
Best answer: Octrees are pretty fundamental to 3D graphics.
posted by equalpants at 5:37 PM on November 1, 2014
posted by equalpants at 5:37 PM on November 1, 2014
With data structures, I'd say there's less opportunity for world-changing revolution; it's pretty much just about about storing and accessing data, with the interesting bits being the algorithms that use them. Sure, you can find new ways to optimize for memory size, access speed, insert speed, etc, but I can't think of any structure that isn't some variation or combination of the classic arrays (hashtables, stacks, queues), linked lists (stacks, queues), trees (BST, B-tree, tries, heaps) or graphs (bayesian network).
posted by Aleyn at 6:11 PM on November 1, 2014 [1 favorite]
posted by Aleyn at 6:11 PM on November 1, 2014 [1 favorite]
Response by poster: Aleyn: "Sure, you can find new ways to optimize for memory size, access speed, insert speed, etc, but I can't think of any structure that isn't some variation or combination of the classic arrays (hashtables, stacks, queues), linked lists (stacks, queues), trees (BST, B-tree, tries, heaps) or graphs (bayesian network)."
I was thinking that might be the case, but I figured, viewed the same lense, most all 'algorithms that changed the world' were possible before, via brute force algorithms, so they too are just an optimization. Alternatively put, optimizations can be the difference between feasible and infeasible.
Also, crap, I just noticed I screwed up the title. =/ Mods, per chance?
posted by pwnguin at 6:19 PM on November 1, 2014 [1 favorite]
I was thinking that might be the case, but I figured, viewed the same lense, most all 'algorithms that changed the world' were possible before, via brute force algorithms, so they too are just an optimization. Alternatively put, optimizations can be the difference between feasible and infeasible.
Also, crap, I just noticed I screwed up the title. =/ Mods, per chance?
posted by pwnguin at 6:19 PM on November 1, 2014 [1 favorite]
Aleyn is completely correct. While I was busy trying to sound clever, that answer is really the key (when it comes to practical programming). I'm sure in math-y, or pure math domains, there are relationships that do not fit these common data structures.
I'd go further and say, what data structures describe is 'how the discrete units of data are related'. So if a novel type of relationship is being modeled (theoretical or physical), then a new/novel/composite data structure may be needed to accommodate it.
posted by j_curiouser at 7:01 PM on November 1, 2014
I'd go further and say, what data structures describe is 'how the discrete units of data are related'. So if a novel type of relationship is being modeled (theoretical or physical), then a new/novel/composite data structure may be needed to accommodate it.
posted by j_curiouser at 7:01 PM on November 1, 2014
Best answer: R-trees unlocked relatively inexpensive spatial queries, in exchange for much larger data storage requirements.
If you're looking for a physical data structure, I'd suggest the 4 byte + 4 byte IFF Chunk Type ID + Length structure, whic is similar to Mac's OSType or Windows' FourCC. This allows you to identify a file and its object structure with a very simple universal reader routine.
posted by scruss at 8:03 PM on November 1, 2014 [1 favorite]
If you're looking for a physical data structure, I'd suggest the 4 byte + 4 byte IFF Chunk Type ID + Length structure, whic is similar to Mac's OSType or Windows' FourCC. This allows you to identify a file and its object structure with a very simple universal reader routine.
posted by scruss at 8:03 PM on November 1, 2014 [1 favorite]
Best answer: Indexes, including library cataloging methods like the Dewey Decimal system and card catalogs. For that matter, books as a replacement for scrolls.
The DBMS as a whole.
The methods used for storage of data on magnetic media.
Encryption, storing data in a secure way.
The 80 column Hollerith card allowing fast sorts, etc.
The concept that programs are data, going back to Babbage.
ASCII.
Vector and raster methods of storing graphic data.
posted by SemiSalt at 6:40 AM on November 2, 2014 [1 favorite]
The DBMS as a whole.
The methods used for storage of data on magnetic media.
Encryption, storing data in a secure way.
The 80 column Hollerith card allowing fast sorts, etc.
The concept that programs are data, going back to Babbage.
ASCII.
Vector and raster methods of storing graphic data.
posted by SemiSalt at 6:40 AM on November 2, 2014 [1 favorite]
Best answer: I've always thought that the relatively recent emergence of hash tables as first-class data structures has been a boon to programmers. In the early days they were relatively rare, but now you can whip one up in a few keystrokes in most modern languages.
posted by schrodycat at 2:01 PM on November 2, 2014 [1 favorite]
posted by schrodycat at 2:01 PM on November 2, 2014 [1 favorite]
Best answer: This may sound dumb, but I remember how amazed I was the first time I saw data being entered into a Lotus 123 spreadsheet. Prior to that point, I had always thought of numbers in columns of individual digits, and you always had to make sure that the digits lined up underneath each other to perform large sums.
When I saw the concept of putting an entire value into a single column - Mind. Blown.
When later I saw Excel with a WYSIWYG view and that a column could expand/contract to fit the data that you put into it, AND that you didn't have to only put numerical digits in there - Wow. Just wow.
posted by CathyG at 1:40 PM on November 3, 2014 [1 favorite]
When I saw the concept of putting an entire value into a single column - Mind. Blown.
When later I saw Excel with a WYSIWYG view and that a column could expand/contract to fit the data that you put into it, AND that you didn't have to only put numerical digits in there - Wow. Just wow.
posted by CathyG at 1:40 PM on November 3, 2014 [1 favorite]
This thread is closed to new comments.
posted by doctor tough love at 4:33 PM on November 1, 2014 [3 favorites]