April 14, 2011

VLDB 10-year Best Paper Award!

Filed under: Uncategorized — magda balazinska @ 12:32 pm

I’m delighted to share the news that Jayant Madhavan (a UW CSE Ph.D alum currently at Google) and Phil Bernstein (researcher at MSR and also affiliate faculty and member of our DB group), along with their co-author Erhard Rahm received the VLDB 2011 10-year Best Paper Award for their VLDB 2001 paper “Generic Schema Matching with Cupid”! (This award is given to the paper from the conference 10 years ago that had the most impact).


April 12, 2011

PODS 2011

Filed under: Publication News — paris koutris @ 12:34 am

Apart from SIGMOD 2011, our group will also participate in PODS 2011 with the following paper:

Parallel Evaluation of Conjunctive Queries (Paraschos Koutris and Dan Suciu)

The availability of large data centers with tens of thousands of servers has led to the popular adoption of massive parallelism for data analysis on large datasets. Several query languages exist for running queries on massively parallel architectures, some based on the MapReduce infrastructure, others using proprietary implementations. Motivated by this trend, we analyze the parallel complexity of conjunctive queries. We propose a very simple model of parallel computation that captures these architectures, in which the complexity parameter is the number of parallel steps requiring synchronization of all servers. We study the complexity of conjunctive queries and give a complete characterization of the queries which can be computed in one parallel step. These form a strict subset of hierarchical queries, and include flat queries like R(x,y),S(x,z),T(x,v),U(x,w), tall queries like R(x),S(x,y),T(x,y,z),U(x,y,z,w), and combinations thereof, which we call tall-flat queries. We describe an algorithm for computing in parallel any tall-flat query, and prove that any query that is not tall-flat cannot be computed in one step in this model. Finally, we present extensions of our results to queries that are not tall-flat.

Blog at WordPress.com.