- SIGMOD EVENTS New
Researcher Symposium and Undergraduate
Research Poster Competition. Please come to these two events at
this week's SIGMOD to encourage the next generation of database nerds!
- PODS 2012 Hung Ngo, Ely Porat, Atri Rudra, and I have a new PODS paper called "Worst-Case Optimal Join Algorithms." For all join queries, we are able to provide the first optimal algorithm in terms of data complexity. The key to the result is an algorithmic proof for a pair of inequalities from discrete geometry called the Loomis-Whitney inequality from the 1940s and the more recent Bollobás-Thomason inequality. We show that these classical inequalties are equivalent to the beautiful recent results by Atserias, Grohe, and Marx. Our work also provides an algorithmic proof of these results. In contrast, all previous proofs are non-constructive. Thank you to the program committee for selecting this paper for the Best Paper Award.
- SIGMOD 2012 Aaron Feng, Arun Kumar, Ben Recht, and I have a paper Towards a Unified Architecture for In-RDBMS Analytics accepted to SIGMOD 2012. The code is available here Bismark (so is the data) and the paper (full version). Thank you to Greenplum and Oracle for valuable discussions that helped us understand this problem!
- ACL 2012 Feng Niu, Ce Zhang, Jude Shavlik, and I have a paper that builds on our experiences with DeepDive to study the impact of Big Data with Distant Supervision versus Crowd-Sourced data on the quality of relationship extraction from the Web. The paper title is Big Data versus the Crowd: Looking for Relationships in All the Right Places.
- COLT 2012 Ben Recht and I have a new manuscript. The starting point of the manuscript is that practioners who run sequential random sampling algorithms (like stochastic gradient) sample from their data without replacement. In many cases, people have observed that sampling without replacement empircally converges to an optimal value faster than with-replacement sampling approaches. There is, however, a gap in our current theory as current theory provides faster convergence rates for with-replacement sampling than without replacement sampling. This paper takes a step toward closing this gap. We establish that without replacement methods do converge faster in several sampling models and propose a general inequality, a symmetrized (noncommutative) arithmetic-geometric-mean inequality, that would close this gap in many cases. CRC Coming Soon.
- VLDB 2012. Accepted for publication in VLDB 2012 in Istanbul.
- Arun Kumar and I have a paper, Probabilistic Management of OCR Data using an RDBMS. The paper is our first attempt to understand the implications of combining rich content models like OCR with the sophisticated querying capabilities of an RDBMS. The state-of-the-art models underlying these content models are probabilistic, e.g., OCRopus for Google Books. These models have very high quality, but the sheer size of these models can destroy query processing performance. Arun's idea is to use some ideas from statistics to compress the model; in turn, this allows him to trade run time for quality. Thank you to the Microsoft Jim Gray Systems Lab for supporting Arun's work. (Code and data here)
- The MADlib Analytics Library or MAD Skills, the SQL. Joseph M. Hellerstein, Florian Schoppmann, Daisy Zhe Wang, Eugene Fratkin, Aleks Gorajek, Kee Siong Ng, Caleb Welton, Xixuan Feng, Kun Li, Arun Kumar, and I have a paper about the status of the status of MADLib, which is an awesome open-source effort led by Greenplum. Thank you, EMC!
Christopher Ré
Email: chrisre at cs.wisc.edu
Phone: (608) 263-5489
Office 4363 Office Hours: By Appointment
Phone: (608) 263-5489
Office 4363 Office Hours: By Appointment
Department of Computer Sciences
University of Wisconsin-Madison
1210 W. Dayton St.
Madison, WI 53706-1685
University of Wisconsin-Madison
1210 W. Dayton St.
Madison, WI 53706-1685
A demo of DeepDive and WiscI are
Dedupalog is
a declarative language for specifying deduplication tasks. In our
upcoming ICDE 2009 paper, 
