8 ms·
The Periodic Table of Data Structures [pdf]
- nissarup 8y agoI want that read/write/space-optimized triangle prominently featured in every languages documentation, filled in with the different data stuctures from that language. Need quick reads? Use Y. Quick writes? Use X. Etc.
- deleted 8y ago[deleted]
- mlevental 8y agobe the change you want to see in the world :)
- zawerf 8y agoI think I saw it popularized as the "RUM Conjecture" on HN a while back: https://medium.com/databasss/on-disk-storage-part-4-b-trees-30791060741 https://medium.com/databasss/on-disk-storage-part-4-b-trees-... http://daslab.seas.harvard.edu/rum-conjecture/ http://daslab.seas.harvard.edu/rum-conjecture/
- tedd4u 8y agoSame authors as the OP btw: Manos Athanassoulis Postdoctoral Researcher Michael S. Kester Graduate Researcher Lukas Maas Graduate Researcher Stratos Idreos Assistant Professor of Computer Science
- sytelus 8y agoThis is very inspirational but not sure if this is done in the best way. The core value of Mendeleev's approach is to find gaps and predict things that should exist but we haven't found yet. However for this to happen, one must isolate the "atoms" that can't be further broken down and identify the pattern in these atoms. The periodic table created in Figure 4 of this paper doesn't exactly sounds like isolation of "atoms" of data structures.
- esturk 8y agoYou're right based on the modern day thinking of what the periodic table is but you're wrong to suggest that people knew what they were doing from the very start. The formulation of the periodic table is quite like modern day data science. Chemists even before Mendeleev observed patterns and tried to build a model to predict missing ones. The beauty is that this was done without understanding the underlying mechanism of how it all worked, ie what makes an element (protons), what makes their periodicity (electrons). That came 50+ years later when we discovered protons and electron orbitals. So going back to the article, their approach is fine because they're just formulating some model from observed patterns. Their reasoning for the underlying mechanism could be completely wrong but that's fine too until a better model comes along.
- whatshisface 8y ago>The formulation of the periodic table is quite like modern day data science. That's because data science is just science. The only distinction is that you're studying somebody's sales pipeline instead of the secrets of the universe.
- Sirupsen 8y agoI am fascinated with unifying theories such as the periodic table (Mendeleev's) and the Copernican view of planets orbiting the sun. The previous, Earth-centric model had more deviations than predictive power. The periodic table is also an example of a structure with tremendous predictive power. I think it's also interesting to distinguish between systems that reveal intrinsic order (e.g. periodic table), and systems that superimpose external order (e.g. a performance review framework). Behavioural economics is an example of a field that desperately needs a modern-day equivalent of Mendeleev to come around and structure. I am craving more examples of this, please, anyone, share!
- kopo 8y agoThey removed the image from the main article for some reason but I thought this was cool - https://en.wikipedia.org/wiki/File:The_Cognitive_Bias_Codex_-_180%2B_biases,_designed_by_John_Manoogian_III_(jm3).png https://en.wikipedia.org/wiki/File:The_Cognitive_Bias_Codex_...
- sheikheddy 8y agoShould "Data Structures" be followed with "is"? I was under the impression that since it's plural, we'd have an "are".
- posterboy 8y agoYes, absolutely. Why do you have to ask? Unless '-s' is its genetive inflection, something German for example has preserved, or something weirder, it is a crystal clear mistake
- hmyr1 8y agoIn this case, yes. > This is why many argue that research on algorithms and data structures is "is" refers to "research", not "data structures"
- fhars 8y agoThe sentence in question is > Data structures is how we store and access data. wich is arguably just a bad sentence.
- coldtea 8y agoBut not quite incorrect.
- addicted 8y agoThe grammar is still correct if the reference here is to data structures as a singular group which is actually what the sentence appears to do.
- dahart 8y agoWhether it’s correct or not, it’s not a great sentence, and would benefit from a rewrite. Language is weird sometimes, so I’m not certain, but your argument seems circular and incorrect. Use of ‘is’ doesn’t cause ‘data structures’ to be singular a collective noun. The noun is plural, so the correct verb is ‘are’. The sentence would need to name the singular collective in order to use ‘is’. For example: “A set of data structures is how we store and access data.” That would be correct. Arguing that “Hard disks is how we store and access data” is correct and that “hard disks” is a singular collective noun, because the sentence used ‘is’, is not normally accepted grammar.
- wiz21c 8y agoReminds me of GoF patterns (the approach), but the result here seems more pedagogical...
- gralx 8y agoHere's the citation from parent link seas.stratos.harvard.edu: S. Idreos, et al., “The Periodic Table of Data Structures,” Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, vol. 41, no. 3, pp. 64-75, 2018.
- rrk4n0 8y agoAbout the gaps """Mendeleev was a friend and colleague of the Sanskritist Böhtlingk, who was preparing the second edition of his book on Pāṇini[47] at about this time, and Mendeleev wished to honor Pāṇini with his nomenclature.[48] Noting that there are striking similarities between the periodic table and the introductory Śiva Sūtras in Pāṇini's grammar""" More: https://en.wikipedia.org/wiki/Dmitri_Mendeleev https://en.wikipedia.org/wiki/Dmitri_Mendeleev
- russfink 8y agoI see Tarjan cited but no Sedgewick, or CLRS. I'm against obsequious citations, so I'll give the benefit of the doubt that these aren't needed.
- bonzini 8y agoIsn't CLRS mostly a secondary source that puts together previous literature? Citations usually prefer a primary source that lets you place a "discovery" accurately in date and place (aka conference/journal).
- thrower123 8y agoCLRS is wildly overrated; it's got a lot of odd gaps in the data structures that it does cover, and wastes a lot of time and space on esoteric junk.
- hyuyuyyyu 8y agohhhghjghhjghgghghhjgjhghghgh
- ape4 8y agoYou could make a periodic table of many things. Websites, languages, databases, etc. Maybe some new ideas could be uncovered.
- aeneasmackenzie 8y agoA few months ago I saw a program like this that would derive a data structure for you based on what operations you wanted to perform (inserts and queries, for example) but I haven't been able to find it again.
- novaleaf 8y agosounds interesting! if you find it again, plz post
- aratno 8y agoIs this the one you’re thinking of? https://blog.acolyer.org/2018/06/21/generalized-data-structure-synthesis/ https://blog.acolyer.org/2018/06/21/generalized-data-structu...
- aeneasmackenzie 8y agoThat's it! Thank you.
- justin66 8y agoI was reminded slightly of the taxonomy of abstract data types (as opposed to data structures) that appears in Sally Goldman's A Practical Guide to Data Structures and Algorithms using Java: https://books.google.com/books?id=xT8qBgAAQBAJ&lpg=PP1&dq=A%20Practical%20Guide%20to%20Data%20Structures%20and%20Algorithms%20using%20Java&pg=PA22#v=onepage&q=A%20Practical%20Guide%20to%20Data%20Structures%20and%20Algorithms%20using%20Java&f=false https://books.google.com/books?id=xT8qBgAAQBAJ&lpg=PP1&dq=A%...
- bordercases 8y agoThe generalized form of the "Periodic Table" is the Morphological Analysis. http://www.swemorph.com/ma.html http://www.swemorph.com/ma.html Most of the theoretical work is in picking the right properties that expose the right trade-offs. Beyond that, the method is deceptively simple.
- DoctorOetker 8y agothis is probably off topic, but I've waited before asking until I found the closest topic from my perspective: A while back (order months or years but certainly within last 2 years) someone mentioned a paper, I believe it was here on HN either as the topic or in a comment, but perhaps it may have been on IRC. I am no longer able to find back this paper, and have only a vague recollection of it (I had read the abstract and the introduction and then postponed reading until I forgot about it). It dealt with the problem of say 2 peers each having their own list or set, and part of their list is in common, but both may also have entries the other doesn't have. The problem was finding the most efficient way such that both end up with the union of both lists or sets. A brute force way would be to each send a copy of their list to the other, a slightly less brute way would be to have only one send a full copy, and have the other return his difference. But the paper detailed a more efficient method, which obviously I can't remember... Does this description ring a bell? Does anyone know the paper I am trying to locate?
- jpitz 8y agoThis isn't new, and doesn't answer that part of your question, but a Merkle Tree is a solution to that problem that can avoid sending the entire set.
- toolslive 8y agohttps://ieeexplore.ieee.org/document/1226606?reload=true&part=1 https://ieeexplore.ieee.org/document/1226606?reload=true&par...
- the8472 8y agoOne way to do this is to send a bloom filter as index and then return the elements that are not part of the bloom filter.
- jpitz 8y agoBut what about the false positives?
- 8y ago
- platz 8y agoA Cartesian product is not a periodic table
- killjoywashere 8y agoIf this works, a universal method to an exact solution for all differential equations would be on there. Good luck with that.