Someone patented linked lists
google.com
google.com
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.
The patent is both obviously invalid and properly named "Linked List". That it is does not cover the single linked list special case does not changes this fact. The title is neutral, and you are inferring an anti-patent tendency from a neutral reporting (from which crowd btw?). I would be hugely curious to hear on which base you inferred that.
Singly-linked and doubly-linked lists are taught as standard linked lists. Multiply-linked lists are not, because they are not especially useful in most cases. With a doubly-linked list (perhaps more clearly called a bidirectional linked list), all the standard algorithms work with minor or no modifications. With multiply-linked lists, even just inserting an element becomes much more complex. You're now traversing m lists for insertion instead of 1. I would question the quality of your CS101 course if your professor taught you about multiply-linked lists. It's a rather specialized data structure that is generally not beneficial. That time would have been better spent covering a more useful data structure.
I don't have an intro data structures textbook anymore, but I just checked "Introduction to Algorithms, 2nd Ed." and they do not seem to mention multiply-linked lists. "A list may have one of several forms. It may be either singly or doubly linked, it may be sorted or not, and it may be circular or not." For further evidence that multiply-linked lists are not widely considered simply "linked lists", I'll note that Wikipedia didn't mention multiply-linked lists as a variant until 2009. http://en.wikipedia.org/w/index.php?title=Linked_list&di...
As I've already said, I agree that the patent is invalid. It's not novel. But I do not agree that it's simply a "linked list". That term is far more generic and its usage without further clarification implies a much broader claim than the patent makes. Out of curiosity, where in the original Unix were these multiply-linked lists used?
As for why I infer anti-patent tendency, why post this at all except as an example of how the patent system is broken? And why assign it the very broad title "Someone patented linked lists" instead of, say, the more accurate (or at least more specific) "Someone patented a variation of linked lists"? Maybe because the former is more inflammatory?
[1] The relevant part of claim 1 is:
said auxiliary pointer being adapted to direct said
computer program to a second following item and defining
a second sequence to traverse said list.Of course the patent is obvious and there's (almost certainly) prior art for the multiply-linked list anyway.
This is a special case of traversing multiple linked lists, which is a basic technique. I actually even hesitate to say it is a technique, or at least to distinguish this technique from the very same technique of using a single linked list, because I don't think I could ever come up with a plausible justification for why anybody previously knowing how to use one would not be able to use two. The restriction making this a special case is that all lists contain the same set of elements. Given the claims, that restriction is unnecessarily narrow and have no technical effect. So the only thing that distinguish this patent from a patent on a particular (but still 100% basic) use of single linked lists, is the phrasing, and the empty (still given the context) emphasis on the fact there are not one, but two, or even three lists.
So despite the fact that basic singly-linked lists + limited to one list by element would not be covered by this patent even in the parallel universe where it would be considered valid (and while we can note that on the contrary, prev/next linked list would), given that it only claims (with many more sentences) that if you have two lists, you can traverse one, or you can traverse the other, i will continue to argue that it covers linked lists, maybe under certain conditions, all right, but those conditions are insufficient to mandate the precision that this is a modification of linked lists, because it is not a modification, it is just about the basic traversal of multiple plain classical linked lists.
(Also, one a side note, I found it cute how the claims are structured, like if the author thought there was a possibility that prior art could be found for two pointers but not three.)
Edit: About the inflammatory part, it might as well have been even more inflammatory by being even more descriptive. Somebody has patented traversal of linked lists.
Imagine the headline read, "Gas up to $8.23 a gallon" and only upon reading the article did you discover that the "gas" they're talking about is 110 octane race gas. Yes, race gas is a type of gas(oline), but the headline is still quite misleading, as the common definition, without qualifiers, is the pump variety.
As for claims of the patent, it does really cover traversing at all. It mentions it, but the meat of the patent is the data structure having two or three pointers built in for traversing and choosing between those pointers for different traversals. This is all very obvious and frivolous, but it's not claiming the basics of traversing a linked list.
(As for your side note, I found that really strange as well. I can't imagine why thy specifically called out the cases of 2 and 3 pointers. Were they planning on filing later for 4 and 5 when they figured it out?)
There is never any interaction described between one list and the other -- so from the point of view of patenting I don't see anything difference between this patent and a mere description of basic single linked lists, description centered on its traversal (the various enumerations are to be considered as irrelevant in themselves, and are not supplemented by anything else).
That reason alone would be one of the major angle of attack of the patent, would it not be already even more basically invalid because of triviality and prior art. The only challenge would be to present those formal concepts using casual language clearly enough so that nobody would mistake this description as the description of a new structure (even in the hypothetical alternate universe where nobody ever previously used two lists at a times for ordering the same sets of elements)
There is no meat.
Your appeal to "authority" requires the admission that Wikipedia actually supports the counter argument, while an Introduction to anything is hardly an appropriate authority for whether or not something is novel enough to be patented.
I'm glad you are responding to every single person claiming that their experience is wrong, because that provides ample opportunity to reduce your karma.
Your argument doesn't change the fact that it's misleading to refer to any arbitrary linked data structure as a "linked list". You can call a skip list a linked list if you want, but that does't make it appropriate, and it doesn't redefine the language for the more general audience. Go ask your coworkers to draw a linked list on the board and see how many draw a multiply-linked list, or a skip list, or any number of other things that could be pedantically considered "linked lists".
Even if we were to accept the argument that "linked list" is just a generic term for data structures involving linked traversal paths, that would not make the HN title appropriate. If the term "linked list" were that generic, then it would be misleading to apply it to this patent, which clearly does not cover everything that would fall unto the generic "linked list" term.
> Your appeal to "authority" requires the admission that Wikipedia actually supports the counter argument,
Are you seriously trying to criticize my "appeal to authority" by making one of your own?
Nevermind the fact that Wikipedia didn't include the term "multiply-linked" until three years after this patent was granted...
> while an Introduction to anything is hardly an appropriate authority for whether or not something is novel enough to be patented.
Are you really that oblivious? I've said a dozen times that this is not a valid patent. That's not the point.
And an intro book is quite appropriate for establishing what a term covers to the general audience. If something is specialized enough that it's not covered in an intro book, then it's specialized enough that it should not be referred to by the generic term.
> I'm glad you are responding to every single person claiming that their experience is wrong, because that provides ample opportunity to reduce your karma.
Do you really think I care if you or someone else is childish enough to downvote all my comments?
Meta: Since your account is relatively new: I was ready to upvote your comment to try to bring it out of the gray text region (i.e. <=0), until I got to this paragraph. It's okay to think these things, but actually typing them out is considered bad form here. While we're on the subject, the rest of the comment does come across as a bit inflammatory.
Hope this helps.
What you're experiencing right now is called cognitive dissonance or cognitive disequilibrium. You've found that the argument you've been making is at odds with the facts. Claiming that you see no difference between a multiply-linked list and a doubly-linked list is an attempt to shrug off a legitimate point with a nonsensical argument. (Or alternatively you are not skilled enough at programming to understand the topic at hand).
The term "linked list" refers to singly and doubly-linked lists, which may be circular and/or sorted. This is from Intro to Algorithms (2nd ed). It's not just my personal association here.
Compare an intro to calculus book: it presents you with several differentiation or integration methods, yet when you come across the Lebesgue integration technique, you don't run to your intro book and claim "It's not in here, it's not actually integration!"
Again: please stop with the disingenuous stuff -- it's still not cool.
edit: Someone please explain the downvotes to me? Is it because im calling out a guy who repeatedly tells people to not appeal to authority is appealing to authority for that disingenuous behavior?
I suspect that the intro book leaves it out because it's not widely associated with the term, because it's a rather specialized data structure.
TaoCP also doesn't seem to mention multiply-linked lists or anything equivalent in its discussion of linked lists.
> Compare an intro to calculus book: it presents you with several differentiation or integration methods, yet when you come across the Lebesgue integration technique, you don't run to your intro book and claim "It's not in here, it's not actually integration!"
Compare someone claiming that Henri Lebesgue invented integration. It's misleading, not because he didn't invent a type of integration, but because he did not invent integration.
To my mind, the linked list claim is worse than this, because even to advanced practitioners in the field, "linked list" has a relatively specific meaning, and is not generally used to refer to "any data structure with linked elements". One could argue that a graph is a form of linked list, but that's not a common definition.
> Again: please stop with the disingenuous stuff -- it's still not cool.
What's not cool is repeatedly calling someone disingenuous when they take the time to answer you thoughtfully. You're coming off as self-righteous and rude.
2) Don't try to extend my analogy about introductory vs rigorous sources to one about claims and invention and patents, the analogy doesn't hold up to it and such extensions to it are nonsensical. I was only talking about your choice of authority in your appeal to authority, and pointing out flaws with that choice - there was no attempt in that paragraph to discuss the wider validity of the patent claim.
3) You arguments are disingenuous which is why I keep calling them such. Disingenuous does not describe the number of words used, it does however describe repeatedly making logical fallacies that you point out and claim to understand elsewhere in your posts.
As for why my books are more valid, it's because they are well respected books. I see no compelling reason to trust Jorge Stolfi (the user who added multiply-linked lists to Wikipedia) over Knuth, Leiserson, Rivest, and Stein, especially given that the initial definition Wikipedia gives agrees with my sources, and the mention of multiply-linked lists on Wikipedia is only 2 lines long a third of the way down the article. My argument is that "multiply-linked list" is not synonymous with "linked list", and so the HN title is inappropriate. I've not seen much that disputes that.
2) Your analogy doesn't hold up because it's already broken. My extension is "nonsensical" because it shows your analogy to be invalid. I have not disputed that multiply-linked lists can be considered a type of linked list any more than I've disputed that Lebesgue integration is a type of integration. What I have argued is that the term "linked list" is not typically associated with multiply-linked lists, and that using the term the way the title does is misleading.
You mention "appeal to authority", but an appeal to authority is appropriate when defining terms. It's bogus to argue that authoritative sources have no weight when discussing what a term means. And TaoCP is not an "introductory text". I would argue that "Intro to Algorithms" isn't truly an introductory text, either, given that it's authors consider the scope large enough to be used in graduate classes.
3) So basically you don't actually know what disingenuous means. It means insincere, lacking in candor. I'm not disingenuous simply because you disagree with me. I'm not even disingenuous just because I engage in logical fallacies, unless I do so intentionally (not that I believe I've committed any logical fallacies).
I'm also not sure I've accused anyone of logical fallacy. There was the one person who accused me of appeal to authority by appealing to the same authority, but I was mostly calling him ridiculous, not actually accusing him of a legitimate fallacy.
Can you provide other examples of the "anti-patent crowd" being deceptive with their examples?
If the title could be used for such purposes then you need the title to be as broad as possible to avoid reducing the scope of the patent unnecessarily. Suppose you patent "an improvement to a automobile engine" and it's later seen that the same improvement is good for boat engines, rocket engines maybe, etc.. This would be equivalent to file wrapper estoppel¹.
However, the claims define the invention and the title (again at least in the UK) must only signify the field of the invention. If you improve "linked lists" in your invention then you don't make up a new field you call it that. Simply "Linked Lists" is broad, it could easily be shorthand for "Linked Lists used in non-traditional fields" or "An alternative to linked lists", etc., and so is highly unlikely to limit the patent but still meets the regulatory obligation to provide a relevant title.
There I said it. Titles don't matter. Granted claims matter, in this case the claims in the B2, http://www.google.com/patents?id=Szh4AAAAEBAJ&printsec=c... (which don't look modified but I didn't really check).
--
¹ Firefox spellcheck says it's "estoppal" but I think I'm right (for a change ;0)>)
Titles are completely unrelated to the actually claims a patent makes. You can title your patent whatever you want, and it carries zero legal force when it comes to evaluating whether or not an invention is or is not covered by the patent in question.
If we assume the intent here isn't deception, then basing your description of what a patent covers on the patent's title at the very least betrays a deep ignorance of how patents actually function.
None of which is to say that this patent isn't bloody obvious or ought not to be struck down.
And no, I don't feel like digging through a bunch of anti-patent articles looking for misleading claims. Even if this were the only example, the point would stand that using misleading claims makes it harder to trust the movement.
The point is that by being misleading, the anti-patent crowd diminishes their moral standing, and makes it harder for people to take their arguments seriously. This is not simply a "linked list" patent, and anyone with any software development experience who bothers to read past the title should know that.
One example would be a doubly-linked list, though they would presumably limit that claim by pointing out that the other pointers allow you to traverse the list in any way, not merely backwards.
That said, I don't think you'll find many programmers who think of this as anything but the obvious general type of a linked list or who are confused about what is claimed. I do get your point that pro-patent types (who seem mostly to be lawyers) will seize on any slight inaccuracy, though.
We see obvious generalities. They see them divided up. We're looking for general algorithms that can make our software flexible. They're looking for ideas that are just different enough to patent.
* It's possible that TaoCP covers them somewhere, but I don't see them in the early discussion of linked lists.
Someone says "linked list" when he means "double linked list". How devious!
> the anti-patent crowd
World conspiracy!
Someone patented compression. http://www.google.com/patents?vid=4558302
Someone patented search engines. http://www.google.com/patents?vid=6285999
Someone patented public-key cryptography. http://www.google.com/patents?vid=4405829
Obviously none of those statements are misleading in any way.
> World conspiracy!
Just because someone doesn't hold the same viewpoint as you doesn't mean they're wearing a tinfoil hat. Get over yourself.
In other words, this "trolling" was helpful for me (which is a first).
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.
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 ;).
This patent is ridiculous enough without exaggeration. I believe that the patent system is broken, but making misleading claims about frivolous patents weakens the arguments. The truth is already ridiculous enough.
As for your comment about "excessive infighting over apparently trivial concerns", I wish I could dispute that. I feel that geeks as a group tend to be pedantic jackasses, and I'm often guilty of that myself. It does hurt our credibility as a whole.
By the way, your interpretation of multiply-linked lists is correct. You can look at it as multiple separate lists crammed together for minor space savings or as a directed graph with labeled edges (labels here represents which "list" an edge is for). This is why I don't think it's an especially useful data structure; there are better alternatives for most cases.
Let's talk again once the owner of the patent successfully sues over it, making millions in the process.
Never going to happen.
Software patents are not the problem, patent trolls are.
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.
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.
That's why the legal system is wrong.
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.
http://www.google.com/patents?id=26aJAAAAEBAJ&printsec=a...
Clearly this isn't serious.
For a reference published in 2001 (before the patent was filed): http://books.google.com/books?id=r_cecYD4AKkC&lpg=PA413&...
Also note that a doubly linked list is described by claim one.
Sure it is: one list with multiple links is the exact same thing as multiple different lists that coincidentally contain the same items.
I do not feel this is a problem. A patent just provides a legal presumption that you are allowed to file a lawsuit. Some people argue that this enables patent trolls, but patent trolls exist because con artists will always try to ride on the coattails of success. My view is that low standards for patentability provides protection against patent trolls: a company can patent early and often in the years before they hit it big and start attracting con men. Easy patentability also deepens the pool of well-documented prior art, providing more clubs with which to beat up patent trolls.
http://www.inventionstatistics.com/Patent_Litigation_Costs.h...
Filing patents isn't exactly free either, in terms of time or money.
Also, how exactly do you "beat up" patent trolls? They threaten to sue you, and you . . . threaten to spend millions of dollars on court fees to have their patent invalidated? That doesn't work so well unless you have millions of dollars you don't happen to need.
Are you really suggesting that all those small-time devs sued by lodsys over BS patents would have some recourse if only they'd filed a bunch of patents themselves? Or if only their predecessors had somehow flooded the patent office with enough BS patents that the lodsys ones got thrown out as prior art?
The whole "patent everything, let the courts sort it out" philosophy sounds nice in theory, but the whole problem is that it's freakishly expensive to sort those issues out in court, so patent lawsuits end up as shakedowns: you either pay up in licensing, or you pay up in laywer fees. Either way you're paying someone.
The only solution is to defund them and shut them down.
B: That is the only solution? You can not think of any other possible solution?
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.
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).
The 2.6 line of the Linux kernel provides an anecdotal counterargument to this. The kernel team managed to gradually rewrite significant portions of the kernel without ever having to enter a development-only phase. If we could find some way of applying the tools that make this possible (diff, git/DVCSes, peer review, integration tests[0], etc.) to the legal system, maybe the world would be a better place.
The closest thing I'm aware the legal world has now, and it's a far, far cry from what we have in software, is having as much as possible be specific to separate, local governments, so if an individual state comes up with a good solution to a problem, it can be applied elsewhere.
[0] Imagine if all prior court cases were automatically tested against any changes to the law, with changes in outcomes flagged for public review.
[0] would be cool, but probably not possible. You get a court case when the law is ambiguous, or the facts are not known. Neither of which can be automatically tested.
Application number: 10/260,471
Publication number: US 2004/0064448 A1
Filing date: Sep 26, 2002
Issued patent: US7028023 (Issue date Apr 11, 2006)