Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: What was the best CS paper you read in 2017?

news.ycombinator.com

Post reply on HN
Print view View original

31–40 of 131 posts

Re: Ask HN: What was the best CS paper you read in 2017?

#31

Post by CaHoop »

AlexTelon wrote: post #23
sulam wrote: post #9

I highly recommend people give this paper a read. I think it points the way to a radical redesign of fundamental parts of the system stack over the next 5-10 years. If you work in systems and you aren’t thinking about this stuff, you’re about to be lapped. The Case for Learned Index Structures: https://arxiv.org/pdf/1712.01208v1.pdf

A very interesting read indeed! Besides HN how can one find great papers like this? How did you find out about it?

I saw this paper on reddit.com/r/machinelearning - usually the more interesting ML papers are posted there.

Additionally, there is http://www.arxiv-sanity.com/ which sorts new machine learning papers by popularity.

Re: Ask HN: What was the best CS paper you read in 2017?

#32

Post by ky3 »

Leslie Lamport's 1978 "State the Problem Before Describing the Solution" [0]. On his web page the author adds that "The title says it all. This one-page note is as relevant today as when I wrote it. Replace "describing the solution" by "writing the program" and it becomes a practical recipe for improving software."

Herewith, the paper in full:

"After several years of writing papers in computer science, I discovered the basic expository rule embodied in the title of this note. As obvious as this rule may seem, there are fields in which it is seldom observed. (Computer networking is one example.) A typical paper in such a field is organized as follows:

(1) a brief informal statement of the problem;

(2) the solution;

(3) a statement and proof of the precise correctness properties satisfied by the solution.

In order to abide by the rule, the following organization should instead be used:

(1) a brief informal statement of the problem;

(2) the precise correctness conditions required of a solution;

(3) the solution;

(4) a proof that the solution satisfies the requisite conditions.

Although it may not be obvious at first glance, there is a profound difference between these two approaches. In the first, the precise correctness conditions can be (and usually are) stated in terms of the solution itself. Some results are proved about the solution, but it is often not clear exactly what problem is being solved. This makes the comparison of two different solutions rather difficult. With the second approach, one is forced to specify the precise problem to be solved independently of the method used in the solution. This can be a surprisingly difficult and enlightening task. It has on several occasions led me to discover that a "correct" algorithm did not really accomplish what I wanted it to. I strongly urge everyone to observe the rule.

(I am ignoring as unworthy of consideration the disturbingly large number of papers that never even attempt a precise statement of what problem they are solving.)"

[0] https://lamport.azurewebsites.net/pubs/state-the-problem.pdf

Re: Ask HN: What was the best CS paper you read in 2017?

#33

Post by sulam »

chubot wrote: post #27
sulam wrote: post #9

I highly recommend people give this paper a read. I think it points the way to a radical redesign of fundamental parts of the system stack over the next 5-10 years. If you work in systems and you aren’t thinking about this stuff, you’re about to be lapped. The Case for Learned Index Structures: https://arxiv.org/pdf/1712.01208v1.pdf

I'm gonna throw some cold water on this and say this is not a new paradigm by any means. https://www.sigarch.org/the-unreasonable-ineffectiveness-of-... However, it's certainly possible that the time for this idea has come. Google is probably in the best position to apply it. I will say that after having worked at Google for over a decade, some of it on data center performance, there are plenty of inefficiencies that…

Have you seen the results when they let a trained model manage Borg? The power reductions were immediate, non-trivial, and performance stayed the same. There's your scheduling result for you.

