9 ms·
Someone patented linked lists
- fleitz 15y agoThat actually sounds more like a skip list than a linked list.
- lanstein 15y agoPatent application
- cleverjake 15y agothat was issued. http://www.google.com/patents/about?id=Szh4AAAAEBAJ http://www.google.com/patents/about?id=Szh4AAAAEBAJ
- deleted 15y ago[deleted]
- deleted 15y ago[deleted]
- dpark 15y agoApplication number: 10/260,471 Publication number: US 2004/0064448 A1 Filing date: Sep 26, 2002 Issued patent: US7028023 (Issue date Apr 11, 2006)
- lanstein 15y agoSorry, wrong tab. Other submission was a link to the application. Any any rate, I'm wrong.
- dpark 15y agoThis is not a patent on the linked list. It's a patent on a modification of the linked list that provides a secondary (and possibly tertiary, etc.) traversal path. The patent should not have been granted, and should be deemed invalid if it ever goes to court, but it is not a patent on just the linked list. The anti-patent crowd makes themselves look bad by trotting out examples like this and being deceptive about the actual content of the patent.
- phoyd 15y agoThis modification looks like "Skip List" and according to Wikipedia http://en.wikipedia.org/wiki/Skip_list http://en.wikipedia.org/wiki/Skip_list is was first described in 1990.
- dpark 15y agoThis is not a skip list, not at all. The skip list is a probabilistic data structure that gives expected access times comparable to a BBST. The patent covers a linked list with an extra set of links that provide a different traversal.
- colomon 15y agoOne example of which would be a doubly linked list, which (according to Wikipedia) goes back at least to IBM's TSS/360 operating system (1967), and was discussed in The Art of Computer Programming volume 1, published in 1968.
- dpark 15y agoA doubly-linked list generally refers to a bidirectional linked list, where the pointers are next and prev. This type of list allows traversal in both directions, but it's still essentially a single traversal. Multiply-linked lists provide next1, next2, etc. pointers for multiple unrelated traversals, each in a single direction (unless we assume a "multiply-doubly-linked list"). Arguably we could consider a doubly-linked list to be a special case of the multiply-linked list, but it would be a poor choice, as certain key operations (such as insertion) are more expensive with a multiply-linked list.
- nitrogen 15y agoThis multiply-linked list just seems to be a special case of an item being in multiple separate lists. In this case, the separate lists also happen to contain all the same items as the first list. Further, these are all special cases of the directed graph. Regarding the overall conversation, it looks like everyone is arguing over whether "linked list" should be interpreted inclusively to contain all list-like linked data structures, or exclusively to refer strictly to those data structures referred to by the "linked list" moniker in traditional CS textbooks. There is also the issue of whether "linked list" has an informal, conversational meaning among a subset of programmers that differs from its formal definition (I believe this thread demonstrates that it does), and whether it should have such separate meanings. It is my opinion that neither of these arguments is helpful to the anti-bad-patent/anti-software-patent cause, and it seems that excessive infighting over apparently trivial concerns is a credibility-destryoing hallmark of the stereotypical geek. After all, if you were a politician, would you continue to listen to a presentation in which the presenters started arguing with each other over whether the background color of the slides was more appropriately described as purple or fuchsia (Is fuchsia a subset of purple, or are they separate entirely? Sounds familiar...)? As an aside, sometimes I wish I could draw a circle around an entire thread and say, "I'm responding to this whole blob," with the page layout updated accordingly ;).
- lightblade 15y agoI'm surprised that this patent was granted.
- alecbenzer 15y agoWhat exactly does a patent office do to determine if something is actually original or not? Like did some clerk look at this and say "Yeah, I'm no computer scientist, but this sounds original to me"?
- CamperBob 15y agoMore or less nothing. They rely on the applicant to disclose any prior art. Disagreements about patentability are a matter for the courts, in the USPTO's view. The only solution is to defund them and shut them down.
- ars 15y agoA: That is not true. Which I know first hand, since I worked with someone who was in a very long dispute with the patent office on the patentability of something. B: That is the only solution? You can not think of any other possible solution?
- CamperBob 15y agoSo how does something like this patent on multiply-linked lists happen, if the USPTO does even the most cursory prior art search on its own? The rules say one thing, the reality says another. That is the only solution? You can not think of any other possible solution? Law is the code we live by. You don't fix code this broken. You rewrite it.
- ars 15y agoAs Daniel_Newby said: "the patent office checks if the patent is substantially similar to previous patents". They do a check, and a thorough one, just not in the same places you do. Remember that they are not programmers. > Law is the code we live by. You don't fix code this broken. You rewrite it. Oh please. A simple solution would be requiring them to hire an expert in each field to double check patents. This would cost too much which is why they don't. But it's a simple solution. PS. In the real world no one rewrites broken code once it gets used a lot. You fix the broken parts. The only time you rewrite code is before many people use it, or in the new product (which is basically the same thing).
- mark242 15y agoIt's unenforceable. Check page 19 of "Programming the Logic Theory Machine", by Newell and Shaw, published in 1957, for prior art.
- brlewis 15y agoLegally, it's presumed valid. It may be easy to prove that the invention is not novel, but doing so would still involve time, effort, and money. The patent holder needs only to settle for a smaller amount of money than would be required to invalidate the patent.
- dpark 15y agoSorry, this patent is invalid, but your prior art covers a different invention. Page 19 shows a singly-linked list. Page 20 shows nested lists (a list where some elements are also lists). I don't see anything in this document that covers the same type of multiply-linked lists that the patent claims.
- nitrogen 15y agoAs I vaguely alluded to in another response to one of your comments, the argument could go like this: 1. The linked list was described in 1957 or earlier. 2. The cited mention of the linked list also considers more complex permutations of lists. 3. This patent effectively describes adding a single set of items to multiple lists (I haven't read the patent, so I may be glossing over details). 4. #2 demonstrates that such a permutation of the concept of a list would be obvious to anyone skilled in the art. 5. Therefore, the patent is invalid.
- yason 15y agoMy head aches and my mind boggles. I don't know what the heck the patent text actually describes but I see vague visions of linked lists, skip lists, and graphs. I can't imagine what it would say to an USPTO officer or a judge.
- trdlo 15y agoWell, well, well. I am gonna to patent data structures: "Comprising but not limited to: the said node or nodes, containing one or more information items, equipped with one or more pointers, the said pointers pointing to the said nodes...blah blah blah" and I will OWN all your asses. Buuaaahahahahaha!
- lukejduncan 15y agoNot just someone, www.lsi.com or @lsicorporation on twitter did
- srl 15y agoThis patent appears to have gone almost 4 years between being filed and being issued. One wonders what they spent that time doing. Looking through their car's user manual for prior art, perhaps? (Or perhaps they took that phrase literally, and conducted a search of the Louvre...) Even if USPTO was actually doing a good job of vetting patents, that would still have been four years during which anybody seeking to use a multiply linked list would have to do so under the shadow of a possible lawsuit (which would be expensive, even if trivially winnable) if and when the patent was accepted.
- monochromatic 15y agoLooks like it was just sitting there for about 3 years, then it got rejected once, then it was amended and allowed.
- danielharan 15y agoEpic troll too subtly epic?
- jsmcgd 15y agoWould there be any basis to suing the USPTO? If it could be shown that their incompetence/negligence led to an organization suffering loss due to an patently invalid patent? (pun not intended but acknowledged).
- monochromatic 15y agoGoogle "sovereign immunity."
- jsmcgd 15y agoInteresting. I just did a bit but I can't tell if it covers the USPTO? Do you know if it does?
- monochromatic 15y agoNo, I don't know offhand if it would apply in a case like this. But I've never heard of a suit against the patent office for damages from allowing a patent they shouldn't have... and that tells me that there's probably something in the way of such a suit proceeding. Sovereign immunity was just my first guess as to what that might be.
- menardp 15y agoLook more closely. The publishing date is April 1st. http://www.google.com/patents?id=26aJAAAAEBAJ&printsec=abstract&zoom=4#v=onepage&q&f=false http://www.google.com/patents?id=26aJAAAAEBAJ&printsec=a... Clearly this isn't serious.
- dpark 15y agoThat's when the USPTO published it. The filing date was Sep 26, 2002. Maybe the USPTO doesn't consider themselves serious anymore?
- kens 15y agoThe Solaris kernel (for example) has lots of data structures that have multiple linked lists. For example, the cpu structure has at least 6 linked list pointers. For a reference published in 2001 (before the patent was filed): http://books.google.com/books?id=r_cecYD4AKkC&lpg=PA413&ots=oCpgc5AzGU&dq=cpu_prev_onln&pg=PA413#v=onepage&q=cpu_prev_onln&f=false http://books.google.com/books?id=r_cecYD4AKkC&lpg=PA413&... Also note that a doubly linked list is described by claim one.
- tedunangst 15y agoThe cpu structure is on several different lists. That's not exactly the same as being on one list with multiple links.
- nitrogen 15y agoThe cpu structure is on several different lists. That's not exactly the same as being on one list with multiple links. Sure it is: one list with multiple links is the exact same thing as multiple different lists that coincidentally contain the same items.
- jleader 15y agoRemember, by discussing this, you are leaving a permanent record that you are aware of its existence. If you are ever sued for violating it, and by some bizarre horrible legal accident the patent is upheld, you will be liable for treble damages. If the patent owner couldn't prove you were aware of the patent, you'd only be liable for ordinary damages. This is why some large companies have a "never discuss patents in email" policy. It's another way in which patent law is broken; the law actively discourages practitioners from discussing patents, even bad ones.
- Sigi 15y agoit would be funny if this wasn't this sad..
- spc476 15y agoSounds like Ming-Jen Wang patented Ted Nelson's ZigZag structure (http://xanadu.com/zigzag/ http://xanadu.com/zigzag/) which is prior art (fully described at least by 1999-see http://himalia.it.jyu.fi/ffdoc/fenfire/history/Milestones.gen.html http://himalia.it.jyu.fi/ffdoc/fenfire/history/Milestones.ge...) and quite possibly patented by Ted Nelson as well (http://lambda-the-ultimate.org/node/233#comment-1715 http://lambda-the-ultimate.org/node/233#comment-1715). And I'm only familiar with ZigZag because of my interest in Ted Nelson's work, otherwise, it doesn't seem to have gone anywhere.
- romey 15y agoThis is really strange. At the career fair at my school, the USPTO was there recruiting engineers and CS students. Assuming one single person with even a modicum of programming knowledge looked at this application, I can't see any way that this was issued, let alone after 4 years of sitting in purgatory(?). If this was sold to Lodsys could they sue any company that used a doubly linked list without licensing it? How would they even find out about what data structures you used in your code?