Texas jury finds Google infringes a patent: $5,000,000 damage award

http://fosspatents.blogspot.com/2011/04/texas-jury-finds-against-google-in.html

by FlorianMueller • 15 years ago

68 65 15 years ago

fosspatents.blogspot.com

jrockway2• 15 years ago

This is one of the disadvantages of open-source software: the patent trolls can easily find places that are violating their bullshit patents. I'm sure Microsoft and Apple also use linked lists, but they're not being sued, because it's harder to prove.

shareme• 15 years ago

are we actually sure of what is being reported??... he has miss-reported before

ggeorgovassilis• 15 years ago

About some files in the JDK copied [1] from Sun/Oracle. I think that was, to put it in Wikipedia terms "original research" and that's always risky. Florian was right about the files but his conclusions about the gravity of those findings were wrong as they were not shipped in the end-product.

[1] http://fosspatents.blogspot.com/2011/01/new-evidence-support...

tzs9• 15 years ago

This is ridiculous. The author has a long and excellent record fighting against software patents. On a couple of occasions his analysis may have been an error, but I don't think he's ever mis-reported anything. You comment is just FUD.

orangecat• 15 years ago

There's a good chance that he's a paid anti-Google shill: http://lwn.net/Articles/434587/. Note that in this case he immediately jumps from the verdict to "Android is doomed", when the case had nothing to do with Android specifically except that it uses Linux, as do millions of other products.

cookiecaper2• 15 years ago

I disagree. I'm also looking for a better source. Florian Mueller has a very bad reputation and was the guy behind "Boycott Novell".

naner2• 15 years ago

> The author has a long and excellent record fighting against software patents.

Based on what? All we have is your (and his) assertion. I had trouble finding any history at all of this guy with "25 years software industry experience". And every single one of his blog posts portrays FOSS software as an unreliable IP minefield. Even if that's not the specific legal issue at hand.

In my opinion this looks like he is paid to smear FOSS.

yuhong• 15 years ago

Another example of this: http://www.groklaw.net/article.php?story=20110420141724403

z0r3• 15 years ago

What a perfectly ridiculous patent.

tzs9• 15 years ago

I find it hard to believe that in the time between the story appearing and your comment you had time to read and understand the patent.

z0r3• 15 years ago

Admittedly, I only read up to the end of the claims section here:

http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sec...

If you read those and skim to see passages like these:

"The problem, then, is to provide the speed of access of hashing techniques for large, heavily used information storage systems having expiring data and, at the same time, prevent the performance degradation resulting from the accumulation of many expired records. Although a hashing technique for dealing with expiring data is known and disclosed in U.S. Pat. No. 5,121,495, issued Jun. 9, 1992, that technique is confined to linear probing and is entirely inapplicable to external chaining. The procedure shown there traverses, in reverse order, a consecutive sequence of records residing in the hash table array, continually relocating unexpired records to fill gaps left by the removal of expired ones.

Unlike arrays, linked lists leave no gaps when items from it are removed, and furthermore it is not possible to efficiently traverse a singly linked list in reverse order. There are significant advantages to external chaining over linear probing that sometimes make it the method of choice, as discussed in considerable detail in the aforementioned texts, and so hashing techniques for dealing with expiring data that do not use external chaining prove wholly inadequate for certain applications. For example, if the data records are large, considerable memory can be saved using external chaining instead of linear probing. Accordingly, there is a need to develop hashing techniques for external chaining with expiring data. The methods of the above-mentioned patent are limited to arrays and cannot be used with linked lists due to the significant difference in the organization of the computer's memory."

The triviality of the patent should be fairly evident (but if I've jumped to a bad conclusion, I'm happy to be corrected). Fair point though!

burgerbrain6• 15 years ago

It's pretty easy to assert that all software patents are "ridiculous". Math is generally held to be unpatentable after all.

hvs• 15 years ago

Actually, if it's a software patent, there's a really good chance that it is ridiculous on the face of it.

z0r3• 15 years ago

I don't think you deserve to be downvoted because I made a whitenoise comment. I should have pasted the explanation I made in my defensive response in the first place or not bothered at all. My bad.

Jabbles• 15 years ago

I find it hard to believe that a jury, selected at random, would have the necessary background to understand the patent. US patent law is notoriously subtle and complicated.

jrockway2• 15 years ago

It's a software patent, so there's no need to read it in order to reach the grandparent's conclusion.

drallison• 15 years ago

I did a quick read of the patent, 5,893,120 filed in 1997. It seems likely to me to be invalid over the prior art.

kenjackson5• 15 years ago

The jury dismissed Google's invalidity defense. This is a case where re-examination might be better. A lot of juries simply may not feel comfortable overturning the PTO, even with a lower standard of proof.

epenn• 15 years ago

Here is a link to the full text of the patent in question: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sec...

tzs9• 15 years ago

Some people have trouble viewing images at the PTO site. Here's a copy as a PDF: http://www.scribd.com/doc/53561493/Pat-5893120

This was generated by the excellent site pat2pdf.org, which I highly recommend for those who want convenient copies of patents.

kenjackson5• 15 years ago

The award is peanuts for Google. But establishes a scary precedent. Basically everyone had get ready to give this company effectively a license fee for past shipments of Linux-based products.

strlen4• 15 years ago

A patent for searching a linked list? This is disgusting.

As a middle finger, here's me infringing on it.

  typedef struct node {
    struct node *next;
    void *data;
  } node_t;
  
  void *find(node_t *head, void *what, int (*cmp)(void *, void *)) {
    while(*head != NULL && cmp(head->data, what) != 0) {
      head = head->next;
    }
    return head;
  }

Of course, there is an age old infringer on this patent:

  (define (find ll what)
          (if (or (null? ll) (eq? (car ll) what))
                  ll
                  (find (cdr ll) what)))

piotrSikora2• 15 years ago

You didn't read the patent, did you?

strlen4• 15 years ago

I did, the only part my code sample doesn't involve is expiring the oldest record, which is:

  void expire(node_t **head) {
    node_t *next = (*head)->next;
    free(*head);
    *head = next;
  }

In terms of using a linked list as an LRU cache, this is done in the Java SDK by LinkedHashMap:

http://download.oracle.com/javase/6/docs/api/java/util/Linke...

http://grepcode.com/file/repository.grepcode.com/java/root/j...

fragmede2• 15 years ago

The patent includes expiring the records in the linked list, and removing (some) expired records when doing the search:

  #define EXPIRE_LOOKUPS 500

  typedef struct node {
    struct node *next;
    void *data;
    int age;
  } node_t;

  void *find(node_t *head, void *what, int (*cmp)(void *, void *)) {
    while(*head != NULL && cmp(head->data, what) != 0) {
      if (head->next == NULL)
          return NULL;
      if (head->next->age > EXPIRE_LOOKUPS)
          head->next = head->next->next;
      ++head->age;
      head = head->next;
    }
    return head;
  }

(I didn't see the patent specify an actual expiry mechanism in any specific detail, so here's a useless, but patent-infringing one.)

jws3• 15 years ago

In the case where you expire the last entry of the linked list you will SEGFAULT. A test for head being NULL at the end of the loop would take care of that, but I'd put it in the condition of the while loop since it is probably free on a modern processor given the memory access pattern and it makes something sane happen when a client calls find(NULL,...).

I also don't think the last element ages, but since aging is unrelated to reality that is ok. On second thought, it protects you from the SEGFAULT because the last element can never expire. Very cunning of you.

strlen4• 15 years ago

On the other hand, I can see it makes interviewing a lot more difficult: "I would answer your question, but it would infringe on a patent".

apgwoz• 15 years ago

You mean, garbage collection?

strlen4• 15 years ago

