Archive for September, 2009

PhD scholarships

The IT University invites applications for PhD scholarships. If you are interested in doing a PhD in our group, read the call here, and contact your potential advisor in the group for information on possible projects.

Vertical partitioning of high-throughput OLTP databases

We generally divide database usage into two main categories:

  • Online Analytic Processing (OLAP) characterized by long and heavy read-mostly transactions processing large amounts of data (e.g. terabytes of log files), typically using aggregates on many rows, and
  • Online Transaction Processing (OLTP) characterized by very short-lived, but very frequent, transactions with either no aggregates or only a few aggregates on small row-subsets.

OLAP workloads will usually benefit from using a column store DBMS with highly efficient data retrieval and CPU utilization, while OLTP workloads should usually aim for a row store which is efficient for writes. (BTW: Abadi, Madden and Hachem wrote an excellent paper comparing column and row stores.)

Let’s take a closer look at row stores for high-throughput OLTP systems. Conventional row stores (e.g. Oracle, MySQL, SQL server, PostgreSQL, DB2 and more) are all basically build on paradigms introduced in System-R back in the seventies but the world has changed since then: most OLTP data sets now fit completely in main memory, hardware is both cheap and fast making it affordable to buy additional hardware when there is a need scale out, and it is no longer necessary to provide concurrency of transactions since transactions are very short-lived and might just as well be executed in serial. Stonebraker et al. wrote a quite revolutionary paper, suggesting a complete re-write of modern OLTP databases to match the world as it looks today. In short, they suggest a distributed memory-only database completely avoiding disk-based storage and minimizing the need for undo and redo logs. Initial experiments on a prototype (H-store (now named VoltDB)) showed drastic (!) throughput improvements so the project is very interesting to follow.

But what does all this babbling have to do with vertical partitioning? While row stores are write optimized they are sub-optimal for reads: all retrieval is done in units of whole rows, even if the retrieving transaction only needs a small subset of the columns. When processing a query after its row retrieval, wide rows with superfluous columns generally result in less throughput than narrow rows without superfluous columns. That is, wide rows are generally wasting costly I/O - even if the I/O is from main memory. A column store would not suffer from these problems but writes are relatively costly in column stores making them undesirable for OLTP workloads. A solution is to vertically partition the tables into (possibly non-disjoint) smaller fractions so that the number of superfluous columns retrieved by each transaction is minimized. Given a set of sites in a cluster, the challenge is now to distribute attributes from an input schema and transactions from an input workload to these sites so that the costs of retrievals, writes and inter-site transfers are minimized. Furthermore, we would like all columns needed by a read query to be co-located with the query as inter-site transfer may be a bottleneck for short-lived transactions, or equivalently: single-sitedness of read queries should be preserved. And last, we would like to be able to prioritize between total cost minimization and load balancing of the sites. This distribution problem is non-trivial, and in fact NP-hard. A soon-to-be-submitted paper presents an exact algorithm and a heuristic solving it. Both algorithms have been experimentally shown to obtain good results.

Post ALGO post: Etiquettes and etiquette

This is part 3 in a series of 3 posts on ALGO 2009, largely repeating the organiser’s report from the business meeting. This is the least serious part.

Name tags

One of the small details that I tried to micro-manage are name tags. For some reason, name tags at many conferences display the attendee’s name in very small letters, and leave most of the tag’s area either white, or taken up by the logo of the conference or venue. (Professional name tag designers typically optimise something else than ease of identification of the attendee. That’s their job, and they are good at it. But it’s not the job I want done.) ALGO had nice, legible name tags, and we also tried to double-check various diacritics.

One the other hand, the batch-driven production from a spreadsheet to the final tag messed up some affiliations, for reasons that remained a mystery. Incidentally, I don’t really understand the value of displaying the affiliation on the tag anyway, they seem to serve mostly as an ice-breaker for conversations. (Maybe we should put people’s hobbies on the tags instead.) From that perspective, a wrong affiliation works at least as well.

Closely related to the layout of the name tag are the mechanics of the badge holder. After obsessing over this for many years I have concluded that the pin–clip combo is the way to go, so that’s what we got. We even told people to not clip the badge to their trousers. It was perfect, nothing could go wrong, everything was prepared for the one conference where you wouldn’t have to squint or use x-ray vision to read the name of whats-his-name-I-think-we-met-at-ICALP-last-year.

Alas, it was not enough. A seemingly unrelated decision destroyed all my careful planning: We decided to hand out multi-ride ticket to the Copenhagen subway system, attached to ITU-branded key bands. (This was to prevent the tickets from being accidentally lost in the pile of written material we handed out to attendees.)

The effect?

Driven by their desire to remain anonymous, and a perverse predilection for craftsmanship, many enterprising attendees carefully removed the ticket from the key band, and attached their name tag instead, thereby constructing the mothership of all that is evil about name badges: they dangled at belly button height, typically obscured behind tables or under jackets, and they swivelled around their single, ill-constructed joint, displaying the badge’s empty back side more often than the laws of probability theory predict.

