Database Seminar Series (2011-2012)

"Big Data" stored in map-reduce (M-R) clusters is often fundamentally temporal in nature, as are many analytics tasks over such data. For instance, display advertising uses Behavioral Targeting (BT) to select ads for users based on prior searches, page views, etc. Prior work on BT has focused on techniques that scale well for offline data using M-R. However, this approach has limitations for BT-style applications that deal with temporal data: (1) many queries are temporal and not easily expressible in M-R, and moreover, the set-oriented nature of M-R front-ends such as SCOPE is not suitable for temporal processing; (2) as commercial systems mature, they may need to also directly analyze and react to real-time data feeds since a high turnaround time can result in missed opportunities, but it is difficult for current solutions to naturally also operate over real-time streams.

We therefore propose a novel framework called TiMR (pronounced timer), that combines a time-oriented data processing system with a M-R framework. Users write and submit analysis algorithms as temporal queries — these queries are succinct, scale-out-agnostic, and easy to write. They scale well on large-scale offline data using TiMR, and can work unmodified over real-time streams. We also propose new cost-based query fragmentation and temporal partitioning schemes for improving efficiency with TiMR. Second, we show the feasibility of this approach for BT, with new temporal algorithms that exploit new targeting opportunities. Experiments using real data from a commercial ad platform show that TiMR is very efficient and incurs orders-of-magnitude lower development effort. Our BT solution is easy and succinct, and performs up to several times better than current schemes in terms of memory, learning time, and click-through-rate/coverage.

I will describe some of the efforts we are conducting at Google towards this goal and the technical challenges they raise. In particular, I will describe Google Fusion Tables, a service that makes it easy for users to contribute data and visualizations to the Web, and the WebTables Project that attempts to discover high-quality tables on the Web and provide effective search over the resulting collection of 200 million tables.

This talk observes that several types of communication patterns exist, not all of them harmful, and that unscalable communication patterns can often be converted to more helpful ones. Doing so can eliminate a wide variety of scalability bottlenecks, from the query scheduler all the way down to the operating system, while still allowing the convenience of a shared-everything system. Along the way, we uncover a second recurring theme: effective solutions increasingly tend towards co-design. The DBMS is a highly complex and layered piece of software, and changes (often fairly small ones) in one part of the system can allow disproportionate simplification and/or enhancement of other parts. Together, these two observations allow a shared-everything DBMS to scale to dozens of cores without giving up features such as durability or strong consistency.

Scientific applications are still poorly served by contemporary relational database systems. At best, the system provides a bridge towards an external library using user-defined functions, explicit import/export facilities or linked-in Java/C# interpreters. Time has come to rectify this with SciQL, a SQL-query language for science applications with arrays as first class citizens.

In this talk I outline the language features using examples from seismology, astronomy and remote sensing. It demonstrates that a symbiosis of the relational and array paradigm is feasible and highly effective to cope with the data intensive research challenges encountered in science.

Subsequently, its ongoing implementation on top of MonetDB is described at some length, providing a vista on the many novel database research issues emerging.