5 ms·

Patent #7028023: Linked List

90 points by yen223 14y ago

dantillberg 14y ago
Isn't this basically what e.g. MySQL secondary indexes are?
RutZap 14y ago
This guy is amazing... he invented everything.. from air purifiers and supplementary bicycle handlebars, shoe tongue securing devices to linked lists (as early as 2002!!!) </sarcasm> Patent Troll!
- chris_wot 14y ago
  The only sorts of patents that should be granted are ones where you fire giant snowballs into the desert in order to irrigate it. http://worldwide.espacenet.com/publicationDetails/biblio?CC=GB&NR=1047735&KC=&locale=en_ep&FT=E http://worldwide.espacenet.com/publicationDetails/biblio?CC=...
verroq 14y ago
Previous discussion http://news.ycombinator.com/item?id=2873795 http://news.ycombinator.com/item?id=2873795
markokrajnc 14y ago
Java LinkedList: http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html http://docs.oracle.com/javase/6/docs/api/java/util/LinkedLis... Since J2SE 1.2 (December 8, 1998)
- tsahyt 14y ago
  I believe linked lists are much older than that though.
trebor 14y ago
I think we need to coin a new acronym: Yet Another Bogus Patent.
mhp 14y ago
I posted it on http://askpatents.com http://askpatents.com if you'd like to list prior art. http://patents.stackexchange.com/questions/738/prior-art-for-linked-list http://patents.stackexchange.com/questions/738/prior-art-for... Even an issued patent can still be invalidated. http://patents.stackexchange.com/questions/587/if-a-patent-has-been-issued-can-it-still-be-invalidated-by-prior-art http://patents.stackexchange.com/questions/587/if-a-patent-h...
- Jare 14y ago
  Multiple internal storage linked lists should be a prime example. I was using them on my 1995 racing game [1], where each car was contained in a global list of cars (for game logic and rendering), a list of cars for each sector of the track (for driving AI), and a list of cars for each map tile (for collisions). 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/things.h https://github.com/TheJare/SpeedHasteSrc/blob/master/game/th...
  - enduser 14y ago
    You would need to have been storing cdrs as well as cars for it to be considered valid prior art.
- amalcon 14y ago
  This is a bit more general than either a doubly-linked list or a skip list, but it seems a pretty straightforward extension of those ideas.
  - beerscout 14y ago
    Not only straightforward, but also not novel. For example such lists have been described (with source code) in this textbook (published in 1994): Taming C++: Pattern Classes and Persistence for Large Projects by Jiri Soukup. Here's a picture taken from this book illustrating the concept: http://community.moertel.com/~thor/blog/pix-20061201/soukup-multi-link-list-prior-art.png http://community.moertel.com/~thor/blog/pix-20061201/soukup-...
Tyr42 14y ago
Hey, if you have solid prior art, post it to patents.stackexchange.com Someone has already started: http://patents.stackexchange.com/questions/738/prior-art-for-linked-list-secondary-and-tertiary-traversal http://patents.stackexchange.com/questions/738/prior-art-for...
sturmeh 14y ago
This has been discussed before, it is not just a linked list. 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.
- vonmoltke 14y ago
  And, as presented in this patent, its a trivial enhancement on a conventional linked list. This is a patent for a data structure. There is no implementation there. Hell, there is no algorithm there. Its just someone who said, "Hey, I can put two forward pointers in each element of a linked list!" and wrapped a bunch of legalistic crap around it. This patent doesn't need prior art to be invalid.
  - dpark 14y ago
    > its a trivial enhancement on a conventional linked list. 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?
    - Evbn 14y ago
      In the patent-law sense, an implementation is a manifestation in hardware that performs some function.
      - dpark 14y ago
rxc178 14y ago
This guy has to have some massive balls to do this.
- manaskarekar 14y ago
  Why? He has nothing to lose. If it's rejected, it's rejected. But if it's accepted.. well you have something going now don't you? As long as there's a legal way you can exploit something, someone will do it.
