WingNews logo WingNews GitHub [2]
top | item 1075505

Ask HN: Cases where software patents have prevented progress?

57 points| pg | 16 years ago | reply

A student writing a thesis about software patents emailed me asking about cases "in which having a patent on an algorithm prevented some significant technological progress." HN seemed the best place to find answers. What are the clearest examples of this happening, and how much did they slow things down?

74 comments

order
[+] petewarden|16 years ago|reply
I have a couple of examples from my personal experience, neither earth-shattering, but when you consider X million engineers running into similar issues, the cumulative tax on innovation is pretty large.

Working on F1 '98, we had to scrap a whole training mode where you'd see your time compared to previous laps because lawyers were concerned it overlapped with the Atari 'ghost car' patent:

http://kotaku.com/270035/patents-are-interesting-ghost-mode

We spent a lot of time and energy trying to work around this, we weren't showing any kind of ghost car, just a time indication, but apparently the patent was broad enough to cover any kind of comparison.

The second was a patent on controlling any kind of video effect based on a sound input(!). This severely constrained what we could do on a major video-processing package, forcing us to avoid some features. They tried to extort independent developers out of a lot of cash, despite being a painfully obvious idea that had been around for decades before the patent was filed:

http://www.trapcode.com/US_SK_advisory.html

[+] ivankirigin|16 years ago|reply
Xerox Parc has a patent on a type of filter viewer that acts like a looking glass to see the effect of the filter. Every year, someone reinvents it and presents it at some HCI conference, only to be told they can't use it. They are sitting on it, not building it, and also enforcing it.

SIFT is a vision technique that is patented and works very well. Patents are getting in the way of commercial progress http://en.wikipedia.org/wiki/Scale-invariant_feature_transfo...

Amazon Onc-Click is an absurd patent. If we grew to scale, Tipjoy would probably have had to pay them money, like Apple does.

[+] jojopotato|16 years ago|reply
The patent on SIFT is particularly frustrating because it's free for researchers to use so it ends up in every paper that concerns interest point recognition. So if you ever wanted to build an application implementing paper research, it makes it kind of tricky.

A fairly decent alternative (although less resistant to rotation) is SURF which isn't under a patent AFAIK.

[+] motters|16 years ago|reply
The SIFT patent probably is preventing progress in computer vision products, since I think it's exclusively licensed to one or two companies. I know of folks who have asked permission to use SIFT within a product and been told that they can't have it.
[+] mattmaroon|16 years ago|reply
Does Amazon actually enforce that? My understanding (perhaps incorrect) was that they quit after the hubbub when they tried it on Barnes and Noble. Also, isn't Bezos notoriously opposed to software patents?
[+] pmichaud|16 years ago|reply
One thing that's difficult to measure but probably not trivial is the overall cooling effect. What I mean is that the tangible cases in which patents really ran into conflict don't indicate the number of cases in which technologies were never researched to begin with because of the risk of infringing a patent.

The cooling effect probably isn't significant for the mythical basement hacker who does it for love, but decisions about what research to pursue are made all the time in larger companies, and one of the factors is potential for legal trouble.

[+] DanielStraight|16 years ago|reply
This is an excellent point. Basically the patent minefield concept. The insanity of software patents has created an overall sense of fear. There is no way to quantify this aspect of patents' negative effect on progress.
[+] gridspy|16 years ago|reply
The basement hacker still runs into trouble when they try to translate their cool technology into a viable startup and cannot source funding.

It is hard to find funding when you are immobilised in a minefield.

[+] fragmede|16 years ago|reply
Microsoft's long filename in FAT filesystem patent was recently threatened against TomTom (http://lwn.net/Articles/320737/).

Instead of working on new features (whatever they may have been), TomTom must instead commit resources to working around the patent.

[+] jacquesm|16 years ago|reply
Excellent example.

Many camera manufacturers faced similar obstacles, and ended up fragmenting the market with proprietary formats or paying the 'microsoft tax'.

[+] mrshoe|16 years ago|reply
I would point to the current HTML5 video element debacle:

http://lists.whatwg.org/htdig.cgi/whatwg-whatwg.org/2009-Jun...

Patents are playing a large role in ensuring that what could be a wonderful thing for the web will almost certainly not be.

