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

61–70 of 131 posts

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

#61

Post by nickpsecurity »

CalChris wrote: post #18

seL4: Formal Verification of an OS Kernel (from 2009). https://www.sigops.org/sosp/sosp09/papers/klein-sosp09.pdf seL4 is about 9000 LOC. So this gives a good indication of what formal verification (Isabelle/HOL) is currently capable of. seL4 is also quite fast as a result of removing unnecessary checks. https://sel4.systems/ seL4 is smaller than L4Ka::Pistachio and it's also capability based which L4 isn't. They cou…

Note that this is formal verification of an imperative, C-based program manipulating low-level structures done years ago. I wouldnt say that represents what we're currently capable of in general case. For starters, a functional program or imperative without pointers (eg in SPARK) is much easier to verify than a C program. Plus, the seL4 organization recently reduced effort for filesystems down by a few multiples with a functional language.

Truth is the seL4 team set themselves up for a harder-than-usual job. For good reason but most folks (esp managed languages) won't see as much difficulty.

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

#62

Post by sova »

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

Yo! This is what I'm talkin' about! Replace directories with self-consistent neural nwots [neural blackbox thingie of weights and activation vals]. It's cool, but for every convenience we take in the direction HD space we backpeddle in processing [meaning, although the dir structure could be super condensed this way with a learned index, this approach is less flexible to cold or not-cpu-related analysis]. It's very cool actually to consider the three branches of processing, hdd, and memcache ... You want to have a balance but in the ideal computer we do no calculation, and that is something worth mentioning.

Reading again of the abstract, allow me to add that it's an optimization beyond structures such as Btrees which are already not really decipherable datasets to the naked eyes. So any optimization in a space that's not designed to be human-legible can take whatever shape, and this is certainly a welcome achievement!

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

#63

Post by oh-kumudo »

catnaroek wrote: post #39
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?

Data warehousing is one obvious application: data is immutable; have a sort key. So NN as a builtin once index structure is perfect for such case. It is only a matter of time for commercial analytic DB to pick up this idea, I would presume.

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

#64

Post by beefman »

Programming languages

Slepak et al - An Array-Oriented Language with Static Rank Polymorphism [1]

Distributed systems

Kiayias et al - A Provably Secure Proof-of-Stake Blockchain Protocol [2]

Cognitive computing

Boahen - A Neuromorph's Prospectus [3]

Machine learning

Silver et al - Mastering Chess and Shogi [4]

1 http://www.ccs.neu.edu/home/shivers/papers/rank-polymorphism...

2 https://eprint.iacr.org/2016/889.pdf

3 https://pdfs.semanticscholar.org/3767/1e53c9949fa08d9dc150ad...

4 https://arxiv.org/pdf/1712.01815.pdf

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

#65

Post by catnaroek »

sulam wrote: post #41
catnaroek wrote: post #39

Earlier quoted context omitted.

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?

There are immediate applications to data warehousing. I hope that's obvious to you, but if not I'm happy to unpack that. Whether or not it applies to online databases probably depends on several factors. The ones I can think of off the top of my head are the read/write ratio, the write rate in general, and obviously size of your data set (although the approach works at GB, not TB, so most can take advantage). Here's…

> There are immediate applications to data warehousing.

I am not too worried about data warehouses. Data warehouses can be fed by batch processes, which you can run, say, once every day or once every week. This leads to the design of algorithms that optimize aggregate measures of performance (e.g. amortized complexity, average complexity, throughput) rather than microscopic measures of performance (e.g. worst-case complexity, latency). Machine learning techniques have a track record of delivering good aggregate results.

However, online databases require optimal worst-case performance. The occasional massively slow operation is not okay - we'd rather every operation be a tiny bit slower instead.

> Do I have any indexed queries? If not, nothing to do here.

Of course I do. Needless to say, complex schemata come with lots of indices that are necessary to speed up queries that pull data from 10-15 tables each.

> Does the data change rapidly? If so, nothing to do here.

Of course the data changes rapidly. Crucially, an online transactional database's input comes from external parties (e.g., public-facing web servers) that cannot be considered trustworthy. Many machine learning techniques are vulnerable to so-called “adversarial examples”. Feeding adversarial examples to an ML-powered index could cause the database's performance to drop drastically in ways that are provably not possible with B-trees.

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

#66

Post by travmatt »

juanmirocks wrote: post #58
godelmachine wrote: post #54

Earlier quoted context omitted.

1) The Morning Paper - blog.acolyer.org - A new super interesting paper review everyday 2) This is my personal ritual. Every weekday I check out recent entries in "Hardware architectures" and "Emerging Technologies" section of arXiv.org Many other sections are gaining traction with me, like Database. Hope this helps.

Thank you for The Morning Paper

You'd also like Fermat's Library

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

#68

Post by robotresearcher »

Eridrus wrote: post #44
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…

The article you link ends on a pretty weak claim, math didn't obsolete biologists and ML won't obsolete systems folks, but every time you write a heuristic you would probably get better results from a model.

A heuristic is a model. A successful heuristic encodes knowledge of the distributions at hand. Heuristics are designed by people who had good insight into the data rather than learned directly from data, but they are models in the same sense.

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

#69

Post by sulam »

catnaroek wrote: post #65
sulam wrote: post #41

Earlier quoted context omitted.

There are immediate applications to data warehousing. I hope that's obvious to you, but if not I'm happy to unpack that. Whether or not it applies to online databases probably depends on several factors. The ones I can think of off the top of my head are the read/write ratio, the write rate in general, and obviously size of your data set (although the approach works at GB, not TB, so most can take advantage). Here's…

> There are immediate applications to data warehousing. I am not too worried about data warehouses. Data warehouses can be fed by batch processes, which you can run, say, once every day or once every week. This leads to the design of algorithms that optimize aggregate measures of performance (e.g. amortized complexity, average complexity, throughput) rather than microscopic measures of performance (e.g. worst-case co…

So, would you take a bet that this won't have been used in any self-evident way within the next 5 years?

Because I would take the other side of that bet. :)

Post reply on HN