I think many complaints about peer review and publication decisions stem from a basic misunderstanding that goes something like this: I did good science, I wrote it up, and now my peers will read the paper and decide whether the underlying science is good. The mistake is treating “the science” as the product and the paper as its container. The paper is the product, with the purpose of…
How do modern columnar database management systems process a query like this? SELECT SUM ( t . c ) FROM t WHERE t . a > 5 AND t . b < 7 ; Columnar systems today are generally either use compiling query engines or vectorized query engines. Compiling query engines generate code that executes the query, allowing tools like LLVM to optimize queries “end to end.” Vectorized query engines use…
I was excited to see that Neo, the ne ural query o ptimizer , got its 600th citation! It’s nice to have a quantification, but what I’m most proud of is the impact Neo had on the research community. Neo was simultaneously the last paper of my PhD at Brandeis and the first paper of my postdoc at MIT. Working with my advisor Olga and then-1st-year-PhD student Chi at Brandeis, along with Mohammad ,…
From database companies to renowned professor of databaseology Andy Pavlo , everyone seems to be writing their “year in review” of the database world. While I could never match Andy’s wit nor his no-doubt earnest adoration for Larry Ellison, I thought I might be able to provide some additional insights into the hottest topics in database research from a bibliometric perspective. For the past few…
This tool takes your paper’s title and abstract, and searches past VLDB, PODS, SIGMOD, and CIDR papers for potential related work. Obviously, this tool does not replace a thorough literature review, but it can help you find papers you might have missed. Names that are highlighted are on the VLDB or SIGMOD program committee. Search related work Title: Abstract: Recent advancements in learned index…
As a query optimization researcher, I’ve spent the last 10 years of my life playing with, learning from, and building on top of the most sophisticated open source query optimizer out there, PostgreSQL . I recently wondered how much PostgreSQL had improved over the decade since I started working on databases. While changelogs and opinion pieces were plentiful, I couldn’t find any strong empirical…
Ever wondered which database systems papers have been the most influential? This page explores the PageRank of a paper in the citation graph, one possible measure of influence. This blog post has been replaced by DBScholar , which uses its own metadata extraction pipeline instead of the (now defunct) APIs used in this post. All rankings, including this one, codify an ideology and thus won’t match…
Update March 19th, 2024: this page now uses the gpt-3.5-turbo model. It’s the holiday season of 2022, and everyone is talking about large language models! OpenAI’s GPT-3 and others are generating quite a bit of interest in the CS research community. Larger datasets and models are significantly improving results on many NLP tasks. Even in databases (my field), large language models are being used…
This post was also published on the MIT DSAIL blog . A good portion of my postdoc at MIT has been spent developing Bao , a system for learned query optimization with an eye towards practicality. Bao was recently published at SIGMOD 2021, where we were thrilled to receive a best paper award . In our paper, we show how Bao can be applied to the open-source PostgreSQL DBMS , as well as an unnamed…
Imagine you are writing a system to repeatedly sort large datasets. You could just blindly choose a search algorithm, like Quicksort, and apply it every time. However, if the data is nearly sorted already, something like bubble sort or insertion sort might be a better idea. But how do we know when this is the case? One approach would be to sample the data and compute some statistics over it, like…
Having spent five years heavily involved in teaching the 2nd semester programming course at Brandeis, I’ve found myself repeating the same maxim over and over again: Code is an essay written for two audiences: the computer, and your fellow programmers. Thinking about the dual-audience nature of code immediately highlights several important aspects of “good code”: When “read” by the computer, good…
Consistent hashing was first proposed in 1997 by David Karger et al. , and is used today in many large-scale data management systems, including (for example) Apache Cassandra . Consistent hashing helps reduce the number of items that need to be moved from one machine to another when the number of machines in a cluster changes. The basic idea is to use two hash functions 1 – one, , which maps each…
Perlin noise can be used to create some interesting and fun visual effects, like the image below (click for high resolution): The above image was created by interpreting each point in 2D Perlin noise as an angle in a vector field, and then tracing particles through the resulting vector field. Each pixel is colored based on its flux. In order to explain how it is built, we’ll go over the basics of…
Sometimes, the perfect version of something is too perfect. Consider two drawings of a cube shown below. Redraw The left-hand side cube is generated exactly as you’d expect – by drawing a number of straight lines. The cube on the right-hand side, however, is generated using an algorithm from Meraj et al.’s 2008 paper, Mimicking Hand-Drawn Pencil Lines . This work may seem entirely unmotivated;…
Machine learning problems often require a kernel function that measures the similarity between two different input vectors, and . Such kernel functions can enable linear algorithms (like SVM, PCA, and k-means) to find non-linear solutions to classification, regression, or clustering problems. Normally, a kernel function is selected from a standard set (although the most common by far appears to be…
Statistics and machine learning techniques for data smoothing have been around for a long time. The idea is to take a noisy function or noisy data and build a function that approximates the important patterns of the data, but omits the noise. Generally, the smoothed function that results is easier to analyze, sometimes because it is differentiable or integrable. Below is a demo of one such data…
Mathematicians have been trying to figure out how to get computers to write proofs for a long time . One of the earliest (dating back to the 1960s) attempts to do so was a logical rule called resolution . I created Vulcan, an NPM package that implements a resolution-based automated proof system. Below is a in-browser demo I created with AngularJS and Browserify . You can use symbols A-Z as…
Might I interest you in a rousing game of Connect Four ? You and the computer take turns dropping discs into one of the seven colums below. The goal is to get four pieces of your color in a row (vertically, diagonally, or horizontally). Winner: none yet... Player {{winner}} Draw: no yes Moves to to think ahead That’s an AngularJS powered Connect Four AI that was originally written in C and then…
I’ve written a parser that does its best to parse invalid and malformed JSON . It is written in JavaScript, and is available on NPM . There’s also an online demo . Why? Recently, I had the unfortunate job of parsing some malformed JSON. This particular JSON had a lot of embedded HTML and newlines, and looked something like this: { "key": "<div class="item">an item with newlines <span…
While reviewing my database theory textbook , I stumbled across a few algorithms for relational schema decomposition and database normalization . Aside from a dead project on Google Code and a buggy and apparently closed-source implementation hosted at the University of Illinois , I couldn’t really find any implementations or libraries implementing these algorithms. So, I created rdtheory.js and a…
In many applications, such as a median filter , we want to sort a small ( ) set of numbers. In the case of the median filter, we are only concerned with sorting sets of one exact size – if this is the case, one can generate an optimal sorting network using a tool like this one to create a provably-unbeatable solution. However, often we want to be able to sort sets of varying size that are still…
Recently, I came across a problem in which I had to store contacts in an instant message application. I needed to be able to display the list of contacts to the user in alphabetical order, and I needed to be able to retrieve a contact object quickly. One data structure that accomplishes all this is a simple binary tree – an in-order traversal of the tree will produce the list of contacts in…