A primary goal of algorithm engineering is to provide practitioners with well-engineered solutions to important algorithmic problems. Our beliefs as to which problems are important to practitioners have been based primarily on anecdotal evidence. To provide more objective information, it seems useful to conduct ``market research'' for the field of combinatorial algorithms, by determining which algorithmic problems are most in demand in applications, and how well currently available implementations satisfy this demand.
This paper is an attempt to answer these questions.
We present an analysis of 1,503,135 WWW hits recorded on the
Stony Brook Algorithms Repository
over a one year period, from February 22, 1998 to February 27, 1999.
The Repository (http://www.cs.sunysb.edu/
algorith)
provides a resource where programmers, engineers, and scientists
can go to find implementations of algorithms for fundamental problems.
User feedback and WWW traffic statistics suggest that it has proven
valuable to people with
widely varying degrees of algorithmic sophistication.
The structure of the Algorithms Repository makes it well suited to measure the interest in different algorithmic problems. For each of 75 fundamental algorithm problems, we have collected the best publicly available implementations that we could find. These problems have been indexed in major web search engines, so anyone conducting a search for information on a combinatorial algorithm problem is likely to stumble across our site. Further, special indexes and hyperlinks aboard our site help guide users to other relevant information.
This paper is organized as follows. In Section 2, we discuss the structure of the Algorithms Repository in more depth, to provide better insight into the nature of the data we present below. In Section 3, we analyze WWW traffic to determine the most popular and least popular algorithmic problems. In Section 4, we report on what our users are finding. Each implementation available on the Repository has been rated as to its usefulness for the corresponding problem. By studying these ratings, we can assess the current state of the art of combinatorial computing, and see how well it matches user demand. Finally, in Section 5, we attempt to get a handle on where the interest in algorithms is located, both geographically and professionally.
The only other attempt at polling interest in algorithmic problems which I am aware of is by Crescenzi and Kann [#!CK-98!#], who use WWW hits on their compendium of NP optimization problems to measure interest in different NP-hard problems. Any polling-based research is subject to a variety of bias and ambiguities. I make no grand claims as to how accurately this data measures the relative importance of different algorithmic research to society. I found many of the results quite surprising, and hope they will be of interest to the algorithmic community.