EmergencyEMERGENCY? Get 24/7 Help Now!

Database Algorithms sin Pantalones

 | February 21, 2012 |  Posted In: Tokutek, TokuView


So there I was, gesticulating in front of the chalkboard, lecturing to 120 students. Topic: the beauty of advanced data structures. The door opens and the department chair walks up the aisle onto the stage and comes up to me. 242 eyes follow her progress through the room. She whispers to me that I must stop speaking in English. Officially, the course must be conducted entirely in Spanish.

Entirely in Spanish… I turn back to face the students. 120 students are waiting for me to speak. I realize that I don’t even know how to say simple constructions like “x plus y” let alone “advanced data structure” or “order log log amortized time complexity.”

Is this a newfangled anxiety dream? Can this replace the tried and true: I’m in front of the class but I forgot to put on my pants? Can this replace the classic: I’m back in high school and have one just more class to take; but I haven’t been attending and don’t know what the material is about?

But I’m not dreaming. This actually happened.

This real-life anxiety dream, the prehistory of Tokutek, and the Imre Simon Test of Time Award come together in the following story.

The Latin American Symposium on Theoretical Informatics (LATIN 2012) is giving its first ever “Imre Simon Test of Time Award” to the paper deemed most influential from among all those published in LATIN at least ten years earlier. The prize is described on the conference website.

Martin Farach-Colton and I just learned that we are getting this award for our paper “The LCA Problem Revisited,” which we presented at LATIN 2000.

Although our paper doesn’t discuss Fractal Trees, cache-obliviousness, or even MySQL, we probably couldn’t have started Tokutek if we hadn’t written this paper first.

Here’s the story in (semi) brief.

In 1999 Martin and I taught a week-long course on advanced data structures at the University of Buenos Aires. We aimed to show that advanced data structures—which are frequently viewed as unwieldy and not very pretty—can be recast as things of beauty. In preparation for our course, we revisited some classic data structures and wrote several papers, including this one.

It is no exaggeration to say that this course in Buenos Aires changed our lives. Afterwards, Martin and I began developing I/O-efficient and cache-oblivious data structures (e.g., cache-oblivious B-trees, packed-memory arrays) and Bradley joined the effort soon after (e.g., Fractal Trees).

Need I mention that on the first day of class, Martin and I learned that we were speaking the wrong language.

Unbeknownst to us, the university had advertised that the class would be conducted in Spanish. We had prepared in English. But students and professors had showed up from all over Argentina, and we had no alternative but to switch languages. Martin speaks Spanish natively, but it was trial-by-fire for me since my rudimentary Spanish didn’t include a single technical word. Each morning, in preparation for class, Martin taught me the vocabulary that I would need to get through the day.

The class was a success and has since become a great memory.

So that’s the story. The bottom line is that Martin and I are thrilled that this paper, which came out of that class, has been recognized by the LATIN conference.



  • Wow, that’s amazing! I wish there was some video, maybe just 10 minutes or so. Of course, that may be because I immortalize a lot of my own failings in a weekly podcast and videos of my own talks….

    • Dear Sheeri,

      Many thanks for the wonderful comment.
      Indeed It was an amazing adventure.
      But boy am I glad there’s no video 🙂


  • This is a great story! Coming from more of an engineering background I didn’t know about this Latin American Theory@CS community until very recently. Wish I had more exposure in my college years to this kind of stuff. Fortunately, by a major stroke of luck I got to be in your class at graduate school.

    • Dear Vincente,

      Thank you for the wonderful comment.

      The Latin American theoretical CS community is one that I particularly care about. I like attending the LATIN conference, and I’ve served on the LATIN Program Committee several times.

      I know what you mean by underexposure. Latin America traditionally produces many great programmers and mathematicians. But some parts are underexposed to theoretical computer science.

      When Martin and I taught our course on advanced data structures at the University of Buenos Aires, students could keep up with our unusually fast pace, thanks to their advanced math skills. Student showed real enthusiasm for the beautiful ideas we were conveying. For example, we taught van Emde Boas trees, and the next morning, three separate groups of students came to us with their working implementations. It was a great environment in which to teach!

      Thanks also for your much-appreciated comment about my class. Having you in that class made a big difference to me. When you have a chance, stop by to catch up.



Leave a Reply