Mneme's Kiss

ERC Starting Grant

2011-06-09T16:00:00.000-07:00

It seems I won one. Wat do?

Thank you, Advice Dog!

Probabilistic databases book published online

2011-06-03T18:11:00.000-07:00

Our Morgan Claypool Synthesis Lecture on probabilistic databases

Probabilistic Databases
Dan Suciu, Dan Olteanu, Christopher Ré and Christoph Koch
Synthesis Lectures on Data Management, May 2011, Vol. 3, No. 2, Pages 1-180
(doi: 10.2200/S00362ED1V01Y201105DTM016)

is now avaiable here!

DATA lab website online

2010-12-15T04:18:00.001-08:00

The DATA lab now has a website: data.epfl.ch.

New paper: "DBToaster: Agile Views in a Dynamic Data Management System"

2010-12-13T18:54:00.000-08:00

We just submitted the final version of our CIDR 2011 paper "DBToaster: Agile Views in a Dynamic Data Management System". This is the first paper to present the overall vision and goals of the DBToaster Project and recommended reading for those who want to learn about the project but only want to read one paper.

Get the pdf here.

Abstract. This paper calls for a new breed of lightweight systems – dynamic data management systems (DDMS). In a nutshell, a DDMS manages large dynamic data structures with agile, frequently fresh views, and provides a facility for monitoring these views and triggering application-level events. We motivate DDMS with applications in large-scale data analytics, database monitoring, and high-frequency algorithmic trading. We compare DDMS to more traditional data management systems architectures. We present the DBToaster project, which is an ongoing effort to develop a prototype DDMS system. We describe its architecture design, techniques for high-frequency incremental view maintenance, storage, scaling up by parallelization, and the various key challenges to overcome to make DDMS a reality.

Please cite as

Oliver Kennedy, Yanif Ahmad, and Christoph Koch. DBToaster: "Agile Views in a Dynamic Data Management System". Proc. 5th Biennial Conference on Innovative Data Systems Research (CIDR ’11), January 9-12, 2011, Asilomar, California, USA.

Talk: MCMC and databases

2010-12-13T18:43:00.000-08:00

Here are the slides of a keynote talk I gave in Spetember at the Scalable Uncertainty Management Conference (SUM 2010) in Toulouse. In this talk I sketched research challenges in creating probabilistic database management systems based on Markov Chain Monte Carlo, describing my own as well as other recent work on the topic. The abstract reads as follows:

Several currently ongoing research efforts aim to combine Markov Chain Monte Carlo (MCMC) with database management systems. The goal is to scale up the management of uncertain data in contexts where only MCMC is known to be applicable or where the range and flexibility of MCMC provides a compelling proposition for powerful and interesting systems. This talk surveys recent work in this area and identifies open research challenges.
The talk starts with a discussion of applications that call for the combination of MCMC with ideas from database management. This is followed by a brief discussion of the now somewhat maturing field of probabilistic databases not based on MCMC, and what can be learned from these. Next, the architecture of an MCMC-based database management system is sketched, and key technical and algorithmic challenges are discussed. For efficient MCMC, it is key to be able to quickly evaluate queries on a sequence of many sample databases among which consecutive samples differ only moderately. The talk discusses techniques for efficiently solving this problem by aggressive incremental query evaluation. The locality of changes between consecutive samples is also key to scaling MCMC beyond state sizes that fit conveniently into a computer’s main memory.
The second part of the talk addresses query languages beyond industry-standard languages such as SQL, which have limited appeal in the context of the scientific applications of MCMC. Computational problems to which MCMC is applied are often best expressed in terms of iteration and fixpoints. Database research knows languages centered around these principles, and it is interesting to understand how iteration as a query language construct interacts with MCMC sampling. The talk presents recent results in this space, including considerations of complexity and expressive power of query languages specifically designed for MCMC.

Please cite as

Christoph Koch: Markov Chain Monte Carlo and Databases. In Proc. SUM 2010, p.1.

Talk: Rethinking the foundations of databases

2010-12-01T16:48:00.000-08:00

Contemporary database query languages and systems are ultimately founded on logic. Last week I gave a talk at EPFL (in the KTN seminar) arguing for an effort to rethink databases and query languages and to found them on the machinery of modern abstract algebra. This bears the promise of radically simplifying and offering new angles of attack on some of the hardest and most central problems in data management -- such as query equivalence testing, the view update problem, and data integration. It also heralds the convergence of database systems and computer algebra systems, bearing the promise of a new breed of systems that could revolutionize large-scale data analysis and scientific data management and computing.

The video of this talk is now online here, and here are the slides. Unfortunately, the final few minutes of the talk are missing from the video.

Pictures of DATA Lab trip to Zermatt on Flickr

2010-11-21T17:06:00.001-08:00

