Posts

SIPping and TIPping for faster search over sorted arrays

Image
Can you do better than binary search? TL;DR: Yes you can with our new algorithms SIP and TIP ;  and, not everything at SIGMOD/PVLDB has to be called ML-in-Systems! That was the question that two of my students Peter Van Sandt (a recent graduate from our BS program and the winner of David DeWitt Undergraduate Scholarship) and Yannis Chronis worked on over the last few years. It is a central question as searching over sorted in-memory arrays is a fundamental operation used in nearly every modern data platform. And, most of these platforms use some form of Binary Search ( BS ).  Interestingly, Interpolation Search ( IS ) has a better average-case complexity of O(log log N), but this result assumes that the data is uniformly distributed. Past attempts to use IS in any of less-than-ideal situation has generally not worked, leaving BS as the undisputed search method over sorted arrays.   We took a deeper look at this search problem in a paper that ...
Post a Comment
Read more

Graph Analytics: Simpler than we think?

Image
Graph analytics are all the rage today with companies rushing to build new software platforms that target just graph analytics all the time. But, are they really that different than many types of iterative data processing? Here we argue that for iterative graph processing, it is not. In fact, one can map BSP-style computation to the good-old relational algebra, with a few extensions for user-defined functions and the ability to express a loop. How can this be done? Consider the common BSP style vertex-centric computation.  The canonical graph analytics computation loop looks like this:   We can map this generic BSP computation to relational algebra using the following recipe. First, store the graph data in two relational tables, a nodes table (with one tuple for each node), and an edges table (with one edge tuple for each edge in the graph). Then, use the table below to map the BSP computation to relational algebra. Essentially in the relational syst...
Post a Comment
Read more

Introducing Ava

Recently we published a paper @ CIDR on a new system (called Ava ) that we are building here @ UW. SIGMOD invited me to write a blog, and that blog has just been published here . In a nutshell, we claim that many data science pipelines will be constructed by chatbots in the near future, and going further in the longer run conversational bots will allow end users to use natural language (both for Q&A) to directly get insights from their data.
Post a Comment
Read more

Quickstep is now part of Pivotal

In January, my students and I spun out a company to help commercialize the technology produced in the Quickstep project . I'm excited to announce that we have now been acquired by Pivotal. More details are here  and here .
1 comment
Read more

WideTable: An Accelerator for Analytic Data Processing

Image
Last year, I told you about BitWeaving , which is a compressed columnar scan that exploits intra-cycle parallelism. With BitWeaving, you can scan a table ... pretty darn fast! As part of the Quickstep project, Yinan and I have been wondering if we could expand the "sweet spot'' of the bare metal performance of BitWeaving to a wider variety of analytical query processing. The answer that we have come up with is called WideTable . The key idea behind WideTable is to denormalize the data into a wide table , and then run complex analytic SQL queries (e.g. with joins and nested subqueries) on the WideTable using BitWeaved scans. There are a number of different ways to use a WideTable, including as a materialized view and as an accelerator. Below, we show the how WideTable can be used as an accelerator. The WideTable component plugs in as a front-end to a traditional SQL engine, which could be a traditional SQL RDBMS system (like Oracle) or a Hadoop/SQL engine (li...
Post a Comment
Read more

From Locomatix to Twitter

Way back five years ago, just as the iPhone came out, Karthik Ramasamy ( @karthikz ) and I ( @pateljm ) started talking about building a combined real-time streaming and real-time analytical platform to power enterprise and consumer mobile services. We started a company called Locomatix to build such a platform. Sanjeev Kulkarni ( @sanjeevrk ), a founding member of the Google AdSense team, joined Locomatix soon after it was formed.  Next came Chris Kellogg ( @cckellogg ), who joined in his last semester at the University of Michigan. Today, I’m very happy to announce that the Locomatix team is joining Twitter ! Special thanks to our families and friends for supporting us throughout this incredible journey. We simply wouldn't have made it without you! Sanjeev, Karthik and I all got our graduate degrees from the University of Wisconsin, so a big part of Locomatix was powered by UW grads. Go Badgers! We are working on converting Chris into a Badger fan -- its still work in (ve...
Post a Comment
Read more

Life Beyond Column-Stores: Exploiting intra-cycle parallelism

Image
So, I have finally decided to start a blog. Why now, you might ask? The first reason is that I have been too lazy to start a blog till now. Since blogs often matter as much as publications, this oversight is inexcusable. Better late than never. The second reason to start a blog is that U. Wisconsin doesn’t, AFAIK, have a blog in the big data space. This is sad given the tradition that our university has in producing key data processing technologies, like the GAMMA parallel database system (which continues to influence what we now call “big data systems”), and BIRCH which provided a key pivot point for data mining (the buzzword-compliant term for that today is “deep data analytics”). This blog is a humble start in trying to get some of what Wisconsin does today in the big data space out into the blogosphere. So, the topic for today is – Exploiting intra-cycle parallelism for query processing . First, a quick background behind this line of thinking. If you zoom into the processor...
Post a Comment
Location: Computer Sciences Department, University of Wisconsin-Madison.
Read more