[+] fragmede|16 years ago|reply
I'd say that HTML5 is the tip of that particular iceberg.

I mean, what was HTML 5 supposed to change? The fact that video (and audio) is broken on the web, leaving to flash as the closed de-facto standard. The whole situation that HTML5 was supposed to fix is, itself, a result of codec licensing/patent issues.

I'd venture that without those issues, the <object> and <embed> tags would have had a bigger impact.

[+] GHFigs|16 years ago|reply
June 2009 is not "current". That issue (of making one or another codec mandatory in the HTML5 spec) is dead with decision you linked, for the reason that "if a browser refuses to implement something, then we can't require it".

I'm being pedantic here, but I think it's very misleading to connect the spec issue with your conclusion that <video> could have been nice but somehow isn't. Had one or the other codec been made mandatory in the spec, the reality today would be exactly the same.

[+] aristus|16 years ago|reply
Singular Value Decomposition was held back for 20 years by patents owned by BellCore. I had to scrap large interesting portions of Dowser to avoid potential problems.

As a counterexample, Autonomy has a patent on Bayesian text classification dating from the late 90's. I've always wondered why they didn't say anything after Paul popularized it for spam filtering.

[+] yuvi|16 years ago|reply
Elliptic curve cryptography and LDPC codes are two that come to mind.

Though afaik the latter hasn't really been improved since ~1960 and were only patented after rediscovering them in 1993, and I have no clue whether progress in elliptic curve cryptography stalled due to patents or because they don't offer any practical benefits over RSA.

[+] smokinn|16 years ago|reply
I still don't know what the issue with supporting multi-touch devices in North America is but I strongly suspect it's because of software patents. Anytime a corporate rep is asked why their device doesn't support it they hem and haw and say that it's complicated but never give a real answer.
[+] btilly|16 years ago|reply
There is a ton of really interesting and cool stuff that was done in wavelet research years ago which got patented and hasn't really seen the light of day in the way it should.

If the patents hadn't existed I'm sure we'd now have much better widely available voice recognition, image recognition, and related data processing software than we do now.

[+] tmitchell|16 years ago|reply
During development of Doom 3, id Software fell into a bit of a patent conflict with Creative. Relevant snippet from http://en.wikipedia.org/wiki/Doom_3:

"A week before the game's release, it became known that an agreement to include EAX audio technology in Doom 3 reached by id Software and Creative Labs was heavily influenced by a software patent owned by the latter company. The patent dealt with a technique for rendering shadows called Carmack's Reverse, which was developed independently by both John Carmack and programmers at Creative Labs. id Software would have placed themselves under legal liability for using the technique in the finished game, so to defuse the issue, id Software agreed to license Creative Labs sound technologies in exchange for indemnification against lawsuits."

I remember something about Carmack coming up with a workaround that paid a performance penalty so others licensing their engine could bypass the Creative mess.

Creative has also taken quite a bit of heat over the years for sitting on Aureal's IP and stifling innovation in sound technology, but I don't have specific examples to cite.

[+] dstorrs|16 years ago|reply
I worked at a company called Pica9, generating PDFs on the fly. Another company has the patent on that, so we had to spend a considerable amount of effort working around it, making sub-optimal choices at easy decision point in order to make it legal.
[+] jchonphoenix|16 years ago|reply
The most obvious one that comes to mind is LZW, which basically killed the entire compression scheme.
[+] dpcan|16 years ago|reply
This question is circular.

The potential "technological progress" doesn't exist because it was thwarted by software patents, so there really is no way of knowing what doesn't exist because it couldn't be created to begin with.

So, are you asking us what things don't exist?

[+] pg|16 years ago|reply
No; the question asks what things would have existed. This is a concept people use all the time in everyday life without provoking ontological crises. E.g. if you say "he would have scored a touchdown if that last defender hadn't tackled him," everyone knows exactly what you mean. You can never be 100% certain about things that would have happened, so you qualify your conclusions, but it's not the case that you can't reasonably talk about such things.

I can't believe I just had to write that. This is why forums are such a time sink. If you were watching a football game with your friends and someone said "he would have scored if that guy hadn't tackled him" and you replied "how can you talk about touchdowns that don't exist?" everyone else would just roll their eyes and not invite you over anymore. But here in the world of text these subtly graduated social cues don't exist; all you can do is reply with more text. I wonder if there is some kind of solution to that.

