Hacker News new | past | comments | ask | show | jobs | submit login
Someone patented linked lists (google.com)
146 points by jarin on Aug 11, 2011 | hide | past | web | favorite | 88 comments



This 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.


At first I thought that too. But within 1 or 2s, I remembered that linked lists have never been limited to single linked lists (except maybe in poor quality courses), multiple linked lists have been around since Unix and very very probably before, have nothing inherently special, so it's absolutely all right to both simply call them "linked list" (like the patent properly does in its title) and to consider them as CS 101.

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.


Never (before you) have I heard someone talk about multiply-linked lists as simply being "linked lists". That term is generally reserved for the "standard" linked list types. Skip lists are also a variant of linked lists, but very few would generally refer to them simply as "linked lists".

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?


Correct me if I'm wrong, but wouldn't a doubly-linked list be covered by this patent? If I understand the claims correctly, the backwards traversal would fall under claim 1.[1] It definitely provides a second sequence to traverse said list, even if it's stretching 'following' a little bit.

[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.


Sure. That alone probably wouldn't invalidate the patent, though. The claim is for a more generic capability.

Of course the patent is obvious and there's (almost certainly) prior art for the multiply-linked list anyway.


I agree there is a risk of misinterpretation as in "all kind all linked lists have been patented, here is the patent" and for this reason, it maybe would have been better to get an even more precise title. By i'm technically still fine with the current one. The claims (both in the application and in the granted patent) barely talk about traversing the "primary" or the "auxiliary" list which provide another sequence (well, providing the same would be... useless), not any kind of tricky algorithm like efficient multiple simultaneous sorting or i don't know what, not even a plain and boring insertion is covered!

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.


Someone else explained my problem with the title better than I managed. http://news.ycombinator.com/item?id=2875082

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?)


I argue that it's claiming the traversal of linked lists, provided you have a choice between at least two linked lists containing the same set of elements. I argue that this restriction is meaningless, because it has no technical impact in this patent. Even when the patent seems to try to be a little more broad, by trying to describe the data structure itself, this description also depends on traversal and nothing else: "[claim 1 ...] said primary function pointer functioning as a primary linked list to direct a computer program to a first sequence to _traverse_ said computerized list [...]" (x2 because the same thing is written for the "auxiliary" list, then x3 in claim 2 for the "tertiary" one).

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" doesn't change the fact that many of us have written data structures involving multiple traversal paths, that these paths are all lists, and that they are all linked, and further that in conversation with peers we have referred to them as Linked Lists.

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 appeal to "authority" doesn't change the fact that many of us have written data structures involving multiple traversal paths, that these paths are all lists, and that they are all linked, and further that in conversation with peers we have referred to them as Linked Lists.

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?


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.

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.


Sorry, but Linked List is class of similar things -- Single-, Double-, Multiple-linkings are all part of the Linked List genre. Just because you associate Linked List strongest with the singly-linked list does not mean that other forms of the same thing, all of which qualify as linked list, can't be called it as well. You are just being disingenuous -- stop it, that is not cool.


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.


In this case, I don't think your analogy holds, because I don't see it as any different than a doubly linked list -- one of the common types. It is just a generalization case of doubly linked list honestly. I see it as about as misleading as finding out the headline gas price was about the premium grade standard pump gasoline rather than the low grade standard pump gasoline, which is maybe a bit tricky, but not rant-worthy.


function_seven's analogy is extremely apt.

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).


A skip list is also part of the "linked list" genre, but it would be misleading to say that William Pugh patented "linked lists" if he actually patented the skip list. (I don't believe he actually patented the skip list, just to be clear.)

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.


I suspect that maybe an intro book skips over some stuff in order to present a good conceptual base rather than a fully rigorous, complete set of definitions and options.

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 maybe an intro book skips over some stuff in order to present a good conceptual base rather than a fully rigorous, complete set of definitions and options.

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.


1) You seem to think that a couple of books somehow form a complete set of all possible linked lists, despite others pointing out equally valid literature that describes things you are not recognizing as linked lists. This is the classic appeal to authority, and suffers from all the normal problems with it. Why do you think only the books you choose to cite are good examples? Why do you dismiss other sources, such as wikipedia and journals elswhere in this thread? Why are those books definitions more reliable than the way the term is used by many many people in academia and industry?

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.


1) What equally valid literature have others pointed out that calls these multiply-linked lists as simply "linked lists"? What journals are you talking about? So far all I've seen are people arguing from their personal views and communications or referencing the title of the patent. Even the reference to multiply-linked lists on Wikipedia was only added in 2009 (and I was the one who pointed this out), and the definition at the top of Wikipedia explicitly lists the same types of lists as TaoCP and Intro to Algos.

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.


It is the title of the patent located on the upper left in google patent. If you search for linked list patent it comes up on patent storm. This does not seem to be a case of deception.

Can you provide other examples of the "anti-patent crowd" being deceptive with their examples?


54, the title, at least in UK (and IIRC in Europe) has no bearing on the field or scope of the invention. I've the vaguest recollection of a case in the UK facing this issue and being judged that the title was not allowed to be used in determining the scope.

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)>)


> It is the title of the patent located on the upper left in google patent. If you search for linked list patent it comes up on patent storm. This does not seem to be a case of deception.

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.