Look at it this way. As the paper points out, a Hashtable is just a heuristic that works fairly well in the worst case and reasonably well in the average case. No one would argue that you couldn't hand-roll an algorithm that is better for a specific, narrowly defined data set. This paper is demonstrating that you don't have to do it by hand, you can train a model automatically without the expected caveats like: size (doesn't have to be huge), latency (the model trains very quickly) or specialized hardware (they used bog-standard CPUs, not GPUs or TPUs).

This is obviously just my opinion, but I think it's pretty big. It's not big because of the paper itself, although that's amazing in isolation (they improved on hashtables!). As I said above, it _points the way_. They have a throw-away sentence about co-optimizing data layout along with lookup and not showing those result. My guess is that beats a hashtable in every way. More importantly, if a model can beat bloom filters, b-trees, and hashtables, you'd better hold onto your socks because most algorithms are just waiting to fall. To me this paper is Deep Blue vs Kasparov. We all know what comes next.

Re: Ask HN: What was the best CS paper you read in 2017?

#34

Post by rgrieselhuber »

chubot wrote: post #27
sulam wrote: post #9

I highly recommend people give this paper a read. I think it points the way to a radical redesign of fundamental parts of the system stack over the next 5-10 years. If you work in systems and you aren’t thinking about this stuff, you’re about to be lapped. The Case for Learned Index Structures: https://arxiv.org/pdf/1712.01208v1.pdf

I'm gonna throw some cold water on this and say this is not a new paradigm by any means. https://www.sigarch.org/the-unreasonable-ineffectiveness-of-... However, it's certainly possible that the time for this idea has come. Google is probably in the best position to apply it. I will say that after having worked at Google for over a decade, some of it on data center performance, there are plenty of inefficiencies that…

Any resources you can recommend on the scheduling topic?

Re: Ask HN: What was the best CS paper you read in 2017?

#35

Post by trojanh »

indescions_2017 wrote: post #8

Bringing The Web Up To Speed With WebAssembly https://github.com/WebAssembly/spec/blob/master/papers/pldi2...

That link seems to broken. Here the original link https://github.com/WebAssembly/spec/raw/master/papers/pldi20...

Definitely a good read.

Re: Ask HN: What was the best CS paper you read in 2017?

#36

Post by chubot »

saycheese wrote: post #13

Does anyone have any suggestions on finding CS papers worth reading beyond those papers listed here?

Follow the citations of papers you liked. Note the authors and read their other publications.

Look at other papers in the same conference. Watch conference videos on YouTube.

Skim at first, and then reread papers that pop back into your mind.

Re: Ask HN: What was the best CS paper you read in 2017?

#37

Post by sulam »

rgrieselhuber wrote: post #34
chubot wrote: post #27

Earlier quoted context omitted.

I'm gonna throw some cold water on this and say this is not a new paradigm by any means. https://www.sigarch.org/the-unreasonable-ineffectiveness-of-... However, it's certainly possible that the time for this idea has come. Google is probably in the best position to apply it. I will say that after having worked at Google for over a decade, some of it on data center performance, there are plenty of inefficiencies that…

Any resources you can recommend on the scheduling topic?

I can't find the exact paper, but you can find a lot after reading this article popularizing the topic:

https://www.theverge.com/2016/7/21/12246258/google-deepmind-...

The future is here. :)

Re: Ask HN: What was the best CS paper you read in 2017?

#38

Post by sulam »

AlexTelon wrote: post #23
sulam wrote: post #9

I highly recommend people give this paper a read. I think it points the way to a radical redesign of fundamental parts of the system stack over the next 5-10 years. If you work in systems and you aren’t thinking about this stuff, you’re about to be lapped. The Case for Learned Index Structures: https://arxiv.org/pdf/1712.01208v1.pdf

A very interesting read indeed! Besides HN how can one find great papers like this? How did you find out about it?

I found this paper after reading through Jeff Dean's talk at NIPS. I recommend that, too, obviously!

http://learningsys.org/nips17/assets/slides/dean-nips17.pdf

You can generally find a paper for each section.

Re: Ask HN: What was the best CS paper you read in 2017?

#39

Post by catnaroek »

sulam wrote: post #9

I highly recommend people give this paper a read. I think it points the way to a radical redesign of fundamental parts of the system stack over the next 5-10 years. If you work in systems and you aren’t thinking about this stuff, you’re about to be lapped. The Case for Learned Index Structures: https://arxiv.org/pdf/1712.01208v1.pdf

I've read that paper, and I wasn't particularly impressed. Is there any concrete evidence that learned indices scale to databases with complex schemata and a large transactional volume? Could learned indices be profitably used, say, in the database backend of an ERP system?

Re: Ask HN: What was the best CS paper you read in 2017?

#40

Post by dekayed »

AlexTelon wrote: post #23
sulam wrote: post #9

I highly recommend people give this paper a read. I think it points the way to a radical redesign of fundamental parts of the system stack over the next 5-10 years. If you work in systems and you aren’t thinking about this stuff, you’re about to be lapped. The Case for Learned Index Structures: https://arxiv.org/pdf/1712.01208v1.pdf

A very interesting read indeed! Besides HN how can one find great papers like this? How did you find out about it?

I'd recommend taking a look at Papers We Love

https://github.com/papers-we-love/papers-we-love

Post reply on HN