The members of the amazing DATA Lab (before it got that name) went to Zermatt in great weather and HERE are our pictures.

New DBToaster project Web page, and DBToaster video lecture

2010-11-21T11:41:00.000-08:00

Since I have moved to EPFL and Yanif Ahmad has started as faculty at Johns Hopkins University, we needed a successor to the DBToaster project page at Cornell. Here it is: www.dbtoaster.org. Right now there is not much there, but expect great improvements soon!

Using Google, I just stumbled over a video of an invited lecture I gave earlier this year:

http://videolectures.net/akbc2010_koch_fivm/

This is a 55 min talk -- the slides are also there. (I was told that this would be recorded and published on the Web, but all but forgot about it.)

This is a talk about the DBToaster project I have given at a number of places recently, with some adaptations (application to probabilistic inference in graphical models) made to fit the topic of the workshop. Hear me talk at my usual speed (that is, way too fast)! The other talks of that workshop are also online as video lectures, and quite interesting!

Please log in at this site and rate the video five stars! :-) :-)

Birth of the DATA Lab at EPFL

2010-11-18T11:00:00.000-08:00

From the viewpoint of EPFL, each faculty member is an organizational unit called a lab. Unfortunately, our personal names are not acceptable to EPFL, so we have to make up an English name, a French name, and an acronym for the lab, describing what we plan to do.

