I know this doesn't really count, but the "Get me off your fucking mailing list" one made me giggle - http://www.scs.stanford.edu/~dm/home/papers/remove.pdf
Ask HN: What is your favorite CS paper?
261–265 of 265 posts
Re: Ask HN: What is your favorite CS paper?
#262Earlier quoted context omitted.
I'm happy to see this excellent paper mentioned. Fritz Henglein (the author) was my thesis supervisor last year, and I worked on developing some of his ideas further. In particular, I generalised discrimination (and added a touch of linear algebra) to devise a simple multi-way join algorithm that computes the join of any number of relations in optimal time (in a specific technical sense). Such results have been obtai…
Is there anything written about your multi-way join algorithm? We've done some really interesting implementations of Generic Join and the like and are always interested in hearing about other potentially better join algorithms.
It's only described in my thesis, which is not yet publicly available. (It should be, but the university thesis publication process seems to have a latency measured in years...)
The case for triangle joins is simple to describe, though. Suppose we have attributes A, B and C and finite maps (relations) R : A x B -> X, S : A x C -> Y and T : B x C -> Z. Now build tries for each so we have
abx : Trie A (Trie B X)
acy : Trie A (Trie C Y)
bcz : Trie B (Trie C Z)
We can join two tries using join : Trie k v1 -> Trie k v2 -> (v1 -> v2 -> v) -> Trie k v. Putting this all together we have:
triangleJoin : Trie A (Trie B (Trie C (X, Y, Z)))
triangleJoin = join abx acy (\bx cy -> join bx bcz (\x cz -> join cy cz (\y z -> (x, y, z))))
Compared to a database that doesn't know how to handle triangle joins the difference is absolutely stunning. The above one-liner managed to do in 5 seconds what took MySQL over an hour...
Re: Ask HN: What is your favorite CS paper?
#263I've been trying to get it frontpaged because, despite it's length, it's perhaps one of the most startling papers of this decade. Sadly, it seems like the HN voting gestalt hasn't decided to upvote a paper that's the CS equivalent of breaking the speed of light: "Generic Top-down Discrimination for Sorting and Partitioning in Linear Time" -> http://www.diku.dk/hjemmesider/ansatte/henglein/papers/hengl... (if you're d…
If I understand the talk correctly, this is just a way to assign objects a lazy list of shorts, and then sort them by that list using a recursive bucket sort.
I like his system for generating these lists when there's nested data. However, it's often as simple as concatenating the lists generated by the fields of the object.
The O(n) time bound isn't surprising to me, since each byte of information in the input can lead to at most one scan through the bucket array. Actual performance is obviously a lot better.
I'd still like to see this integrated into a more mainstream language. It would be an interface where all you have to implement is a generator that concatenates the generators of the fields of your class in the desired order.
I know how to do any combination of fixed-width numbers, structs, unions, strings, but I'm not sure how to handle tree-like structures, and something with cycles... I can't even think of a regular comparator for.
I assume this isn't this simple, so what am I missing?
Re: Ask HN: What is your favorite CS paper?
#264Earlier quoted context omitted.
Is there anything written about your multi-way join algorithm? We've done some really interesting implementations of Generic Join and the like and are always interested in hearing about other potentially better join algorithms.
It's only described in my thesis, which is not yet publicly available. (It should be, but the university thesis publication process seems to have a latency measured in years...) The case for triangle joins is simple to describe, though. Suppose we have attributes A, B and C and finite maps (relations) R : A x B -> X, S : A x C -> Y and T : B x C -> Z. Now build tries for each so we have abx : Trie A (Trie B X) acy :…
Is there any way I could get a preprint of your thesis?
I've been working on a project that sits somewhere between spark and riak and this actually might address a core issue I have both at the node and query dispatch level.
Re: Ask HN: What is your favorite CS paper?
#265Earlier quoted context omitted.
Given that I'm an ignorant. Can you ELI5 like what is the impact of this? What does it change? What can you do with it on practical terms?
Imagine that you make your living in a somewhat unorthodox but honest way: you live in a tent outside of the castle and every morning, as the king walks into the castle, he hands you a deck of cards. "I've just played cards last night," he says "and I'm going to again tonight, and I'd like these cards ordered and sorted by suite and number by this evening." Then the king goes into his castle and does whatever it is t…
er, given the specific example used, I would expect the wizard to say "look, you know exactly what the cards are, why don't you buy your own sorted deck of cards and staple them to the floor of your tent. Then when the king gives you a deck, just put each card on top of the matching one, then scoop them all up together in order." to which you would of course reply "but my tent is too small!", and the wizard would say "then just put down one of each number of one suit, plus the other 3 aces. Then pile all the cards on the aces first, just by matching suit, and finally take each of those piles in turn and do it by number."
Now, I haven't read the paper, but my guess is that the next objection is "but the king keeps switching the suits! Yesterday, they were diamonds, today they're little squiggly sketches of soft-serve poop! Which he pays me well enough to not think too hard about!" and the wizard would go on to explain that as long as you ask what the suits and numbers are in advance, you can make piles for them. Or something.
Sorry, usually I try to read papers before commenting, but I've gotta run -- I hear that whining noise that usually means my poop dispenser's jammed again.