[+] jacquesm|16 years ago|reply
I think it is a perfectly valid question. If someone got sued by the holder of a patent and withdrew a piece of software or an application then that's proof positve.

http://brej.org/yellow_star/letter.pdf

Would be a nice example, in http://brej.org/yellow_star/ there is a bit that says "There are instructions which are patented by MIPS and have been removed.".

That's a clear impediment to progress, once the MIPS instruction set was documented and people started to write software for it anybody ought to be free to re-implement these instructions for the express purpose of interpreting MIPS object code.

[+] DenisM|16 years ago|reply
By analogy - name a great business impeded by corruption in the government. Unm. We know there are great businesses in America and not that many in (more) corrupt countries, but we can't point at killed businesses themselves.
[+] te_platt|16 years ago|reply
By progress do you mean creation of new technology or making technology available? A case I followed (involving infringement on a fingerprint recognition patent) shows how even weak patents slow the development process.

Summary - Small company receives patent, sues large companies for infringement, two years and more than a million dollars later patent is invalidated, technology moves on. All the gory details here:

http://www.legalmetric.com/cases/patent/utd/utd_206cv00115.h...

[+] aidenn0|16 years ago|reply
It's been speculated that Apple dropped ZFS due to patent concerns.
[+] wmf|16 years ago|reply
Yeah, the NetApp-Sun ZFS lawsuit is like a big "patent minefield here" sign.
[+] bioweek|16 years ago|reply
Were there patents on compression algorithms? Are there any weird things Linux has to do to work around patents?
[+] jws|16 years ago|reply
In general, anywhere you find Huffman coding being done, it could achieve superior compression with Arithmetic Coding but is not because of IBM's patents.

This is essentially every JPEG image on the planet. The standard provides for arithmetic coding, but no one implements it because of the patent. Wikipedia asserts that arithmetic coding saves about 5% of the files size.

So that is 5% of every flash card sold for a camera wasted and 5% of the bandwidth costs for images on the internet wasted.

If GATT hadn't tacked on three more years in 1995 these would have expired by now, but it looks like 2012 or 2013 is the date now.

The MPEG series of standards probably could also have benefited similarly from Arithmetic Coding.

[+] wclax04|16 years ago|reply
LZW, but that is the problem with GIFs; and the subsequent move to PNGs
[+] pmjordan|16 years ago|reply
There's the FAT32/vfat issue that caused Linus to take out the write support for long filenames. Not helpful, but I wouldn't call it impeding innovation.
[+] 10ren|16 years ago|reply
Not an example, but there are many cases of people "working around" a patent. In this case, it is a spur to technological progress. That is, preventing progress can encourage progress.

There's a "prospect" theory for patenting (which with this student is probably familiar), that a patent is like staking a claim to minerals, with a samilar effect: that it encourages others to stake claims nearby, and so explore that region. If others could use the same area as the patent, they wouldn't be encouraged to explore, and you'd get a technological monoculture (in another sense, this would be greater progress, in that it is more widely adopted).

I've been trying to think of an example, but I can't. I think the main way a patent can block progress is if the technology is not exploited well by the owner (like smalltalk being too expensive), and in such cases, we don't hear of it. When a patented technology is exploited successfully, money and time is reinvested in developing it, so that progress on it is accelerated.

[+] eru|16 years ago|reply
However --- imagine that the claims on minerals would be hard to see [1], and accidental violation would put you at great legal risk. Then people might get discouraged from staking claims in that general region.

[1] It's not easy to look through all the patents before building anything --- and may even be harmful to your legal position.

[+] petercooper|16 years ago|reply
Apple's patents on sub-pixel text anti-aliasing. The text in both Windows and Linux looks hideous by comparison. You can enable these features in certain situations on Linux with extra packages, though.

Correctional update: Microsoft holds patents in this area but Apple has a cross-licensing agreement on them.

[+] vetinari|16 years ago|reply
Apple has patents on truetype hinting, not subpixel anti-aliasing. Ironically, when working around this patent, it is easier to get results similar the OSX, rather than similar to Windows.