This is not so easy. (How do you translate "data-driven" to French -- I can't even translate it to German.) The suggestion I finally came up with after many months of hard thinking (mostly about other things though) has just been approved by the EPFL administration.

DATA, enchanté!

Christoph now at EPFL

2010-07-06T09:28:00.000-07:00

I have joined EPFL! My new homepage is here (still under construction).

Release of database theory slides

2009-08-31T14:26:00.001-07:00

I have decided to make some of my database theory slides plus their latex sources publicly available at http://www.cs.cornell.edu/~koch/teaching/dbtheory/. Anybody may use and modify them, and you do not have to acknowledge me in your derived writings and slide sets (although it would be nice if you did). However, if you find the slides useful, I ask you to sign my blog article announcing this page, and to say something nice.

I hope that these slides will be useful to young lecturers who have not yet created their own slide sets on the topic, or to lecturers who usually do not teach this material but who might change their minds because of the availability of these slides.

Most of the slide sets are available both in English and German, and I think that for German, there is no source of this material yet that is available free of charge.

Note that these slides are not representative of the courses that I teach or have taught in the past. The slides made available here focus on certain aspects of logic and finite model theory. By themselves, I do not think they make an interesting or self-contained course. I make these slides available because I have currently no plans of using them in the future; since they took a lot of time to create, I hope that someone else can profit from them.

I have currently no plans to release my other DB theory slides, but this may change in the future.

Give your picture the Ithaca touch

2009-08-19T17:32:00.001-07:00

http://www.lutralutra.co.uk/squirrelizer/

Google Faculty Summit

2009-08-01T21:43:00.000-07:00

This week I attended the two-day 2009 Google Faculty Summit at the Googleplex. Here are some highlights:

Quite some time was spent presenting Google.org, which is an umbrella organization for Google's activities for doing good. Apparently, Google has a statute to use one percent of its profits and equity for this. Previously, Google.org acted more like a classical philantropy, giving money, but is now shifting to doing things where Google's core competencies can come into play. One prominent example is Google Flu Trends.
Other technologies that much time was spent on were Android and Wave. The latter is still not ready, but the demo was cool, and Lars Rasmussen, the presenter, is a really funny guy -- check out this older Wave video on Youtube. (It seems that together with his brother Jens, he initiated both Wave and Google Maps; that's really impressive.) What I liked most was automatically translated instant messaging between people who do not speak the same language.
There was also an interesting talk by Brad Chen on Native Client, a way of running native code in a browser in a -- hopefully -- secure way. Brad's claim that security (broadly construed, I really think he meant that -- one will be able to judge from the video once it goes online whether I misunderstood him) is easy was ridiculous, though.
The technical talk on Google's approach to machine translation by Franz Josef Och was one of the best, in my opinion.
A talk on Google Book Search spent a considerable amount of time explaining the terms of the settlement that was recently reached with authors and publishers. Personally, I still have a too lively recollection of Brewster Kahle's criticisms he made at his recent Cornell talk to be happy about all this.
There were also nice round table discussions. I joined the one where Alon Halevy answered questions on the Fusiontables project. It's a really cool project (and there seems to be a great opportunity to combine FusionTables with Cornell's Youtopia project, once the Fusiontables API becomes available), but it is really still work in progress and a lot of essential features are not available yet.
There was a talk on Youtube.EDU by Obadiah Greenberg from Youtube. It is an effort in which many leading universities put videos of entire courses online and make them available for free to everyone. It's an amazing resource. Youtube.EDU can display the most subscribed universities. The top three are Stanford, Berkeley, and MIT. They now offer hundreds of courses on Youtube.EDU; for example, MIT has moved its OpenCourseWare initiative to Youtube. Virtually all of Cornell's peers have fully embraced Youtube.EDU and we, in Computer Science (which accounts for a large part of the course materials on Youtube.EDU), are not part of this at all. It's a real pity, we may be missing the boat here.

I won't say more on the talks here; I expect the videos to be available on Youtube soon; once that's the case, I'll add links to them.

Overall, the summit was perfectly organized, and all the Googlers showed a great sense of humor as well as humility. (Some things went wrong here at last year's summit, judging from the videos that one can find on Youtube.)

Amazing Austrians win Netflix prize, says newspaper

2009-07-28T22:09:00.000-07:00

The June 28 edition of the Kurier (an Austrian daily newpaper) that I read on a flight has a story claiming that a team of Austrian programmers have won the Netflix award. That's consistent with the rumors that the winning team has been notified by Netflix, although no announcement has been made yet. That Austrian team is part of the BellKor team, which is one of the two contenders for the prize. So it is quite likely that these news are true. Amazingly, I could not find this information in English on the Internet -- what a hot blog this is! ;-)

It is sad though that BellKor was not at all mentioned in the article; it really looks like this was a primarily Austrian effort, which shows more than a little chauvinism.

Here is a link to the story (in German).

Invited talk at CIAA'09 on applications of automata in XML processing

2009-07-23T12:54:00.001-07:00

Last week I gave an invited talk at the 14th International Conference on Implementation and Application of Automata (CIAA'09) in Sydney, Australia. I talked about applications of automata in XML processing. More specifically, I addressed three problem areas:

Using automata for XML validation, where I addressed DTDs and XML Schema (more precisely, restraint competition grammars), their automata theoretic analogs, and efficient streaming validation.
Using automata in XML publish-subscribe and complex-event processing systems, and
Using automata for evaluating highly expressive node selecting queries with a constant number of sequential passes over the data.

I also talked a little about the industrial importance of complex-event processing systems.

Overall, the conference was a very nice opportunity to meet some old friends. Unfortunately, it was not a equally great opportunity to make new ones among the Koala population (i.e., form a coalition). All the local Koala's seemed to live in zoos and were said to die from stress if one touches them. (So that's illegal.) Generally, the wildlife is well protected there. I saw a sign at the beach which put picking up seashells or barnacles under a fine of up to $22,000.

(Note: the picture is from Wikipedia. I saw no Koalas, just barnacles.)

SIGMOD 2009 New Researcher Symposium

2009-07-23T08:11:00.001-07:00

The goal of this year's SIGMOD New Researchers Symposium, which I co-chaired with Nesime Tatbul from ETH Zurich, was to give graduate students and junior researchers advice on various challenges involved in human factors, such as successfully making the move from graduate student to being part of, and productive in, a team of researchers in an industry lab or to becoming junior faculty and having to build up a research group. The two panels, consisting of well-known members of the data management community, also covered issues such as attracting and mentoring graduate students or junior researchers and providing good leadership of a research group. The slides used by the panelists are now available here. (Note: some panelists did not use slides.)

Why “Mneme’s Kiss”?

2009-07-08T21:40:00.000-07:00

The name of this blog was inspired by a short talk to prospective PhD students at Cornell University that I gave a while ago, representing the database research group. I concluded my talk with a short “theory” part, where I “proved” the following theorem:

Theorem. Creative computer science research is only possible in data management.

Proof Sketch:

No creativity without divine help.
Divine help is only available to data management researchers.

Part 1 was a "proof by reputation". Already the ancient Greeks knew that the muses are the source of all inspiration. I just cited three reputable sources (only one greek), and left the rest of this part of the proof as an exercise to the reader:

Sing to me of the man, Muse, the man of twists and turns

driven time and again off course, once he had plundered

the hallowed heights of Troy.

– Homer, The Odyssey

O Muses, o high genius, aid me now!

O memory that noted what I saw,

Now shall your true nobility be seen!

– Dante Alighieri, The Inferno

Of Man’s first disobedience, and the fruit

Of that forbidden tree, whose mortal taste

Brought death into the World, and all our woe,

With loss of Eden […] sing, Heavenly Muse

– John Milton, Paradise Lost

For part 2 (no creative research unless it is in databases), I just needed to point out that the three original muses of Greek mythology were

– Aoidē (song)

– Meletē (practice, meditation)

– Mnēmē (memory).

Memory: that's data management. Thus, among computer science research areas, only data management has its own muse, so creative research is only possible there! [QED]

Now let me point out that in my native German, one does not get inspired by a muse’s touch as it is, I think, the case in English, but by her kiss. Who wouldn't prefer the latter.