Ganesh Swami

I’m excited about the Workshop on Modern Massive Data Sets I’ll be attending next week at Stanford.

The 2008 Workshop on Algorithms for Modern Massive Data Sets (MMDS 2008) will address algorithmic, mathematical, and statistical challenges in modern statistical data analysis. The goals of MMDS 2008 are to explore novel techniques for modeling and analyzing massive, high-dimensional, and nonlinearly-structured scientific and internet data sets, and to bring together computer scientists, statisticians, mathematicians, and data analysis practitioners to promote cross-fertilization of ideas.

These are my notes (disclaimer: I’m no expert, corrections are welcome.)

Most algorithm engineers thus far are happy with algorithms that are linear, i.e., in the number of data points in the dataset. With web-scale data, linear is not good enough: sub-linear is required. These streams of data are typically unbounded and do not fit in main memory. They cannot even be stored, as it is infeasible to go back and reload them.

The Frequency Problem is used as a model problem over data streams, for example, computing means/variances, medians, top-k frequent items, distinct elements etc. One approach is to approximate the computation over the stream via random sampling.

There are four topics that keep recurring when looking at proofs of streaming algorithms using randomization:

• Markov’s inequality
• Chebyschev’s inequality
• Holder’s inequality
• Chernoff bounds

This is really key. As an example, suppose we wanted to run some complicated algorithm (offline) over the packets flowing through a router. As this would a huge number of packets, we won’t have the luxury of storing all packets, but only a subset. By sampling the packets with probability p, we can estimate the amount of memory required to store the packets as the expectation value of the binomial variable with parameter p and n, where n is the number of packets going through the router.

The use of one of the bounds over the other is a matter of how tight the bound is. The Markov inequality only uses the expectation value of the random variable while the other use higher moments. They do this by using the Markov inequality to a moment generating function exp(tX) of the random variable X.

You’ll want to check the preliminary program for the kind of topics that are going to be covered. While you are at it, check out the workshop webpage from 2006. I’ll go find something to wipe the drool off my chin…

I know some of my readers are deeply interested in high performance computing and computational physics: this is a post for them. The conference I had mentioned in my previous post was the GROMACS Workshop on Advanced Simulation Methods.

Gromacs is a high performance simulation engine primarily for solving Newtonian dynamics (it also does normal mode analysis, structure minimization and mixed molecular mechanics-quantum mechanics simulations.) It was an industry leader in terms of raw single processor performance for many years, until Desmond from D.E. Shaw Research took over with their super-scalable algorithms (I’ve written about this before.) With Gromacs 4.0, they’ve fixed the scalability problems and with a variety of other algorithmic fixes, they are the top dog once again. Disclaimer: these are all claims by relevant parties and I have not verified them myself, though I’d love to do so unencumbered. Though the Gromacs 4.0 paper is published, I’ll only be writing about it when the actual product is released.

The focus of the workshop was on algorithms, though there were some applications too. I’m sure an applications person would have felt out of place, but I felt I had something to contribute in almost every topic that was discussed. I’m archiving the list of topics here for posterity:

• The new domain decomposition parallelization in Gromacs 4.0, with some tips & tricks to get the most out of your hardware
• Different methods to perform free energy calculations. Slow-growth, perturbations, Bennett Acceptance Ratio. Which protocol is most efficient, and what new things will be in Gromacs 4.0?
• QM/MM. How do you mix Quantum Mechanics with Gromacs?
• Virtual sites for hydrogen motion removal and long time-steps
• Membrane protein simulations
• Replica exchange, and extracting kinetic data from it
• Local pressure extensions to Gromacs
• Gromacs source code walk-through

The take home message: strong coupling between various pieces of the algorithm is anti-thesis to parallel scalability. The CPU industry seems to have hit a brick wall in terms of improving raw computational speed: the future is in multi-core. Therefore, remove the coupling with better algorithms and you are on your way to highly scalable and by definition superbly fast algorithms.

The timestep used in an integrator while solving a set of equations inherently determines the speed of the algorithm. Big timesteps will make the algorithm unstable as you your trajectory will not be able to follow the phase space manifold accurately (as a side note Euler-type integrators also become unstable as you make the timestep smaller, but this is the least of your worries with a non-symplectic integrator.) The Nyquist theorem determines the sampling rate, so removing fast (or high frequency) degrees of motion such as hydrogen bond vibrations with constraints on them is required for a big timestep. Usual constraints algorithms are coupled leading to undesirable non-scalable algorithms. The Gromacs developers have solved this with a new constraints algorithm called P-LINCS.

I was at the BC Technology Impact Awards ceremony last week representing my company Zymeworks. Zymeworks was nominated for the most promising pre-commercial technology company, but unfortunately we didn’t win. The award in this category went to Lignol Energy Corp., a clean tech company.

The organizers had tiled one wall of the Banquet Hall with a 100 feet screen. They had calibrated multiple projectors to blend the edges. Pretty impressive. You can get this technology from a couple of companies: here’s one.

Abebooks.com, an online market for new and used books also won an award. I’ve been using this website for the past couple of years to get used textbooks. Highly recommended.

John MacDonald, the founder of MDA (the ‘M’ in MDA) and of Day4Energy Inc. got the Person of the Year award. It’s truly an honor to be in the same room with the accomplished!