Many papers in Computer Science tell the following story:

• There is a pre-existing problem P.
• There are few relatively simple but effective solution to problem P. Among them is solution X.
• We came up with a new solution X+ which is a clever variation on X. It looks good on paper.
• We ran some experiments and tweaked our results until X+ looked good. We found a clever way to avoid comparing X+ and X directly and fairly, as it might then become obvious that the gains are small, or even negative! We would gladly report negative results, but then our paper could not be published.

It is a very convenient story for reviewers: the story is simple and easy to assess superficially. The problem is that sometimes, especially if the authors are famous and the idea is compelling, the results will spread. People will adopt X+ and cite it in their work. And the more they cite it, the more enticing it is to use X+ as every citation becomes further validation for X+. And why bother with algorithm X given that it is older and X+ is the state-of-the-art?

Occasionally, someone might try both X and X+, and they may report results showing that the gains due to X+ are small, or negative. But they have no incentive to make a big deal of it because they are trying to propose yet another better algorithm (X++).

This process is called citogenesis. It is what happens when the truth is determined solely by the literature, not by independent experiments. Everyone assumes, implicitly, that X+ is better than X. They beauty of it is that you do not even need for anyone to have claimed so. You simply need to say that X+ is currently considered the best technique.

Some claim that science is self-correcting. People will stop using X+ or someone will try to make a name for himself by proving that X+ is no better and maybe worse than X. But in a business of science driven by publications, it is not clear why it should happen. Publishing that X+ is no better than X is an unimpressive negative result and those are rarely presented in prestigious venues.

John Regehr made a similar point about our inability to address mistakes in the literature:

in many cases an honest retrospective would need to be a bit brutal, for example to indicate which papers really just were not good ideas (of course some of these will have won “best paper” awards). In the old days, these retrospectives would have required a venue willing to publish them, (…), but today they could be uploaded to arXiv. I would totally read and cite these papers if they existed (…)

But there is hope! If problem P is a real problem, for example, a problem that engineers are trying to solve, then you can get actual and reliable validation. Good software engineers do not trust research papers: they run experiments. Is this algorithm faster, really? They verify.

We can actually see this effect. Talk to any Computer Scientist and he will tell you of clever algorithms that have never been adopted by the industry. Most often, there is an implication that industry is backward and that it should pay more attention to academic results. However, I suspect that in a lot of cases, the engineers have voted against X+ and in favor of X after assessing them, fairly and directly. That is what you do when you are working on real problems and really need good results.

Credit: This blog post was inspired by a comment made by Phil Jones on Google+.

Whether you submit your work scientific journal or just post it on a blog, you can expect to receive harsh criticism from time to time. Sometimes you are facing arrogant or ignorant readers. Other times, your work is genuinely flawed. My own work is frequently flawed, as you know if you read this blog.

Over time, I have learned that even if the reviewer is wrong, spending time to careful respond can be tremendously useful. If you are 100% correct, then you get to build up your confidence and can later answer similar criticism hastily. Very often, however, you did not do everything perfectly. Maybe your arguments and data are correct, but you might have presented them better.

There are specific strategies to deal with harsh reviews:

• Expose yourself regularly to criticism from total strangers. In my experience, if you rarely publish, you are more likely to have difficulty dealing with criticism. I have been called an idiot, I have had to deal with overly aggressive people and I have been ridiculed on occasion. Of course, I occasionally get depressed after receiving harsh criticism, especially if I thought I had produced great work and feel unappreciated, but I am typically able to recover mentally in minutes or, at least, hours. Part of it is just habit: my brain has learned that harsh criticism does not necessarily signify upcoming pain.
• It is critically important to distinguish yourself from your work. If someone repeatedly produces inferior work, his reputation will suffer. However, everyone (even Nobel prize winners) gets it wrong from time to time. It is important to keep in mind that most reviewers do not care that much about you. In fact, they often quickly forget about you while you ruminate over their review.
• The best way to address criticism is to take it one comment at a time. If someone finds ten different flaws in your work, don’t look at it as one message: break it into ten components and address each one separately. This approach scales up linearly: it just take ten times longer to address 10 flaws than one. Brian Martin describes it well:
  

  I’ve found a way to make the revision process easier. I don’t reread my text, because that just cements my previous approach. Instead, I go through the recommendations of the referees and the editor one by one, making changes. After I finish all those changes, large and small, I print out the whole article and read through it, fixing up expression and making it flow.

  Tackling recommendations one by one is important psychologically. Looking at a list of criticisms, sometimes pages of them, can be demoralizing; the task seems too big. Focusing on a single point is easier. Once it’s done, you can check it off and proceed to the next point, either immediately or tomorrow.

  Sometimes responding to a point requires additional work, such as obtaining and reading some new theory or doing some new calculation. It’s helpful to write down every step that’s required – for example, (1) order Smith’s book, (2) read the theory section, (3) write a one-paragraph summary – and tackle them one by one.

