KSM runs into patent trouble

As a special case it's worth doing the research if you have some confidence you'll find nothing, and if you expect "We looked and found nothing" to be a major "selling point" for your software. See GNU zip (gzip) IIRC.