After my first conference rant on competitive analysis (based on my current stints on the SPAA and ICALP committees), I feel it's only fair to spread the love and rant a bit on my fellow algorithmists.
I simply claim the following : if you are presenting an algorithm with the claim that it might be useful in practice, you should aim to include at least a short experimental section showing that you've implemented the algorithm and that it/how it behaves.
Here's why:
1) If your suggestion is it's potentially going to be useful in practice, and it's your algorithm, it's incumbent on you to provide some evidence for this statement. An implementation is the best evidence. I don't expect pages of simulation results examining corner cases (although, if there's space, that's certainly nice); but a couple of paragraphs explaining that you implemented it, tested on basic data, and the program actually finished goes a long way.
2) It's not that I don't trust your math. It's just that -- well, no, it is just that I don't trust your math. Maybe you've proven that the algorithm is O(n^2). I'd like to know if in practice it seems to be O(n log n) [even if it's O(n^2) in the worst case -- now you've given an average-case or special-case open problem!]. I'd like to know if there's a hidden constant of 10,000 there that makes it really not practical in its current form. I'd like to see that you didn't make an error and that it doesn't look like Theta(n^3) when you run it. [I've got 46 papers to look over in a month. Make my job easier, your paper's more likely to get in.]
3) Maybe, just maybe, someone who might actually want to implement your algorithm will actually read your paper. A non-theorist. Don't you think they want to see that it seems to actually work before implementing it better themselves? Won't some experiments make talking about your work to non-theorists easier? Help make that connection...
I'm not saying every algorithms paper needs an implementation section. In many cases, "algorithmic" results are really "complexity" results -- we're just showing that something can be done, we don't actually expect anyone to do it, and in this case there's no need for a simulation or experimental results. (Of course, in such cases, I expect the authors to limit their claims of interest/utility in practice.) In some cases, space won't permit a reasonable evaluation of the algorithm -- but do plan on it for the journal version. In some cases, the coding and evaluation of the algorithm are so interesting it merits an entirely separate paper!
But I'm amazed at how few algorithms papers provide any actual experimental results (unless they're appearing in a networking/database/other systems conference, where it's more understood that results are also expected). I've actually submitted theory papers to theory conferences with experimental sections and had reviewers urge them to be taken out, which I find mystifying (and I ignore).
And yes, if I'm reviewing your paper, and you don't have any numbers where I think you should, I'm probably mentally (and numerically) docking your paper score....
Subscribe to:
Post Comments (Atom)
3 comments:
Amen.
But I would add a few extra comments:
1) Doing a half-hearted experimental section is no good. How many times do I see people processing megabytes of data and considering that this is "large". The seventies have been over for quite some time. If you are not working with gigabytes of data, for many applications, you are just playing with your toys.
If you can do something fast with 50,000 data points, it says nothing about how your algorithm will behave with 100,000,000 data points.
2) This recommendation should not apply only to TCS. Overall in Computer Science and Applied Mathematics, there is too little serious experimental work.
After my Ph.D., I went to do some signal processing in industry. I had signals that would literally use up a CD-Rom (650 MB). That was circa 1999, now the problems in industry are much larger.
I would then try to apply some academic results, and then, upon closer inspection, I would notice things like "oh! the authors tested their scheme over 1024 data points... hmmm... I have 5 orders of magnitude more... I wonder what will happen..." and sure enough, many of the algorithms that were proposed as "fast" just crumble under the load.
3) People people... *constants* matter. They matter a whole lot. Not all O(n) algorithms are the same. Some are ten times slower than others. This matters a lot for practitioners.
4) Not all operations are equal. Random access can be, in some cases, several orders of magnitude slower than sequential access. These effect are almost impossible to measure on paper... you have to run the software.
5) Doing experimental work is a great way to discover new problems and new ideas. There is no way that your brain can be "as smart" as the real world.
6) If everyone did more experimental work, we would collectively value a lot more "simplicity". I am pretty sick of the "here, I was the first to show that this could be done in O(n log n), we are done here". No sir. Until we have practical implementations, we are not done with a problem. And crazy "it could be done" algorithms don't cut: they are worthwhile contributions, but they do not count as solving the problem.
Papers that present algorithms and only an asymptotic analysis are a huge waste of time for people in industry and in other branches of CS.
It might come as a surprise, but the problem you worked on for months is likely to be uninteresting to someone in industry who needs a solution only to solve some other problem.
Here is a typical scenario. A young graduate gets hired and he needs to solve a problem. He is naive, so he searches for research papers claiming to solve that problem. There are 10. He spends two weeks reading and another two months implementing, because the authors didn't bother to say how their method would work in practice. In the end, none works. Now, what do you think that person will think about theory research articles for the rest of his career?
Oh, by the way, I'm always surprised when theoreticians complain about practicians not being up-to-date. If they care about what practicians know, then one would think that theoreticians would write articles for practicians too. Alas, that seldom seems to happen.
Hmmm.... I expected more theorists to respond and defends themselves (especially after daniel and rgrig's comments).
But I guess I'll defend my theorists somewhat. Daniel and rgrig, while I agree in large part with your spirit, I would take exception to what I see as the insistence that theorists should come up with "near-industrial-strength" implementations for experiments. I think that's asking a bit much. Such implementations require their own skill set, and often have system-specific requirements. That's not necessarily where theorists are best qualified. In my post, I ask that they give a "proof-of-concept", which I think means implementing and testing their algorithm (on simple cases).
I'm not saying theorists shouldn't do what you ask; I just don't think it should be required in a theory paper. Certainly one additional problem you raise is the "algorithm engineering" area is generally under-appreciated by the (academic) theory community, so the sort of survey/implementation papers you suggest happen more rarely than they should, which is a shame.
Post a Comment