s/*head != NULL/head != NULL/ (d'oh)

guelo• 15 years ago

What is the problem with that east Texas district?

tzs9• 15 years ago

Nothing. There's a common myth on the internet that it massively favors patent plaintiffs, but in reality it isn't even in the top five.

There are two reasons so many patent suits are filed there.

1. It has judges that have experience with patent suits and like handling them. Whether you are plaintiff or defendant, you want this.

2. There isn't much federal crime there. Criminal cases always take precedent over civil cases on the court calendar. In some districts, especially those where the stupid "war on drugs" is highly active, it can take a long long time to get any court time for civil cases.

leftnode2• 15 years ago

Basically a pissed off judge - http://www.technologyreview.com/communications/16280/page1/

Natsu4• 15 years ago

It's a rocket docket. So cases move through very quickly. And many of the rulings have been very patent-friendly. There aren't very many judges in that district, either, as I recall.

Now, you will find stats saying that patent holders don't win disproportionately often there. What those leave out is how many EDT cases settle beforehand. Basically, only the strongest cases even go to trial there and they still lose about half the time.

I can't remember if there's a rule requiring local counsel or not, but I know that several firms have set up shop in or near Marshall, Texas.

joeyh• 15 years ago

The title here on Hacker News has been mangled to be incomprehensible or just wrong. This is not a "Linux patent", it is a software patent which is potentially infringed by the Linux kernel.

alecco2• 15 years ago

Note it's the same person here and there.

jstedfast3• 15 years ago

unfortunately, it's not "potentially" it's "it does", the courts ruled in favor of it being an infringement.

alecco2• 15 years ago

Misleading title, dubious blog. This is an anti-Google/Android blogger with likely ties to Google competitors.

http://lwn.net/Articles/434587/

http://news.ycombinator.com/item?id=2428188

Natsu4• 15 years ago

I don't see what the author has to do with it. It links to the relevant patents & court files so you can read them yourself.

They just won a judgment against Google for using Linux. Granted, it was in East Texas, but that's where all the trolls file. This is exactly why software patents should not be allowed. I hope the patent gets invalidated soon.

sbov• 15 years ago

I hate reading patents because I always feel like they try to make it look as complicated as possible. In particular, I always find the inclusion of the computer architecture somewhat useless. Do we really care that there might be 25 software applications running on your computer? Is there any reason other than overcomplication (and thus making the patent appear more novel) to include this stuff?

Because of this, I just want to make sure I understand the patent properly:

From what I can tell, its a patent on a hash table that resolves collisions using chaining, implemented using linked lists. On top of this, each entry has an expiration time and it can remove them as it does lookups for entries.

kenjackson5• 15 years ago

In particular, I always find the inclusion of the computer architecture somewhat useless. Do we really care that there might be 25 software applications running on your computer?

I think the reason for this is that it moves the patent from an idea/algorithm to one that runs on a physically manifested device.

neilk• 15 years ago

In the USA, software patentability has always been dubious. But you can patent a complete physical setup that also runs software.

So software patents are usually written as if one had invented some special-purpose device, that just happens to consist of hardware that looks remarkably like a standard PC, running software.

jws3• 15 years ago

I'm not seeing which part of the Linux kernel is afflicted, but this exhibit from an Amazon case at least suggests that it is for the route cache.

http://docs.justia.com/cases/federal/district-courts/texas/t...

If so, it should be easy to excise from future kernels with minimal performance impact. (I was suspecting filesystem entry caches, but that doesn't show up when I google.)

In a perfect world the patent would not have been issued since it is obvious to anyone skilled in the art that considers when to purge expired entries from a hash table with linked list overflow, especially in a world where systems are constrained by memory access times more than computation. But we are not legislated by that world.

naner2• 15 years ago

So here we go again. Last time there was a highly voted fosspatents article here it was completely bogus. And everyone chimed in about how this guy had ulterior motives:

http://news.ycombinator.com/item?id=2355056

gregburek• 15 years ago

I think that Microsoft Corp. v. i4i Limited Partnership, which was argued before the Supreme Court on April 18, may change how this plays out in the end.

"Since 1983, the courts have followed a clear, firm rule: In order to overcome the statutory presumption that a patent is valid, a litigant must provide clear and convincing evidence that a patent is invalid. That's a high hurdle to overcome. ... Many observers expect the Supreme Court will reject the current bright-line rule and, at least under some circumstances, make it easier for parties to attack the validity of patents." - http://www.abajournal.com/magazine/article/court_may_make_it...

Previously on HN: http://news.ycombinator.com/item?id=2453895 and http://news.ycombinator.com/item?id=2464698

Texas jury finds Google infringes a patent: $5,000,000 damage award

Related Stories