I'd argue it's still a case of deception. The fact that the patent is poorly titled doesn't change that. If the patent were titled "wheel and axle" but contained its current content, it would still be misleading to say that someone had patented the wheel and axle.

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.


Oh, so someone patented a multiply linked list. That's better? It's not like there's not oodles of prior art or it's nonobvious...


I feel like reading comprehension on HN is dropping lately, or at least that some people are willfully choosing to not read entire comments before replying. I specifically said that the patent should not have been granted.

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.


You are correct in that the patent covers a multiply-linked list. Specifically, one with two or more pointers, where the other pointers allow you to traverse the list in other ways.

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.


I agree that this is an obvious invention. I think using the unqualified term "linked list" is misleading, though. As I pointed out elsewhere, references typically do not include the "multiply-linked list" when defining the linked list. They'll mention single, doubly, circularly, and possibly sorted linked lists. I don't see any mention of multiply-linked lists (or equivalent) in Intro to Algos or TaoCP. *

* It's possible that TaoCP covers them somewhere, but I don't see them in the early discussion of linked lists.


It is though, did you read any of the above comments?


Yes, I hopped in my time machine and read xilun0's comment 13 minutes before he actually posted it.


My bad, i thought your comment was in his thread for some reason.


No worries. I'll probably do the same thing to someone else tomorrow. :)


> being misleading

Someone says "linked list" when he means "double linked list". How devious!

> the anti-patent crowd

World conspiracy!


> Someone says "linked list" when he means "double linked list". How devious!

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.


your analogies are flawed. stop trolling.


You are trolling. Your comment uses a pedantic point to purposefully arouse a negative reaction in readers. Bad form.


The ensuing discussion was very helpful for someone like me that is learning. The underlying topics have been intimidating, but have been made much less so by this discussion (YMMV). These discussions often have so much jargon in them, that it becomes frustrating.

In other words, this "trolling" was helpful for me (which is a first).


This modification looks like "Skip List" and according to Wikipedia http://en.wikipedia.org/wiki/Skip_list is was first described in 1990.


This 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.


One 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.


A 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.


This 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 ;).


While I ended up arguing a lot of tangents, my original point was that the title diminishes the standing of the anti-patent crowd. Whether "linked list" is taken as a generic term that describes a whole class of data structures or whether it's restricted to just the basic "linked list" types, the title is misleading. The patent does not cover the basic linked list types nor does cover the entire the entire class.

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.


The patent by itself does not describe a skip list, but the most common skip list implementations use a multilevel list data structure similar to what's described in the patent.


Yes, especially when there is no actual court case.

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.


If you are ok with bad software patents but not patent trolls what is your solution for limiting them?


I've seen several proposals, such as making patents non transferable, shortening their life time or not allowing cases to go to court unless you can prove your business depends on that patent.


Remember, 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.


This 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.


Looks like it was just sitting there for about 3 years, then it got rejected once, then it was amended and allowed.


It's unenforceable. Check page 19 of "Programming the Logic Theory Machine", by Newell and Shaw, published in 1957, for prior art.


Legally, 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.


Exactly. Many smaller businesses can't afford a lengthy legal battle even if they are likely to win.


Lady justice's scales are balanced by cash.

That's why the legal system is wrong.


Sorry, 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.


As 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.


Aside from it being obvious, I'm pretty sure there's prior art for specifically what this patent describes. One of the times this was posted to Reddit someone posted a link to a book that describes pretty much exactly what's in this patent, with a diagram no less. http://my.reddit.com/r/programming/comments/1bbb3/congratula...


Would 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).


Google "sovereign immunity."


Interesting. I just did a bit but I can't tell if it covers the USPTO? Do you know if it does?


No, 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.


Sounds like Ming-Jen Wang patented Ted Nelson's ZigZag structure (http://xanadu.com/zigzag/) which is prior art (fully described at least by 1999-see 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). 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.


Look more closely. The publishing date is April 1st.

http://www.google.com/patents?id=26aJAAAAEBAJ&printsec=a...

Clearly this isn't serious.


That's when the USPTO published it. The filing date was Sep 26, 2002. Maybe the USPTO doesn't consider themselves serious anymore?


The 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&...

Also note that a doubly linked list is described by claim one.


The cpu structure is on several different lists. That's not exactly the same as being on one list with multiple links.


The 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.


This 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?


Not just someone, www.lsi.com or @lsicorporation on twitter did


That actually sounds more like a skip list than a linked list.


My 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.


I'm surprised that this patent was granted.


What 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"?


My understanding is that the patent office checks if the patent is substantially similar to previous patents. A non-novel idea can easily get through if it is phrased in a different way or never appeared in an earlier patent.

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.


Defending against a patent lawsuit, regardless of how absurd or invalid the patent is, can often cost millions of dollars:

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.


More 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.


A: 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?


So 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.


As 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).


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.


Actually I would the kernel a confirmation: The fixed the broken parts gradually without ever throwing everything away and starting over.

[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.


Unfortunatly you should not be. My understanding is that patents on obvious methods are quite common.


Epic troll too subtly epic?


it would be funny if this wasn't this sad..


Patent application


  Application number: 10/260,471
  Publication number: US 2004/0064448 A1
  Filing date: Sep 26, 2002
  Issued patent: US7028023 (Issue date Apr 11, 2006)



Sorry, wrong tab. Other submission was a link to the application. Any any rate, I'm wrong.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: