{"id":19801,"date":"2017-12-11T15:46:39","date_gmt":"2017-12-11T20:46:39","guid":{"rendered":"https:\/\/mjtsai.com\/blog\/?p=19801"},"modified":"2018-01-14T16:44:51","modified_gmt":"2018-01-14T21:44:51","slug":"the-case-for-learned-index-structures","status":"publish","type":"post","link":"https:\/\/mjtsai.com\/blog\/2017\/12\/11\/the-case-for-learned-index-structures\/","title":{"rendered":"The Case for Learned Index Structures"},"content":{"rendered":"<p><a href=\"https:\/\/twitter.com\/schrockn\/status\/940037656494317568\">Nick Schrock<\/a>:<\/p>\n<blockquote cite=\"https:\/\/twitter.com\/schrockn\/status\/940037656494317568\">\n<p>Jeff Dean and co at GOOG just released a paper showing how machine-learned indexes can replace B-Trees, Hash Indexes, and Bloom Filters. Execute 3x faster than B-Trees, 10-100x less space. Executes on GPU, which are getting faster unlike CPU. Amazing.<\/p>\n<\/blockquote>\n\n<p>The paper is <a href=\"https:\/\/www.arxiv-vanity.com\/papers\/1712.01208v1\/\">here<\/a>, and there&rsquo;s also <a href=\"http:\/\/learningsys.org\/nips17\/assets\/slides\/dean-nips17.pdf\">a presentation<\/a> (via <a href=\"https:\/\/news.ycombinator.com\/item?id=15892956\">Hacker News<\/a>).<\/p>\n\n<p>Update (2018-01-08): See also: <a href=\"https:\/\/blog.acolyer.org\/2018\/01\/08\/the-case-for-learned-index-structures-part-i\/\">Adrian Colyer<\/a>.<\/p>\n\n<p>Update (2018-01-09): See also: <a href=\"https:\/\/blog.acolyer.org\/2018\/01\/09\/the-case-for-learned-index-structures-part-ii\/\">Adrian Colyer<\/a>.<\/p>\n\n<p>Update (2018-01-14): <a href=\"http:\/\/dawn.cs.stanford.edu\/2018\/01\/11\/index-baselines\/\">Peter Bailis et al.<\/a>:<\/p>\n<blockquote cite=\"http:\/\/dawn.cs.stanford.edu\/2018\/01\/11\/index-baselines\/\">\n<p>While learned indexes are an exciting idea for many reasons (e.g., they could enable self-tuning databases), there is a long literature of other optimized data structures to consider, so naturally researchers have been trying to see whether these can do better.<\/p>\n<\/blockquote>","protected":false},"excerpt":{"rendered":"<p>Nick Schrock: Jeff Dean and co at GOOG just released a paper showing how machine-learned indexes can replace B-Trees, Hash Indexes, and Bloom Filters. Execute 3x faster than B-Trees, 10-100x less space. Executes on GPU, which are getting faster unlike CPU. Amazing. The paper is here, and there&rsquo;s also a presentation (via Hacker News). Update [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"apple_news_api_created_at":"","apple_news_api_id":"","apple_news_api_modified_at":"","apple_news_api_revision":"","apple_news_api_share_url":"","apple_news_coverimage":0,"apple_news_coverimage_caption":"","apple_news_is_hidden":false,"apple_news_is_paid":false,"apple_news_is_preview":false,"apple_news_is_sponsored":false,"apple_news_maturity_rating":"","apple_news_metadata":"\"\"","apple_news_pullquote":"","apple_news_pullquote_position":"","apple_news_slug":"","apple_news_sections":"\"\"","apple_news_suppress_video_url":false,"apple_news_use_image_component":false,"footnotes":""},"categories":[],"tags":[1351,263,143,343],"class_list":["post-19801","post","type-post","status-publish","format-standard","hentry","tag-artificial-intelligence","tag-theory","tag-database","tag-search"],"apple_news_notices":[],"_links":{"self":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/19801","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/comments?post=19801"}],"version-history":[{"count":4,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/19801\/revisions"}],"predecessor-version":[{"id":20171,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/19801\/revisions\/20171"}],"wp:attachment":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/media?parent=19801"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/categories?post=19801"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/tags?post=19801"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}