Open access journals make articles freely available. Some of them even allow the authors to keep the copyright of their work. It would seem that they offer a compelling alternative to traditional journals, especially if you hope to reach to people outside academia.
However, open access may allow you to get a free copy of an article, but your rights might still be limited. For example, videos on YouTube are freely available, but you are not allowed to copy or reuse them freely.

The directory of open access journals gives a list of over 300 open access journals in Computer Science. Thus, finding an adequate open access journal where you can submit your work is relatively easy.

However, there are a few sore points.

1. Indexing of open access Computer Science journal is generally weak

A journal needs to be indexed so that your fellow researchers can find out about your work. Most open access journals will be indexed by Google Scholar, but other indexes are important in Computer Science such as DBLP and the ACM Digital Library. Scopus is also often used by hiring and promotion committees. (Scopus is run by Elsevier.)

As I review the open access journals in Computer Science, I find that indexing is often a sore point. The next table shows that the ACM Digital Library does a poor job at indexing open access journals. In fact, I could find only two open access journals indexed by ACM. It cannot be explained by the prestige of the respective journals: some of these open access journals that ACM fails to index are just as good or better than others it indexes. And, of course, no ACM publication is open access. Quite clearly, ACM is doing little to help open access.

Elsevier and Springer allow authors of papers in some regular journals to make them available under an open access format in exchange for a one-time fee. Their journals are typically well indexed so they may offer good alternatives.

2. Many open access Computer Science journals require complete copyright transfer

To publish an article, a journal does not require complete copyright ownership. The only valid justification for requiring that the author gives away his copyright is to restrict access. When reviewing open access journals in Computer Science, I see that several of them inexplicably require complete copyright transfer:

Conclusion There is still much room for progress.

There is a growing list of famous scientists who have pledged to boycott Elsevier as a publisher. If I were in charge of Elsevier, I would be very nervous: academic publishers need famous authors more than the famous authors need the publishers. After all, famous scientists could simply post their work online, and people would still read it.

Elsevier has committed too many sins to give an exhaustive list: they have created fake academic journals so that pharmaceutical corporations could claim that certain facts appeared in a journal, they have sponsored evil regulations, and they have restrictive views on what constitutes fair use. Unbelievably, they were also involved in arms trade. They probably have the devil on their board of directors.

The boycott is currently lead by a famous mathematician, Timothy Gowers. Gowers accuses Elsevier of charging exorbitant prices for its journals.

Focusing solely on database-related journals, I decided to look at how much journals charge per article.

Observations:

• The price distribution appears almost random. I can see no relation between prestige or paper length and prices.
• Elsevier is hardly alone at charging high prices for papers. Wiley and Springer are just as expensive. Of course, it is possible that Elsevier ends up charging more through deals and bundling.
• ACM is very inexpensive on a per-article basis. However, ACM often asks the authors to pay page charges whereas Elsevier rarely does in my experience.
• Though SIGMOD Record is limited to short contributions, its price is unbeatable. And it has no page charge. Moreover, it is generally a well regarded publication venue among database researchers.

My take: The evidence is strong that high-quality inexpensive journals are possible. Current journals are up to an order of magnitude too expensive. However, Elsevier is selling what we want to buy: prestigious journals that people outside the best schools cannot afford. Just like middle-income Americans get into debt to keep up with the top 1%, colleges increase their library budgets to keep up with Stanford and Harvard.

The solution to overpriced journals is to reduce library purchasing power. Most colleges do not have the infinite budgets Harvard and Stanford have, and they should not act like they do. In fact, if we could reduce the purchasing power of most libraries to zero, then researchers and students would be forced to pay $20 or more per article. You can be quite certain that they would mostly read the cheaper (and more competitive) journals. And Stanford researchers want to be cited by the researchers from the lesser institutions so they would also migrate away from overpriced journals. Reduced budgets would still allow publishers like Elsevier to make generous profits, but they would only profit by offering great products at an affordable price.

Disclaimer: I am currently reviewing a paper for Pattern Recognition (an Elsevier journal), and I recently published in Discrete Applied Mathematics (another Elsevier journal).

