Patent #7028023: Linked List
google.com
google.com
It is a list which has elements that not only point to the next element, but the element after it, and so on. (As to provide a recovery method if one element is to be destroyed, or to ease implementation for removal etc.
However that's still fringing on patent trolls.
Indeed it is. The patent should not have been granted, and from previous discussions about this, there is ample evidence of prior art.
However, exaggerating this patent by claiming it is a "linked list" patent diminishes the conversation around patents. It doesn't make patents sound worse. It makes those who are anti-patent seem disingenuous. This patent is bad enough on its own merits without implying that someone was granted a patent for the linked list concept as a whole. If Subaru were issued a patent for a new method of fuel injection, would it be appropriate to claim that they were issued a patent for the internal combustion engine?
> This is a patent for a data structure. There is no implementation there.
What is a data structure if not an implementation?
The patent is a cartoon of a half-baked idea. It does not even describe how to implement element addition or removal. (Unless the caller maintains some special structure, many O(1) list operations become O(N). Removal is delicate because you need all incoming pointers.). It's unclear whether the "inventor" ever implemented the data structure.
Second, the patent describes an implementation that allows multiple traversals. That it doesn't cover addition or removal seems irrelevant. The patent is for the structure that allows the traversals. You could build up the structure in a number of ways, but the end result would be the same.
If you gloss over construction and modification details, this "invention" is entirely covered by "Fortran-style" linked lists which have been in common use since the 1950s. (Store the primary list in an array, then have one or more integer arrays containing the index of the next node. Relative to storing the "aux_next" pointer inside the node, this allows dynamically creating and destroying an arbitrary number of indices.)
This invention is obvious and trivial and there seems to be lots of prior art. I'm not sure why you still seem to think I'm defending it. Regardless, describing how these lists should be constructed would not make this any less trivial or obvious.
The title of the patent is "Linked List". How is that an exaggeration?
> If Subaru were issued a patent for a new method of fuel injection, would it be appropriate to claim that they were issued a patent for the internal combustion engine?
I think you misunderstand my point. I did not claim that this person patented linked lists. I claimed this person patented a trivial enhancement to a conventional linked list, and did not provide any implementation detail (which is really what makes it trivial).
On the subject of implementation, I do not see a data structure description as an implementation, any more than I see an algorithm as an implementation. Being an electrical engineer I am biased towards thinking of implementation as an actual, functional system (not necessarily hardware). I know there are many patents where this definition of implementation doesn't hold, but that is why I am uncomfortable with software and business method patents in general, and think chemical and drug patents should be a special category.
So it's a poorly titled patent. All that tells me is that the inventor was too unoriginal to even come up with a better name. If he'd titled it "the wheel", would it be accurate to claim that a patent was granted on the wheel?
>I think you misunderstand my point. I did not claim that this person patented linked lists. I claimed this person patented a trivial enhancement to a conventional linked list, and did not provide any implementation detail (which is really what makes it trivial).
I actually think you misunderstand my point. I agree that this is trivial and obvious. However, that doesn't justify exaggerating the actual claims ("linked list patented!"). People who are already dead-set against software patents might enjoy this, but they're just being self-congratulatory, and there's no real point.
People who are in favor of software patents or on the fence will instead recognize the exaggeration and dismiss the argument as disengenuous. Worse, they may take this as evidence that the anti-software-patent movement has no real basis, because the movement demonstrates that it has to exaggerate in order to even make its point.
People are lazy, news at 7.
> If he'd titled it "the wheel", would it be accurate to claim that a patent was granted on the wheel?
No, because the scope of the patent is based entirely on the claims. Nothing else has legal significance.
Now you are being disingenuous. The title has no legal significance. The only thing that has legal significance is the list of claims, and the are to be read as a conjunction (A & B & C...)
At no point in his comments do I see him say "A linked list has been patented" or something similar.
Even an issued patent can still be invalidated. http://patents.stackexchange.com/questions/587/if-a-patent-h...
Not sure if this is formally valid prior art, as each list a car is part of can be considered different lists (i.e. different set of members), not different sequences on the same set.
Frankly, I'd rather see this abomination be dismissed on the grounds of being obvious.
[1] https://github.com/TheJare/SpeedHasteSrc/blob/master/game/th...
I've complained about patents once before, and I think this sort of patent is a perfect example of something that wouldn't be worth a single day of patent protection. It's a colossal over-payment. Does it really make sense for our society to "pay" 20 years of protection for an idea that is so trivial to most of the practitioners in the art?
It's like a street magician selling the secret to their cup and ball routine for $100,000. It's not a mystery, and it isn't worth the price. But for some reason, the USPTO reasons, "well, I haven't seen your cup and ball routine before, so here's the check." They have far too low a standard, and we are paying far too high a price for the vast majority of patents. We can't keep doling out decades of protection for such common-place "inventions".
http://news.ycombinator.com/item?id=4153732
...
Patent Troll!
http://worldwide.espacenet.com/publicationDetails/biblio?CC=...
I'm certain that at least one older algorithms text I own mentions skiplists, and there is no doubt much other prior art here, seems like the kind of thing that might find its way into kernel scheduling queues.
"A method includes addressing, through a command generated by an application executing on a computing platform, one or more device(s) in storage communication with the computing platform based on an appropriate communication link. The method also includes accessing, based on the addressing, a physical register of the one or more device(s) through an appropriate interface therein. Further, the method includes obtaining statistical information associated with a performance of the one or more device(s) at the computing platform through the access of the physical register."
All I read was "This patent regards using a software-controlled computer to communicate with another computer in an arbitrary manner which can allow for data statistics and performance tracking. Oh, wait, that's not specific... Hmm... Oh wait! Yes, and you have to get the data from a register."
The only way I can make sense of these ridiculous patents is if the patent examiners are under pressure to grant patents as part of their yearly performance metrics.
Someone has already started:
http://patents.stackexchange.com/questions/738/prior-art-for...
Since J2SE 1.2 (December 8, 1998)
Additional pointers are trivially implied so I don't think that this patent should not stand.
What a mess!
As long as there's a legal way you can exploit something, someone will do it.
1) LSI is not a patent troll. They generate a small portion of their revenue through patents, but most of that is through its purchase of Agere (cell phone tech patents).
2) The patent in-question is near impossible to prove that it is being used by anyone unless the code is available to look at. And even then would require going over their code to find the issue. Most lawyers don't want to put in that much work to find a violation, they would rather have more broad patents to litigate or monazite with.
3) As there is a good chance that there is prior art to this patent, it probably won't be used by LSI. Worst-case is LSI hits financial troubles and sells the patent to a troll that tries to use it.
As the USPTO is underfunded and understaffed, a lot of possibly invalid patents are granted.
http://www.uspto.gov/web/offices/ac/qs/ope/fee100512.htm
Of course those are just the filing fees, most filers will file using patent attorneys which bring the ~$500-ish dollar cost up to $5k-10k per application.