chris_wot 14y ago
By the same author: "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." http://www.google.com/patents/US20120144069 http://www.google.com/patents/US20120144069
- Breakthrough 14y ago
  How do you get a patent regarding "A method includes addressing, through a command generated by an application [...] based on an appropriate communication link" to be issued? 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."
  - antidoh 14y ago
    "How do you get a patent ..." 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.
    - rayiner 14y ago
      Patent examiners actually take pride in their high rejection ratio.
      - antidoh 14y ago
        And yet the environment in which they work encourages more granted patents, as the new patent examination facilities being promoted by the administration imply (to me). Obama's/admin's stated reasons are to grant more patents faster.
joelthelion 14y ago
The examinators should probably be fired.
- crusso 14y ago
  Examiners and the filers should be exiled to Zimbabwe with one day of water and bread crumbs.
  - joelthelion 14y ago
    What makes you think there is no food in Zimbabwe?
brador 14y ago
Anyone know the cost of getting a patent like this?
- georgemcbay 14y ago
  It varies based on claims and size of the filing entity. There's a fee list here: http://www.uspto.gov/web/offices/ac/qs/ope/fee100512.htm 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.
Tipzntrix 14y ago
So this is a linked list that's ordered in two different ways? If I create a third pointer to reorganize the same data in a third way, can I patent that on top?
- gnat 14y ago
  Nope, Claim 2 is for a tertiary pointer as well. Your attempt to patent a triply-sequenced linked-list would be rejected as insufficiently innovative. Unlike the patent in question. cough
  - Tipzntrix 14y ago
    Damn, guess I have to step it up one more level and put a fourth pointer on there...
_phred 14y ago
Somewhat like a Skiplist, which is introduced in a 1990 paper: http://en.wikipedia.org/wiki/Skip_list http://en.wikipedia.org/wiki/Skip_list 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.
zerostar07 14y ago
So, unless it s open source software, how would they know who implements their patented list?
- usea 14y ago
  There are many companies who make a living by finding software patent infringement for their clients, sometimes through analyzing decompiled source code.
Fando 14y ago
Wow what a load.
Fando 14y ago
Wow what a load.
superqd 14y ago
I am stunned. Seriously, seriously stunned. 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 http://news.ycombinator.com/item?id=4153732 ...
seigel 14y ago
Awesome
mikehoward 14y ago
I believe that doublely linked lists are described by Knuth in the Art of Computer Programming volume (something). My recollection is that it may have been in a problem or note. They are definitely used in UNIX for the run queue where rapid traversal was necessary. I recall them from an internals course I took at UNIX expo back in the mid '80's. Additional pointers are trivially implied so I don't think that this patent should not stand. What a mess!
PatentTroll 14y ago
I am a strong supporter of the patent system, and in general an advocate for software patents. This, however, is a likely example of an error. We accept a certain error rate in any process, and if the USPTO is expected to be infallible, then fees would skyrocket and people would complain that patents cost a million dollars. Anyone who tried to enforce this patent would more likely than not have it invalidated in court or on re-exam. Apparently the assignee (LSI Logic, hardly a 'troll') has chosen not to enforce this patent on Google and Microsoft because it is so weak. So before we grab the pitch forks, remember that the "system" as a whole has worked here, even if the PTO let one through. The tech world has not come crumbling down, Google was not shut down, and everybody who has ever modified a linked list has not been sued out of oblivion. If you have a much better method, I'm genuinely interested to hear it.
- reader5000 14y ago
  It doesn't matter. The non-zero probability of having to defend against this turd patent is real. Maybe the "owner" of the patent is reasonable and decides not to enforce it, maybe not. Maybe they sell it later and it is enforced. There is still a nonzero cost to this patent. The greater problem is companies see the PTO is willing to let shit like this through and therefore patent everything in sight. The "system as a whole" failed utterly here.
  - zaroth 14y ago
    The closest solution for this is the SHIELD act. Write your elected officials and rally support!
kyrra 14y ago
I am a former employee of LSI, and I actually had a chance to participate in a meeting with one of the patent lawyers at the company. This patent was specifically talked about in that meeting. 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.
- marshray 14y ago
  In my opinion, it should be obvious to anyone skilled in the art that this patent should not have been issued and those who filed it and approved it have participated in a fraud against the US legal system.
  - kyrra 14y ago
    Sadly, that's not how the patent system is setup in the US. It rewards companies who try to file as many patents as possible and see if they can get those patents granted. It falls on the USPTO to validate and grant those patents. As the USPTO is underfunded and understaffed, a lot of possibly invalid patents are granted.
