Moderately good problems in computer science.

It seems that there is no lack of important moderately difficult problems in Computer Science that require about 1 or 2 days of thinking and about a months of implementation. Lets talk about one such example problem:

Problem 1: Find near duplicate documents?

Application: Search.

One reasonable problem definition: make hash of random points from the documents such that if x1 is a near duplicate of x2, both x1,x2 will have same hash.

A reasonable solution: Make a 128 bit MD5 of the document (better, do that for paragraphs, sentences, n-grams). Choose part of the hashes from the parts of the documents in an order to increase probability of matching near duplicates.

Broader's paper: This paper is actually a good paper since it not only provides a reasonable solution, it defined the problem nicely and gave a solution with a bound for near duplicate matching. Similar techniques are implemented in Goog and in MSFT and in many other search companies for their production near duplicate detection tasks.

You can read Broader's slides here.