Update: Though you can get articles from SIGMOD Record for free if you to the SIGMOD Record home page, ACM sells them through its Digital Library for over $10 a piece.

Hashing is a programming technique that maps objects (such as strings) to integers. It is a necessary component of hash tables, one of the most frequently used data structure in Computer Science.

Typically, Hash tables have the property that looking up or storing a value associated with a key requires constant time. If you use user identifiers to retrieve names and phone numbers, you can scale up to millions and millions of users without performance penalty. However, the worst case complexity of a hash table is linear: it may need to go through most values each time you want to look up a key. Thankfully, the worst case is typically improbable: it only happens when too many objects hash to the same value. In practice, hash functions are chosen so as to spread hash values uniformly (pseudo-randomly).

Most programming languages like Java or C++ use deterministic hash functions. This means that given a string, it will always hash to the same integer, for all Java software in the whole world. And overall, deterministic hashing works quite well. Unfortunately, deterministic hashing is insecure. If your are building a web application, and hackers know which hash function you are using, they can create a denial-of-service attack and bring down your application. The gist of it is not complicated: it suffices to ensure that the hash tables fall back on their worst case performance.

This is very serious: it means that if you rely on the default hash functions of your programming language (e.g., String.hashCode in Java), your application could be at risk. On this issue, Alexander Klink and Julian Wälde issued a well written security advisory.

The fix is relatively simple: programming languages need to adopt random hashing. In random hashing, every time the software is initialized, a new hash function is picked, at random. This does not make attacks impossible, but it makes them much more difficult.

The problem is not novel. In 2003, Crosby and Wallach raised the issue and many responsible vendors fixed their products. Alas, the only programming languages to adopt random hashing were Ruby and Perl. Others are more reluctant.

So, how easy is it to hack the hash functions in, say, Java? Java uses an iterated hash function. At each iteration, iterated hash functions compute a new hash value from the preceding hash value and the next character. Strings in Java are hashed using the function
F(y,c) = 31 y + c.
where y is the previous hash value and c is the current character value. Thus, the hash value of a string made of the characters 65, 66 (corresponding to “AB” in ASCII) is 31 times 65 + 66 which is 2081.

Why does Java uses the number 31? The choice is somewhat arbitrary (and 31 might fail to be ideal) but because it is an odd number, the compression function F is permuting which helps distribute more uniformly the hash values.

It is fairly hard to construct reasonable strings that collide over 32 bits in Java. However, a modest hash table will use only the first few bits of the hash values. Let us consider only the first 16 bits. It is not difficult to check that the strings “Ace”,”BDe”,”AdF” and “BEF” all have the same hash value in Java.

Of course, having 4 strings colliding will not disrupt hash tables. But because the hash function is iterated, we can multiply the number of collisions. Indeed, any two same-length sequences of these four colliding strings will also collide. This means that you can construct 16 strings of length 6 all colliding (“AceAce”,”AceBDe”,”AceAdF”, “AceBEF”, “BDeAce”,”BDeBDe”,”BDeAdF”, “BDeBEF”, “AdFAce”,”AdFBDe”,”AdFAdF”, “AdFBEF”, “BEFAce”,”BEFBDe”,”BEFAdF”, and “BEFBEF”). You can keep going to 64 strings of length 9. And so on.

How badly does this impact the performance of a hash table? I tried inserting all the colliding strings in a Java Hashtable container. For comparison, I also inserted randomly chosen strings into either a Hashtable or a TreeMap (tree structure). The net result is that what should be a tiny cost (0.006 s) becomes a massive cost (30s). A server able to process thousands of queries per second might quickly become bogged down trying to process a couple of queries per second.

For these tests, I am using a MacBook Air with a 1.8 GHz Intel Core i7 running Java 6. My code is available.

Why aren’t programming languages adopting random hashing? A potential issue is that language designers like determinism. They much prefer reproducible bugs. Nevertheless, any expert programmer should be aware of this problem.

Further reading:

• Scott A. Crosby and Dan S. Wallach, Denial of Service via Algorithmic Complexity Attacks, Usenix Security’03.
• Daniel Lemire, The universality of iterated hashing over variable-length strings, to appear in Discrete Applied Mathematics.

Update: I initially reported that Ruby was the only language to adopt random hashing. In fact, Perl adopted random hashing with version 5.8.1. In version 5.8.2, Perl adopted an hybrid that switches between a deterministic and a random hash function when needed. (Thanks to Mike Giroux for the pointer.)