Next time I’ll tatoo the name on people’s forehead.

Computer use

The etiquette about open laptops during talks is very much unclear in the CS community. We politely asked people to avoid accessing the internet during sessions, and if so, to do it from the back row so as to annoy the speaker and the rest of the audience as little as possible. Several attendees told me they were happy about this decision; the auditoriums were certainly relatively free of open laptops. I remain uncertain about how to handle this – I can get a lot of work done while half-way listening to a talk, and the alternative is to stay out of the lecture room…

Speaker instructions

One thing I decided against, for fear of committing a social mistake, was to send instructions to the speakers about how we would have liked the talks at ALGO. Namely, more accessible.

Talk quality at our conferences is generally high: clear, readable, well-presented, entertaining. However, most of the speakers vastly overestimate the audience’s level of familiarity with the subject. This makes it very difficult to attend a presentation to learn something, in particular about a field in which you aren’t an expert already.

One of the problems is that talks are grouped into thematically related sessions. This seems to imply that everybody in the room is already an expert about “latest derandomisation tricks in quantum I/O kernelisation,” so why bother explaining the basics again? An earlier rumination of Michael Mitzenmacher about the STOC 2009 schedule already touched on the bold idea of mixing sessions at random. (But this may introduce more problems than it solves.)

The smaller events at ALGO, such as WAOA and IWPEC, are technically highly specialised workshops in the first place, pitched at an expert audience. So how do we turn this around? It would be great if ALGO attendees could “stay for IWPEC” to finally find out what “this FTP-stuff” is all about – but the atmosphere has the exact opposite effect. Similarly, I talked to a WAOA attendee who was frustrated about the O-part being largely incomprehensible. (The attendee was there for the A-part.) How do we solve this? Clearly, not every IWPEC talk can define treewidth again, but my ambition with ALGO was to reduce balkanisation, not contribute to it.

Many of the “too difficult” talks are given by students. There are a number of reasons for this – students assume that everybody knows what they do (I did), students need to demonstrate that they’re smart and did a difficult thing, some students lack the broad overview to be able to place their subfield into a broader ensemble, previous talks have been given only at departmental seminars, where everybody else is equally interested in derandomising quantum I/O kernelisation, etc. Maybe for this target audience, a “Here’s what we’d like your talk to be”-letter could have done a lot of good.

Post ALGO post: Numbers

This is part 2 in a series of 3 posts on ALGO 2009, largely repeating the organiser’s report from the business meeting.

Boring statistics

For some conference attendees, this has already become a drinking game: the part where the organiser entertains with useless statistics.

I have probably the best number ever: the total height of the ALGO attendees is 283m, discounting those that didn’t give us their measurements at registration. (We needed these to plan ALGO 2009’s social event, a short bicycle trip to Copenhagen city hall.)

Number of participants

More interestingly, in particular to later organisers of ALGO: the budget. When planning an event like this, the big open question is how many people will actually show up. Previous ALGO organisers were very helpful in giving us their numbers, but it’s hard to use them for prediction. Previous ALGOs hosted ESA, WAOA, and ATMOS, but in 2006 and 2008, ALGO also hosted WABI, the Workshop on Algorithms in Biology, which is a large conference. We did attract IWPEC to ALGO 2009 (two dozen talks), but it is unclear how many extra attendees this produces – ESA itself had several tracks of IWPECish presentations, so there is a lot of speaker overlap. In the end, we were able to match the Karlsruhe numbers, even without WABI, and without the large number of local attendees Karlsruhe presumably had.

Registrants by type

The number of attendees doesn’t give full information for the budget, because students pay far less. ALGO budgets over the last four years operate with the number 57% for the number of expected regular participants. At ALGO 2009, we had some 75 students, so the number of regular participants is in fact slighly above 60%. We tried to make student participation as attractive as possible, but it seems to be difficult to attend ALGO just for the event, without a paper. (Or is Copenhagen sufficiently attractive for the advisor, not the student, to attend?)

Length of stay

Another constant throughout the ALGO budgets from previous years is the assumption that an attendee stays for 3 days. (You need this to calculate the number of lunches.) We asked attendees at on-line registration to tell us their expected date of arrival and departure, and asked them to confirm these dates when they collected their name tags. If these numbers are to be trusted, more than half of the participants actually stayed for the full week; in particular, they gluttonously devoured all the food they actually paid for. This would be a huge success from the perspective of us wanting to organise a large, monolithic 5-day event. Of course, since we have to order all these lunches, there is very little wiggle room left in the budget.


Finally, the budget. For paying 180 participants, we budgeted with something like 500,000 Danish kroner, or roughly 65,000 euros. Most of the expenses are food. This includes lunches, coffee, breakfast, and some cakes during the day. After the business meeting on Monday, we provided snacks and drinks at ITU. The social event was a bicycle trip through Copenhagen, the main expense is renting some 200 bicycles. ITU provided the rooms for free, and most of the staff. (We had to find some help with registration.)

