If you want to explain this to a nontechnical person…
Let's say Aunt Marge clips coupons. She clips a lot of coupons, so she keeps them in one of those index files with a slot for each letter of the alphabet, by product name. When she goes looking for a coupon, say for coca cola, she goes to the "C" slot and flips through the slot looking for a coca-cola coupon. If while flipping through she pitches out expired coupons then she has infringed this patent. (if she does it "with a computer")
Edit: This is just claim #1, there are more variations claimed.
For the average layperson, you are correct and I'll probably use this analogy myself in conversation. Legally, however, your analogy doesn't hold water. Yes, it's an analogy and many times they aren't 100% analogous, but I feel it's worth pointing out the legalistic differences.
And here's the reason: Aunt Marge isn't using a linked list. That is, each coupon doesn't point to the next coupon in the list. It's simply a collection (or array) of coupons.
Now, let's bring this back to a point that's somewhat more relevant. If you did implement something more analogous to Aunt Marge's coupon collection (say an array), and trimmed out items as the code noticed they were expired, would you infringe this patent? Maybe not. I haven't tried reading the details of the patent, but if the article is correct and if, as in every other case, every detail of the patent matters, then I'd wager your array-with-expiring-items would not infringe.
And that is what's wrong with software patents. Maybe we've been expiring items from collections, dictionaries and arrays for a long time. But suddenly, apply it to a linked list and you've infringed the patent. Nonsense.
A linked list of course has no direct analogy in the physical world, but I think the analogy has a workable definition of "next(couponX)" which is "put your finger on the back of couponX, move your finger away from yourself, if you touch the face of another coupon, that is the next coupon".
The slot is not an array, it is not directly accessible by index number or key. It is close to a doubly linked list with a head and tail pointer, but it has more operations than a linked list though. You can flip through by "a bunch" and easily start at a randomish middle point which doesn't map back to linked lists, but also isn't important for this example.
"A linked list of course has no direct analogy in the physical world"
First few that come to mind: conga line, necklace, bike chain and DNA. Tangentially, lines of people forming a queue or a push down stack of dishes or the number you pick at the deli counter for your turn forming a circular buffer. All of these are examples of physical world linked lists.
I like these. You can embody the "link" nature, but the physical analogies also gain operations that make them not match linked list[1], such as:
• The examples all seem to include back links as well.
• Most of them you can access an interior element in constant time.
• Most of them you can get a size estimate without traversing.
• The dishes are more stack like. Traversal is destructive, but it doesn't add operations. (I think)
• The deli numbers give you a constant time "distance between" operator (unless the deli has lost a lot of the tags), and require a global method dispatch to find "next". 37? 37?… 38?
[1] Somewhere in the '80s, Dr. Roman[2] was explaining binary search to a class of 'us' and started to use a phone book analogy, until he realized that people have more information than just alphabetic letter position to work with, they have an idea about frequency in names as well. That's stuck with me as a caution of the difficulty of analogy.
[2] Oh look, he is department chair now. Well done! (Warning to students: if you are having trouble in CSE425S (formerly CS 455) with the programming-language-of-the-week being prolog, and you figure out how to build yourself variables, he will see through you and give you a bad grade, my poor little grid bugs.)
Then you get uniform distribution problems. If I know the first few digits are 980 I can make a leap well to the back of the book. It really does become an interesting problem.
You can force it by not letting the person see the key, only the results of the comparison, but that is a little silly.
Maybe some of the mismatch comes from the human heuristic being so much faster than the physical turnpage-readname-compare operation. In a computer the compares are so fast that there isn't really a point to building a heuristic to optimize away the first few.
If the comparison finding were slow on a computer you would not use binary search, so in a sense you are forcing the human to use the wrong algorithm.
What you're describing is an interpolated binary search (where you don't divide in two, you pick a point based on a guesstimate of where the key will lie).
It turns out that interpolated binary searches are useful in computers, in cases where the structure being searched has a significant overhead for each read - for example, seeking in variable-bitrate-encoded video streams is such an application.
Its an old one but filing cabinet document index sheets would be a linked list. Those were lists of the contents in a cabinet/drawer, some of which were lists not in the order of the contents, but in an alternate order for finding documents.
I'd think of it more like, if you kept all the coupons in numbered cubbyholes, and each coupon had a post it note with the location of the cubbyhole where the next ordered coupon was.
Project A contains a generic collection. Project B contains an abstraction of objects with expiry times. Project C instantiates A's collection for B's objects.
Now assuming A implements the collection using linked lists and C uses A and B as black box, linked libraries, does anyone infringe on the patent?
No, because the key point of this patent appears to be removing expired objects as a side-effect of searching the linked list for an unrelated object.
So unless Project A's generic collection implements an optional callback that is called on every object seen while searching the collection, project C uses that callback to delete expired objects, you'd seem to be in the clear.
> If you want to explain this to a nontechnical person…
It would be interesting to get the materials from the trial and see how both sides explained the patent to the judge and the jury. During pretrial both sides will have made a technology presentation to the judge to explain their take on the background of the patent and what it does, and then during the trial both sides will try to explain to the jury what the patent means.
Some of these presentations can be very good content-wise and very well produced and presented.
The implications of this might be much larger than most people realize, because of the GPL patent landmine, GPLv2 Section 7:
> 7. If, as a consequence of a court judgment or allegation of patent infringement or for any other reason (not limited to patent issues), conditions are imposed on you (whether by court order, agreement or otherwise) that contradict the conditions of this License, they do not excuse you from the conditions of this License. If you cannot distribute so as to satisfy simultaneously your obligations under this License and any other pertinent obligations, then as a consequence you may not distribute the Program at all. For example, if a patent license would not permit royalty-free redistribution of the Program by all those who receive copies directly or indirectly through you, then the only way you could satisfy both it and this License would be to refrain entirely from distribution of the Program.
Fortunately, only the copyright holders (i.e. the people who have contributed code to Linux) could sue for GPL licence violation, so we can hope it's not in the interest of the Linux developers to stop all distribution of Linux...
I followed the link to the patent, and just want to make sure I understand things correctly. I'm not very knowledgeable about legal jargon, or formal CS terminology.
>> Performing storage and retrieval that uses the hashing technique with the external chaining method for collision resolution.
Isnt this just describing a hash table?
>> In order to prevent performance deterioration due to the presence of automatically expiring data items, a garbage collection technique is used that removes all expired records stored in the system in the external chain targeted by a probe into the data storage system.
So the software doesn't run slowly, we're going to do something special to get rid of those pesky expired records.
I believe, "removes all expired records stored in the system in the external chain targeted by a probe into the data storage system." is just preparing you for the description of what they're going to do, without actually saying anything.
>> Each insertion, retrieval, or deletion of a record is an occasion to search an entire linked-list chain of records for expired items and then remove them.
Whenever an action is taken on a record, remove expired records near the record targeted by the action.
>> Because an expired data item will not remain in the system long term if the system is frequently probed, it is useful for large information storage systems that are heavily used, require the fast access provided by hashing, and cannot be taken off-line for removal of expired data.
Expired items don't stay long. System doesn't have to be taken offline to remove expired items... Because they remove expired items after CRUD of a record takes place, I guess.
Surely I'm missing something here. Or is it just that silly that you can get a patent on something like this?
That's the gist of it. It should point out how fucked up the patent system in the US is. Also, it was originally patented in 1992, and it's just now being legislated with.
What I imagine happened is some programmers at a now defunct company wanted to get their names on a patent because it's cool. They come up with the most generic algorithm ever, easily get it patented, and then they get to brag to their drinking buddies.
Then, the company they work for goes out of business/gets bought and the patent is transferred to a patent troll like this Bedrock company who then try to find where it 'infringes'.
That's all my imagination, but similar things have happened.
What I just learned with this article is the Bedrock company is no longer active...how can you win a case when you're not even an active company anymore!?
Note: I don't have a tremendous amount of sympathy for any large company like Google, Oracle, Apple, Amazon, etc. who get sued for silly patent 'infringements' because they would do the same in a heartbeat. ALL software patents should be abolished.
> I don't have a tremendous amount of sympathy for any large company like Google, Oracle, Apple, Amazon, etc. who get sued for silly patent 'infringements' because they would do the same in a heartbeat. ALL software patents should be abolished.
Apple is only 5 characters? Amazon doesn't end in "le"?
Oracle is the only one in the second half of the alphabet? Google is the only one whose name isn't also a thing? Apple is the only edible thing? Apple only has two vowels the others have three? Apple doesn't have an "o"?
20 years. It looks to me like this one was actually filed on 2 Jan 1997 and granted on 6 Apr 1999. [1]. I think the 1992 date came from on of the patents used as a reference in the application.
I flipped through and there doesn't seam to be anything about weak hash tables, but that's not surprising seeing as TAOCP is written around an assembly language, while weak hash tables make most sense in a GCed environment.
If they referenced it and the patent was still granted, that's bad. It means that the USPTO still considered the patent to be "novel" in spite of all the information found in TAOCP.
I put "novel" in quotes because the courts seem to use a hair-splitting definition of it. I honestly think that, when faced with a pile of Lego blocks, there are patent lawyers who could argue that it's non-obvious that one could combine them.
You have to read the claims if you want to know what the patent covers. Everything else is just background information and helps in understanding what the claims mean.
I really dislike that these matters are often initially decided by a random jury. Nearly everything related to software is non-obvious to a layperson, so how are they supposed to rule on patentability, and subtle infringements? I don't have a better answer, since narrower pools of jurors would have certain biases, but I feel this is a huge problem.
I have this (most likely irrational) fear that one day I'll be on trial related to some work I've done, and my fate will be decided by 12 average people, who are decidedly not my peers, and don't have the background (or capacity even) to understand the relevant concepts of the case.
"Implications for Android: Concerning Android, I wouldn't rule out that maybe some of the hundreds of thousands of Android applications out there use the teachings of the infringed patent claims in one way or another."
Wow, developer FUD much? Let me propose a small fix for you Florian:
"...I wouldn't rule out that maybe some of the millions of software applications written since this patent was filed use the teachings of the infringed patent claims in one way or another."
Why single out Android on this? oh wait, I forgot, because it's Florian...
There are definitely some things missing from his analysis, but at least he links to the appropriate court documents so you can ignore his analysis and do your own if you're so inclined.
The real questions are things like what version of Linux infringed? Has that code been removed yet? I have to think it would be removed the minute people found out. Was the infringing code part of the main kernel, or something else? I seem to recall a mention of RHEL, so maybe it's specific to that.
That said, it's a real danger. Even if the patented code is removed, they can (and will) go after people for past damages. They're a patent troll, that's what they do. And you can expect all future cases to be filed in East Texas. There's also no more escape clause, because they'll just sue batches of people who are distributed all over the country or world and claim that East Texas is just as good a place as any because no forum would be more convenient.
The best fix for this is to get the law changed to eliminate software patents entirely. Maybe, just maybe, i4i will help with that, but I'm not sure. Reexamination requests are also in order. Hopefully this patent will get busted soon
Ultimately, this is just another reminder of why software patents are a bad thing.
Perhaps you are unaware that Google makes Android, or that Android uses a Linux kernel?
This makes Android the most likely target among Linux-based phones and tablets for the patent owners to go after next, since they have already established (until/unless Google can get it overturned on appeal) that their patent is valid against Google. They can try to leverage off that and bring in Android as just more instances of the same overall infringement.
What Florian seems to be insinuating is that Android application developers would be somehow at risk in some way from this ruling due to them having written programs that "use the teachings of the infringed patent claims in one way or another". What is that even supposed to mean?
If I write code to target a platform whose implementation infringes a patent somewhere deep 'beneath the hood' I am not liable to pay any damages for that, I did not ship infringing code and my code is agnostic to whether the platform infringes or not.
I cannot see the need (besides FUD) for Florian to have written that. He mixes cherry picked facts and analysis with wild speculation (commonly involving Android's 'bleak future') and hopes that people won't see the difference.
Edit:
As another example, see how he conveniently forgot to mention the factor of the finding coming from an East Texas court when he extrapolates from this verdict to all Android related patent suits.
case class Elem(key: K, var value: V, var expires: Long)
private val BUCKETS = 10
private val store = new Array[LinkedList[Elem]](BUCKETS)
for(i <- 0 until BUCKETS) store(i) = new LinkedList[Elem]
def put(key: K, value: V, expires: Long): Unit = {
val b = bucket(key)
store(b).find(_.key == key) match {
case Some(x) => {
x.value = value
x.expires = expires
}
case None => {
store(b) = new LinkedList(Elem(key, value, expires), store(b))
}
}
}
def get(key: K): Option[V] = {
val now = System.currentTimeMillis
var result: Option[V] = None
// BUG: This doesn't handle the first element in the list being expired
var prev: LinkedList[Elem] = null
var i = store(bucket(key))
while (i.next != i) {
if (i.elem.expires < now) {
prev.next = i.next
} else if (i.elem.key == key) {
result = Some(i.elem.value)
}
prev = i
i = i.next
}
result
}
private def bucket(key: K) = key.hashCode % BUCKETS
}
Ya, there's a bug. Too busy ATM to think about the clean way to fix it.
The linked list is crucial to the patent, as the "external chaining" way of avoiding collisions when hashing. Another way is "linear probing" (and Knuth is cited) but there's already a similar patent for that.
It's a good idea (incremental garbage collection of expired records with each lookup, instead of batching it), but obvious. Good enough to be in a textbook, but only worth maybe one line.
There might be some cleverness in the specifics of integrating it into the internals of maintaining the hashtable, but I haven't read the detailed description to check.
( http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sec...
The idea is in three short paragraphs at "BRIEF SUMMARY OF THE INVENTION", and the problem is at "BACKGROUND OF THE INVENTION". The part I haven't read is "DETAILED DESCRIPTION OF THE INVENTION".
I wish the specific details were given of the reasons for why this parent was held valid, how exactly linux was found to infringe.
Since this was a District Court decision, the appeal would go to the Court of Appeals for the Federal Circuit, which keeps statistics on reversal rates on its web site. Last I looked, the reversal rate was somewhere between 18-30%. I.e., the odds are stacked against reversal on appeal.
And you do need something specific to appeal. You can't simply say, "We lost, we'd like to appeal". Pretty much the only appeals that take that form are death penalty cases, which typically have automatic appeals.
From the summary it would look like an utterly stupid technique with O(n) retrieval cost. However, I suspect the linked list they refer to are linked lists off each hash bucket, which in the case of collision have to be searched anyway so purging stale data is virtually free. It doesn't cost that much to search the entire list rather than just up to the match because most hash tables are designed to keep these lists short enough to support the "constant time access" performance claim. That's clever enough if you don't mind that some stale data might not be purged for a long time because its bucket not hit. However, it's also the sort of thing that any experienced programmer might cook up with a half-hour's thought. Which is the basic reason software patents are inherently anticompetitive: to a patent office, there's no such thing as an obvious idea. Partly because none of this is obvious to lawyers, and partly because the patent system was designed for chemical formulas and paper clips in an industrial age where if an idea wasn't already patented it must be patentable.
This would be a really good time to dig up prior art. If anyone knows of a published description of an algorithm that describes all the elements of a claim and there's proof that it was published before, I think, 1997, I'm sure there are a lot of people who would be interested.
I don't understand -- why didn't Google just acquire the company / patent? Would the cost be far overshadowed by the risk of losing the suit... and then they'd have another patent arrow in their quiver?
I assume they wanted to beat the suit to discourage patent trolls from going after Linux and Android in the future. That plan backfired. I'm guessing it backfired due to the jurisdiction...Google's team may have underestimated the ignorance of the court and overestimated their ability to educate.
This particular suit is a tiny chink in a big dam. But, enough of these little patent trolls, as well as a few heavy hitters like Oracle, going after Google could cause them (and other Linux distributors, as well) significant pain. Fighting every patent claim is the only sensible choice. If patent trolls know Google never rolls over, and they're going to have to litigate every single time (and lose a lot of the time), they may be more hesitant to go after Google, and may instead choose more compliant targets.
If I were in Google's shoes, I'd do the same thing.
It may be that acquisition would now be a reasonable response, though the price of the company just went way up because of this win...unfortunately, now their patent troll business model has been validated.
The problem with some stirrers of this article is that the forgot the legal definition of infringement...remember Google's claim that as one entity of an open source project that they are not a party to any infringement claims?
Careful of what you read as some of this seems to have the MS tinge of Linux infringes..
Let's say Aunt Marge clips coupons. She clips a lot of coupons, so she keeps them in one of those index files with a slot for each letter of the alphabet, by product name. When she goes looking for a coupon, say for coca cola, she goes to the "C" slot and flips through the slot looking for a coca-cola coupon. If while flipping through she pitches out expired coupons then she has infringed this patent. (if she does it "with a computer")
Edit: This is just claim #1, there are more variations claimed.