dlitz 14y ago
It's a troll patent. Is it owned by a patent troll?

90 points by yen223 14y ago

Isn't this basically what e.g. MySQL secondary indexes are?

This guy is amazing... he invented everything.. from air purifiers and supplementary bicycle handlebars, shoe tongue securing devices to linked lists (as early as 2002!!!) </sarcasm> Patent Troll!

chris_wot 14y ago
The only sorts of patents that should be granted are ones where you fire giant snowballs into the desert in order to irrigate it. http://worldwide.espacenet.com/publicationDetails/biblio?CC=GB&NR=1047735&KC=&locale=en_ep&FT=E http://worldwide.espacenet.com/publicationDetails/biblio?CC=...

verroq 14y ago

Previous discussion http://news.ycombinator.com/item?id=2873795 http://news.ycombinator.com/item?id=2873795

markokrajnc 14y ago

Java LinkedList: http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html http://docs.oracle.com/javase/6/docs/api/java/util/LinkedLis... Since J2SE 1.2 (December 8, 1998)

tsahyt 14y ago
I believe linked lists are much older than that though.

trebor 14y ago

I think we need to coin a new acronym: Yet Another Bogus Patent.

mhp 14y ago

I posted it on http://askpatents.com http://askpatents.com if you'd like to list prior art. http://patents.stackexchange.com/questions/738/prior-art-for-linked-list http://patents.stackexchange.com/questions/738/prior-art-for... Even an issued patent can still be invalidated. http://patents.stackexchange.com/questions/587/if-a-patent-has-been-issued-can-it-still-be-invalidated-by-prior-art http://patents.stackexchange.com/questions/587/if-a-patent-h...

Jare 14y ago
Multiple internal storage linked lists should be a prime example. I was using them on my 1995 racing game [1], where each car was contained in a global list of cars (for game logic and rendering), a list of cars for each sector of the track (for driving AI), and a list of cars for each map tile (for collisions). 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/things.h https://github.com/TheJare/SpeedHasteSrc/blob/master/game/th...
- enduser 14y ago
  You would need to have been storing cdrs as well as cars for it to be considered valid prior art.
amalcon 14y ago
This is a bit more general than either a doubly-linked list or a skip list, but it seems a pretty straightforward extension of those ideas.
- beerscout 14y ago
  Not only straightforward, but also not novel. For example such lists have been described (with source code) in this textbook (published in 1994): Taming C++: Pattern Classes and Persistence for Large Projects by Jiri Soukup. Here's a picture taken from this book illustrating the concept: http://community.moertel.com/~thor/blog/pix-20061201/soukup-multi-link-list-prior-art.png http://community.moertel.com/~thor/blog/pix-20061201/soukup-...

Tyr42 14y ago

Hey, if you have solid prior art, post it to patents.stackexchange.com Someone has already started: http://patents.stackexchange.com/questions/738/prior-art-for-linked-list-secondary-and-tertiary-traversal http://patents.stackexchange.com/questions/738/prior-art-for...

sturmeh 14y ago

This has been discussed before, it is not just a linked list. 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.

vonmoltke 14y ago
And, as presented in this patent, its a trivial enhancement on a conventional linked list. This is a patent for a data structure. There is no implementation there. Hell, there is no algorithm there. Its just someone who said, "Hey, I can put two forward pointers in each element of a linked list!" and wrapped a bunch of legalistic crap around it. This patent doesn't need prior art to be invalid.
- dpark 14y ago
  > its a trivial enhancement on a conventional linked list. 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?
  - Evbn 14y ago
    In the patent-law sense, an implementation is a manifestation in hardware that performs some function.
    - dpark 14y ago

rxc178 14y ago

This guy has to have some massive balls to do this.

manaskarekar 14y ago
Why? He has nothing to lose. If it's rejected, it's rejected. But if it's accepted.. well you have something going now don't you? As long as there's a legal way you can exploit something, someone will do it.

chris_wot 14y ago

By the same author: "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." http://www.google.com/patents/US20120144069 http://www.google.com/patents/US20120144069