The only expense that could have been reduced is the invited speakers. First, ALGO had a lot. 7 invited speakers for an event with less than 200 registrants cost a lot of money per ticket. In even years, ESA “pays” for 2 invited speakers on the first three days, WABI gets the third. We decided to have 3 speakers on the first three days anyway, and 2 speakers per day for Tuesday and Friday, which hopefully transformed these days into very attractive experiences and made many people stay beyond ESA. Of course, all of this is expensive.

Should I do this again, I would probably be less generous. A possible model would be to let invited speakers pay for their own travel. (This is something that the speaker can easily find funding for anyway.) I understand that other conferences use that model, or at least put a cap on the travel reimbursement.

Post ALGO post: Decisions

This is part 1 in a series of 3 posts on ALGO 2009, largely repeating the organiser’s report from the business meeting.

ALGO week

Here’s what the ALGO week looked like, from 7 September to 11 September 2009:

Without WABI, the ESA conference has the first three days to itself – an alternative would have been to give three full days to IWPEC and let it overlap, at least partially. Given the IWPEC submissions that might have been a better idea.

PC meetings

More critical is the situation before the conference proper, when all the various PCs have to coördinate their activities. It has been decided that ESA waits for ICALP’s decisions, so with Springer’s deadline for conference production, the available time slots are pretty tight. For the organiser this means that the deadline for early registration has to be pretty late, which makes it hard to produce a realistic final budget. Also, we were unable to hold hotel rooms longer than the first week of July, which was before WAOA’s notification. This turned out to be no problem, hotel rooms were still plentiful.

Still, all the PCs had to work under very tight conditions. Moving the ICALP PC meeting to the left a bit, and possibly moving the ALGO conference date farther into mid- or late September would remedy this.


One of our early decisions was to view ALGO as a monolithic, five-day event, rather than a smörgåsbord of workshops and events for which to register (and get billed) separately. This is a hard decision that has many consequences for organisation, financing, dealing with PCs, etc.

  1. Student registration covers social events. The social events are an important part of the conference, in particular for students. Therefore, I’m never really happy with conferences where student registration does not cover the joint dinner or the social events. Many institutions make it much harder to get reimbursement for a dinner ticket than an exorbitant conference fee. Thus, we slightly under-priced participation for students, and slightly over-priced participation for regular attendees.
  2. No separate workshop registration. ALGO 2009 participants paid the same, whether they stayed for five days including all social events, or whether they just popped by for their own talk and left the same day. This made it attractive to stay for more days, which is what we want, but probably also prevented some people from attending.

In the end, I think we made the right decision. We had lots of attendees, and many stayed for many days. However, the ATMOS workshop is probably hurt by this: it’s a 1-day event, even trying to attract relevant industry, and the full ALGO participation fee is just too high for that. In hindsight, I believe a separate “1-day, no fun”-registration, for exactly half the price of the full ALGO registration, is the proper way to go.


We decided early on to have ALGO at the university, during the semester. I like this a lot better than using a dedicated conference venue or a hotel; the atmosphere is nicer, and we’re sending important signals in both directions. The possible downside is that ALGO 2009 was crowded (which I like), and that we had to make some compromises with respect to lecture rooms that would otherwise not have been an issue.

It’s also dirt cheap.

Exponential time complexity

At the next three group meetings or so, I’ll try to give a very concrete introduction to exponential time complexity, including some very recent and exciting results (none of them mine). Here’s the plan, expressed in terms of papers I want to mention:

21 Sep: On Problems without Polynomial Kernel, Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin (ICALP 2008). Infeasibility of instance compression and succinct PCPs for NP, Lance Fortnow, Rahul Santhanam (STOC 2008)

28 Sep: On the Possibility of Faster SAT Algorithms, Mihai Pătraşcu and Ryan Williams (SODA 2010).

5 Oct: (cancelled).

A lot of exciting stuff is happening in this area right now, in fact, we just had a proposal for a 2010 Dagstuhl seminar accepted: Exact Complexity of NP-hard Problems.

ALGO 2009 blogging

Invited speaker Michael Mitzenmacher has been blogging from ALGO: ESA Talk and Paper, Controversy at ESA, ESA 2009; Jeff Phillips guest-blogs at the Geomblog: Geometry at ESA; and invited speaker Noam Nisan writes Report from algo 2009.

Data mining at ITU

I’m happy to report that there is now officially data mining papers coming out from ITU. Andrea Campagna and myself had our paper Finding Associations and Computing Similarity via Biased Pair Sampling accepted at IEEE International Conference on Data Mining. In the paper we present a new sampling techniques that can be used to find related items in a set of transactions. We look forward to presenting this in December!

ALGO 2009 pictures

We are having a hectic but fun week with ALGO 2009. Per Rasmussen has taken a lot of pictures from the events, which included a bicycle trip to Copenhagen City Hall.

ALGO organizers with minister Helge Sander and vice-chancellor Mads Tofte

Update. It turns out that we even made it to national TV (see ALGO attendees walking into Copenhagen City Hall in the background).
ALGO on live TV