Google loses Linux patent suit

An East Texas Jury has decided that Google has been infringing a patent through its use of Linux and must pay $5 million to East Texas based Bedrock Computer Technologies. The suit, filed in 2009, concerns patent 5,893,120, "Methods and apparatus for information storage and retrieval using a hashing technique with external chaining and on-the-fly removal of expired data", filed in 1997 and granted in 1999.

Bedrock claimed that the technique outlined is used in Linux and on that basis sued Google, Yahoo, MySpace, PayPal, Amazon, Match.com, AOL, CME Group and two small software companies – Softlayer and Citiware, based in East Texas – for patent infringement. The latter two companies were included apparently to ensure that the cases be heard in East Texas's patent litigation friendly courts.

Bedrock's specific claim is that versions of Linux post version 2.4.22 or after, or version 2.6.25 or later, contain code which infringe the first two claims of the patent:

1. An information storage and retrieval system, the system comprising:

a linked list to store and provide access to records stored in a memory of the system, at least some of the records automatically expiring,

a record search means utilizing a search key to access the linked list,

the record search means including a means for identifying and removing at least some of the expired ones of the records from the linked list when the linked list is accessed, and

means, utilizing the record search means, for accessing the linked list and, at the same time, removing at least some of the expired ones of the records in the linked list.

2. The information storage and retrieval system according to claim 1 further including means for dynamically determining maximum number for the record search means to remove in the accessed linked list of records.

The case dockets make reference to a file by the name of route.c being entered into evidence by Bedrock. The patent itself is not about the simple implementation of a chained linked list but the idea of removing expired records while traversing the list when searching for records and setting a limit on the number of records being removed to avoid searches spending all their time deleting expired records.

As the case progressed, a number of the defendants, being Red Hat customers, called on Red Hat to intervene, which it did in December 2009 with a separate suit and then directly, seeking to have the patent declared invalid. Update - Red Hat's direct intervention was blocked, but the separate suit is still ongoing.

On 11 April, a jury trial for Bedrock vs. Google began. Google's defence was that it did not infringe on the first two claims of the patent and that the patent itself was invalid. The trial ended on 15 April with the jury deciding that Google had infringed and setting compensation for Bedrock at $5 million. Bedrock has also sought an injunction against Google to prevent it from infringing further, but there has not yet been a ruling from the court on that matter.

Google is expected to appeal after issuing a statement saying it "will continue to defend against attacks like this one on the open source community". The cases are also still ongoing for the other defendants and Red Hat.

Update - Match.com settled its case with Bedrock on 28 March. Terms of the settlement were not disclosed.

(djwm)