Breakthrough 14y ago
How do you get a patent regarding "A method includes addressing, through a command generated by an application [...] based on an appropriate communication link" to be issued? 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."
- antidoh 14y ago
  "How do you get a patent ..." 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.
  - rayiner 14y ago
    Patent examiners actually take pride in their high rejection ratio.
    - antidoh 14y ago
      And yet the environment in which they work encourages more granted patents, as the new patent examination facilities being promoted by the administration imply (to me). Obama's/admin's stated reasons are to grant more patents faster.

joelthelion 14y ago

The examinators should probably be fired.

crusso 14y ago
Examiners and the filers should be exiled to Zimbabwe with one day of water and bread crumbs.
- joelthelion 14y ago
  What makes you think there is no food in Zimbabwe?

brador 14y ago

Anyone know the cost of getting a patent like this?

georgemcbay 14y ago
It varies based on claims and size of the filing entity. There's a fee list here: http://www.uspto.gov/web/offices/ac/qs/ope/fee100512.htm 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.

Tipzntrix 14y ago

So this is a linked list that's ordered in two different ways? If I create a third pointer to reorganize the same data in a third way, can I patent that on top?

gnat 14y ago
Nope, Claim 2 is for a tertiary pointer as well. Your attempt to patent a triply-sequenced linked-list would be rejected as insufficiently innovative. Unlike the patent in question. cough
- Tipzntrix 14y ago
  Damn, guess I have to step it up one more level and put a fourth pointer on there...

_phred 14y ago

Somewhat like a Skiplist, which is introduced in a 1990 paper: http://en.wikipedia.org/wiki/Skip_list http://en.wikipedia.org/wiki/Skip_list 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.

zerostar07 14y ago

So, unless it s open source software, how would they know who implements their patented list?

usea 14y ago
There are many companies who make a living by finding software patent infringement for their clients, sometimes through analyzing decompiled source code.

Fando 14y ago

Wow what a load.

Fando 14y ago

Wow what a load.

superqd 14y ago

I am stunned. Seriously, seriously stunned. 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 http://news.ycombinator.com/item?id=4153732 ...

seigel 14y ago

Awesome

mikehoward 14y ago

I believe that doublely linked lists are described by Knuth in the Art of Computer Programming volume (something). My recollection is that it may have been in a problem or note. They are definitely used in UNIX for the run queue where rapid traversal was necessary. I recall them from an internals course I took at UNIX expo back in the mid '80's. Additional pointers are trivially implied so I don't think that this patent should not stand. What a mess!

PatentTroll 14y ago

I am a strong supporter of the patent system, and in general an advocate for software patents. This, however, is a likely example of an error. We accept a certain error rate in any process, and if the USPTO is expected to be infallible, then fees would skyrocket and people would complain that patents cost a million dollars. Anyone who tried to enforce this patent would more likely than not have it invalidated in court or on re-exam. Apparently the assignee (LSI Logic, hardly a 'troll') has chosen not to enforce this patent on Google and Microsoft because it is so weak. So before we grab the pitch forks, remember that the "system" as a whole has worked here, even if the PTO let one through. The tech world has not come crumbling down, Google was not shut down, and everybody who has ever modified a linked list has not been sued out of oblivion. If you have a much better method, I'm genuinely interested to hear it.

reader5000 14y ago
It doesn't matter. The non-zero probability of having to defend against this turd patent is real. Maybe the "owner" of the patent is reasonable and decides not to enforce it, maybe not. Maybe they sell it later and it is enforced. There is still a nonzero cost to this patent. The greater problem is companies see the PTO is willing to let shit like this through and therefore patent everything in sight. The "system as a whole" failed utterly here.
- zaroth 14y ago
  The closest solution for this is the SHIELD act. Write your elected officials and rally support!

kyrra 14y ago

I am a former employee of LSI, and I actually had a chance to participate in a meeting with one of the patent lawyers at the company. This patent was specifically talked about in that meeting. 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.

marshray 14y ago
In my opinion, it should be obvious to anyone skilled in the art that this patent should not have been issued and those who filed it and approved it have participated in a fraud against the US legal system.
- kyrra 14y ago
  Sadly, that's not how the patent system is setup in the US. It rewards companies who try to file as many patents as possible and see if they can get those patents granted. It falls on the USPTO to validate and grant those patents. As the USPTO is underfunded and understaffed, a lot of possibly invalid patents are granted.

dlitz 14y ago

It's a troll patent. Is it owned by a patent troll?